関数の中で同じ関数を呼び出すことを再帰呼び出しといい、再帰呼び出しをする関数を再帰関数という。
階乗を計算する関数 int fact(int n)を作りたい。n! = n*(n-1)!なので
int fact(int n) {
if (n == 0)return 1;
return n * fact(n - 1);
}
フィボナッチ数列を計算する関数int fib(int n)を書いてみましょう。フィボナッチ数列の定義はa[0]=0,a[1]=1かつa[n]=a[n-1]+an-2です。この場合、初項の条件が終了条件にあたります。数列の定義をそのまま関数にするだけで書くことができます。
int fib(int n) {
if (n <= 1) return n;
else return fib(n - 1) + fib(n - 2);
}
メモ探索という考え方を使えば高速化できるらしい
int mamo[MAX_N + 1];
int fib(int n) {
if (n <= 1)return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
いまはよくわからない
スタック
# include<iostream>
# include<stack>
using namespace std;
int main() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
cout << s.top();//3
s.pop();
cout << s.top();//2
s.pop();
cout << s.top();//1
s.pop();
return 0;
}
キューは、スタックの上からじゃなくて下から取り出すバージョン
深さ優先探索は、一番初めの状態から遷移を繰り返すことでたどり着ける全ての状態を生成する。従って全ての状態に対して操作を施したり、全状態を列挙したりできる。
例題
整数a[1],a[2],,,,a[n]が与えられます。その中からいくつか選び、その和をちょうどｋにすることができるか判定しなさい。ただし、
1<=n<=20,-108<=a[i]<=108,-108<=k<=108
前もやったなこれ確か。a[1]から順に加えるかどうか決めていきｎ個全てについて決め終わったらその和がｋに等しくなるかを判定する
# include<iostream>
using namespace std;
int a[21];
int n, k;
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() {
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (dfs(0, 0))cout << "Yes";
else cout << "NO";
return 0;
}
再帰で解くとこういう感じなのか
ちなみに動的計画法も一応
# include<iostream>
using namespace std;
int main(){
int n,a[100], A;
bool dp[100][10010];
cin >> n >> A;
for (int i = 0; i < n; i++)cin >> a[i];
memset(dp,0,sizeof(dp));//いったん全部falseに
dp[0][0] = true;//dp[0][0]だけtrueに
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= A; ++j) {
if(j<a[i])dp[i + 1][j] = dp[i][j];
else dp[i + 1][j] = dp[i][j- a[i]] | dp[i][j];
}
}
if (dp[n][A])cout << "yes";
else cout << "no";
return 0;
}
Lake Counting
大きさがＮ×Ｍの庭があります。そこに雨が降り、水たまりができました。水たまりは８近傍で隣接している場合に繋がっているとみなします。全部でいくつの水たまりがあるでしょうか。
N,M<=100;
方針
適当なＷから始め、そこから繋がっている部分を．に置き換えるという操作を繰り返していきます。１回のＤＦＳで、はじめのＷとつながっているＷは全部．に置き換わるので、Ｗがなくなるまでに何回ＤＦＳを行ったかが答えになります。状態の遷移は８方向の移動の８通りで、ＤＦＳは各マスに対してたかだか１回しか呼ばれないので計算量はＯ(8NM)となります。
# include<iostream>
# include<algorithm>
# include<string>
using namespace std;
int N,M;
char field[110][110];
void dfs(int x, int y) {
field[x][y] = '.';
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int nx = x + dx, ny = y + dy;
if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W')
dfs(nx, ny);
}
}
return;
}
int main() {
int res = 0;
cin >> N >> M;
char tmp;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> tmp
field[i][j] = tmp;
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (field[i][j] == 'W') {
dfs(i, j);
res++;
}
}
}
cout << res;
}
あとネットで見たvectorとqueueを使う解き方
# include<iostream>
# include<string>
# include<vector>
# include<queue>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
vector<string>grid(N);
for (int i = 0; i < M; ++i) {
cin >> grid[i];
}
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; ++j) {
if (grid[i][j] == 'W') {
queue<pair<int, int>>q;
q.push(make_pair(i, j));
grid[i][j] = '.';
while (!q.empty()) {
const pair<int, int>p = q.front();
q.pop();
for (int d = 0; d < 8; d++) {
static const int di[] = { -1,-1,-1,0,0,1,1,1 };
static const int dj[] = { -1,0,1,-1,1,-1,0,1 };
const int k = p.first + di[d];
const int l = p.second + dj[d];
if (0 <= k && k < N && 0 <= l && l < M&&grid[k][l] == 'W') {
grid[k][l] = '.';
q.push(make_pair(k, l));
}
}
}
++ans;
}
}
}
cout << ans << endl;
return 0;
}
幅優先探索も探索の手法の一つ。深さ優先探索と同じく、ある状態から始めてたどり着ける全ての状態を探索する。深さ優先探索と違うところは探索する順番で、幅優先探索でははじめの状態に近いほうから探索します。つまり、初めの状態→最短一回の遷移でたどり着ける全ての状態→最短二回の遷移でたどり着ける全ての状態→、、、、、という順に探索していきます。幅優先探索では同じ状態は一度しか通らないので、計算量はＯ（状態数×遷移の仕方）程度になります。
深さ優先探索ではスタックを使っていましたが幅優先探索ではキューを使います。最初に、初期状態をキューに入れます。その後、キューから状態を取り出し、そこから遷移出来るすべての訪れたことのない状態をキューに入れる、という操作をキューが空になるか、解が見つかるまで繰り返します。キューの様子を見てみると、初期条件に近い順に出てきていることがわかります。なんとなく全部写した。
迷路の最短路
列の数がm,行の数がnのマスで構成される迷路がある。迷路の各マスはスタート(s)、ゴール(g)、通行可能なマス(0)、通行不可能なマス(1)のいずれかの状態である。スタート(s)から出発し、上下左右に１マスずつ通行可能なマス(0)のみ通りゴール(g)まで移動した場合の、最短歩数を求めよ。
N,M<=100
まず、迷路を作成する。各マスの訪問履歴を作成する。スタートのマスをキューに格納する。キューの先頭から一マス取得する。取り出したマスがゴールなら終了。前に取り出したマスから上下左右の何れかに移動する。移動先のマスが迷路外でないことを確認する。
# include<iostream>
# include<queue>
# include<string>
# include<cstdio>
using namespace std;
const int INF = 100000000;
typedef pair<int, int>P;
char maze[110][110];//迷路を表す文字列の配列
int N, M;
int sx, sy;//スタートの座標
int gx, gy;//ゴールの座標
int d[110][110];//各点までの最短距離の配列
int dx[4] = { 1,0,-1,0 }, dy[4]{ 0,1,0,-1 };//移動4方向のベクトル
//{sx,sy}から{gx,gy}への最短距離を求める
//たどり着けないとINF；
int dfs() {
queue<P>que;
//全ての点をINFで初期化
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
d[i][j] = INF;
}
}
que.push(P(sx, sy));
d[sx][sy] = 0;
while (que.size()) {
}
}