第一章 c语言_递归算法.ppt

第八章 递归算法 第八章 递归算法 8.2.1 分而治之 8.2.2 寻找最大值 8.2.3 折半查找法 问题分析 8.2.4 汉诺(Hanoi)塔问题 8.2.5 青蛙过河 8.2.6 快速排序 第八章 递归算法 8.3.1 分书问题 8.3.2 下楼问题 8.3.3 八皇后问题 8.3.4 过河问题 问题分析 问题分析 技术难点 8.3.5 排列问题 问题实质：在一个有向图中寻找一条路径； 状态转换：如何从一个结点跳转到另一个结点； 状态树？ 如何避免访问重复的结点？ 如何用简练的语句实现状态的转换？ 如何将5种情形归纳为同一种形式？ #include stdio.h #define MAX_M 20 #define MAX_N 20 int M, N; struct Status { int W, D, B; }steps[1000]; int s = 0, num = 0; int flags[MAX_M][MAX_N][2] = {0}; void CrossRiver(int W, int D, int B); int IsValid(int w, int d, int b); void main( ) { scanf(%d %d, M, N); flags[M][N][0] = 1; steps[0].W = M; steps[0].D = N; steps[0].B = 0; s = 1; CrossRiver(M, N, 0); } void CrossRiver(int W, int D, int B) { int i, j, f; int w, d, b; if(B == 0) f = -1; else f = 1; for(j = 1; j = 5; j++) { switch(j) { case 1: w = W + f*1; d = D; break; case 2: w = W + f*2; d = D; break; case 3: d = D + f*1; w = W; break; case 4: d = D + f*2; w = W; break; case 5: w = W + f*1; d = D + f*1; break; } b = 1 - B; if(IsValid(w, d, b)) { flags[w][d][b] = 1; steps[s].W = w; steps[s].D = d; steps[s].B = b; s++; if(w == 0 d == 0 b == 1) { num ++; printf(Solutions %d: \n, num); for(i = 0; i s; i++) printf(%d %d %d\n, steps[i].W, steps[i].D, steps[i].B); } else CrossRiver(w, d, b); flags[w][d][b] = 0; s--; } } } int IsValid(int w, int d, int b) { if(w 0 || w M) return 0; if(d 0 || d N) return 0; if(flags[w][d][b] == 1) return 0; if(d 0 w d) return 0; if((N-d 0) (M-w N-d)) return 0; return 1; } 2 2 Solutions 1: 2 2 0 0 2 1 1 2 0 1 0 1 2 0 0 0 0 1 Solutions 2: 2 2