深さ優先検索、再帰の実装の仕方まとめ。
//基本はこういう感じ。実際にはこれだと無限ループしてしまうので、条件分岐させる。
int solve(int i, int n) {
solve(i+1, n+1);
solve(i+1, n);
return 0;
}
//何かの法則を見つけて再帰
そのまえに、再帰のおさらい。
int func(int n) {
int ans = 1;
if(n == 0) return ans;
ans = n * func(n-1);
cout << "ans::" << ans << endl;
return ans;
}
//木（の枝）を想像すればいい。
とりあえず、行き止まりまで進む(太字：分岐点）
A B C D E F G
1 2 3 4 5
8 9
流れとしては、A->B->C(分岐)->D->E ->F->G(Gで値が返される。)
C <-D<-E <-F //Dまでreturnに行きつく。次はC->1のルート
->1->2(分岐)->3->4->5 //5で値が返される
2 <-3<-4 //3までreturnに行きつく。
->8->9 //9で値が返される
2 <-8 //2も全ての枝分かれまで進んだので2でもreturn
C <-1<-
A<-B<- //ようやくAの値が分かる
return値が返される順番としては、
(G-F-E-D-(5-4-3-(9-8-)2-1-)C-B-A) こんな感じ。
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
ハノイの塔
2つのときどうするかを考える。-:empty 1 1 2 - - → 2 1 - → - 1 2 → - - 2 ----------- ----------- ----------- ---------- // 1が真中へ 2が右端へ 1が2の上に乗って右端へ
二つだと簡単だが４つだとどうすればいいか。考え方としてはかんたんで、1が複数になればどうだろう、と考える。
(1~n-1)が真中へ nが右端へ (1~n-1)がnの上に乗って右端へ
これをそっくりそのまま書けばよい。
void Hanoi(int n, int from, int work, int dest) {
if(n == 1) {
printf("1を%dから、%dへ移動\n", from, dest);
} else {
Hanoi(n-1, from, dest, work); //(1~n-1)が真中へ
printf("%dを%dから、%dへ移動\n", n, from, dest); //nが右端へ
Hanoi(n-1, work, from, dest); //(1~n-1)がnの上に乗って右端へ
}
}
//n-1で深く潜るので、そのままでは無限ループする。
なので、n = 1のとき止まるようにしたい。要するに条件分岐すればよい。
//わかれば簡単。深く考えずに。
//
再帰関数というのは要するに、「進むか後退する（再帰）→ブレーキをかける（条件分岐）」の繰り返し。
考え方のコツとしては、最初を考えて、行き止まりのときを考える。この二つだけでよい。
つまり、
int solve(int i, int n) {
//初めを考える。
solve(i+1, n+1);
solve(i+1, n);
//行き止まりでここに来た時どうするかを考える。
return 0;
}
数を求める
trueかfalseか求める
迷路問題
だいたいは幅優先検索で解いた方が簡単だが、練習のために深さ検索でも解けるようにしておく。
迷路問題でややこしいのが、「一度通った道をどう処理すべきか」ということ。結論を言うと、通ったかどうかのフラグはグローバル変数にして管理できる。
とりあえず、一度通った道を通らないように設計したプログラムを作ってみる。
SRM425 div2 medium
double getProbability(int n, int east, int west, int south, int north) {
m_east = east/100.0; m_west = west/100.0;
m_south = south/100.0; m_north = north/100.0;
memset(m_step, true, sizeof m_step);
return prob;
}
double CrazyBot::dfs(int cnt, int x, int y) {
printf("(%d, %d) ", x, y); //for debug
if(cnt == 0) {
return 1.0;
}
double r = 0.0;
m_step[x][y] = false;
if(m_step[x-1][y]) r += m_north*dfs(cnt-1, x-1, y);
if(m_step[x+1][y]) r += m_south*dfs(cnt-1, x+1, y);
if(m_step[x][y-1]) r += m_west*dfs(cnt-1, x, y-1);
if(m_step[x][y+1]) r += m_east*dfs(cnt-1, x, y+1);
putchar('\n'); //for debug
m_step[x][y] = true;
return r;
}
赤色::printf("(%d, %d) ", x, y); //for debug のx, yの位置
cnt = 2 cnt = 1 cnt = 0 break;
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
このあとに、行き止まりになったとき、
一旦0になったから、1に戻る。 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 --> 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 //このあとに、青色の部分でも同じことを行う。
実際の動作はこんな感じだが、深く考えずに１回目と２回目以降の２つだけを考えてみる。
スタート地点のマス 今踏んでいるマスを踏んだことにする。flag = false; 行けるマスに進む //ここまでたどり着いたら全てまわったということに自然になっている。 flag = 0のままなら、全く違う道を行くとき、通っていないのに通っているとみなされるので、 flag = 1にして、元の状態に戻しておく。 //↑多分この動作を考えるのが、一番難しいんじゃないか。
