再帰処理を学ぶ

AtCoder 版！蟻本 (初級編)

今日からAtCoder 版！蟻本 (初級編)の記事を読み進めましょう！
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。
ここからは長い期間がかかります。

全探索

前回はfor文における全探索を学びました。
しかし、全探索には再帰処理、bit全探索など種類があります。
一つずつ学習していきましょう。

V - 2.05.再帰関数

再帰関数を記述する際には、ベースケースである終了条件、再帰関数を呼び出す再帰ステップと考えて記載すると分かりやすいです。

C++

// n を受け取って、0~n の総和を計算して返す関数
int sum(int n) {
  // ベースケース
  if (n == 0) {
    return 0;
  }

  // 再帰ステップ
  int s = sum(n - 1);
  return s + n;
}

例題

例題 2-1-1　部分和問題

問題は蟻本を参照してください。(ここに記載すると著作権の問題が発生します。)

深さ優先探索、幅優先探索は再帰処理 で解きます。
i番目の数を足した時、足さなかった時を条件分岐して書きましょう。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int n, k;
vector<int> a(n, 0);

bool dfs(int i, int sum){
    // ベースケース
    if(i == n) return sum == k;
    // 再帰ステップ
    if(dfs(i+1, sum)) return true;
    if(dfs(i+1, sum + a[i])) return true;

    return false;
}

int main(int argc, const char * argv[]) {
    cin >> n;

    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    cin >> k;

    if(dfs(0, 0)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

C - たくさんの数式

問題文はAtCoderを参照してください。

• 上記の問題のように+を入れるか入れないかで再帰をしていく。
• 9999999999の入力の際は10桁を超えるのでlong long型を使いましょう。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

ll dfs(int i, ll sum, string s){
    // ベースケース
    if(i >= s.length()) return sum;
    // 再起ステップ
    // +を代入しない
    ll sum1 = dfs(i+1, 0, s);
    // +を代入する
    if(i+1 < s.length()) s = s.insert(i+1, "+");
    // 加算
    string tmp;
    int c=0;
    ll sum2=0;
    while(c < s.length()){
        if(s.substr(c, 1) == "+"){
            // +なら加算処理
            sum2+=atoll(tmp.c_str());
            // 加算後は再度数字を連結するのでクリア
            tmp.clear();
        }else{
            // 数字なら文字列を連結
            tmp += s[c];
        }
        c++;
    };

    // 最後の数字を加算
    if(tmp.length()>0) sum2+=atoll(tmp.c_str());
    sum2 = dfs(i+2, sum2, s);

    return sum1+sum2;
}

int main(int argc, const char * argv[]) {
    string s;

    cin >> s;

    ll sum = dfs(0, 0, s);

    cout << sum << endl;

    return 0;
}

私みたいな灰色コーダーにも分かるように記載。
ACで通りました。