《数据结构用C语言描述》第三章.jsp.ppt

计算斐波那契数列的函数Fib(n)的定义  求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n = 1 ) return n;  else return Fib (n-1) + Fib (n-2); }  如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 斐波那契数列的递归调用树 Fib(1) Fib(0) Fib(1) Fib(2) Fib(3) Fib(4) Fib(1) Fib(0) Fib(2) Fib(1) Fib(0) Fib(1) Fib(2) Fib(3) Fib(5) Fib(1) Fib(0) Fib(2) Fib(1) Fib(0) Fib(2) Fib(1) Fib(3) Fib(4) ? ? ? ? ? ? ? ? ? 栈结点 n tag tag = 1, 向左递归；tag = 2, 向右递归 Fib(1) Fib(0) Fib(2) Fib(1) Fib(0) Fib(2) Fib(1) Fib(3) Fib(4) ? ? ? ? ? ? ? ? ? 2 1 3 1 4 1 n=1 sum=0+1 2 2 3 1 4 1 n=2-2 3 1 4 1 n=0 sum=1+0 3 2 4 1 n=3-2 ? ? ? ? 4 1 n=1 sum=1+1 4 2 ? n=4-2 ? ? ? ? ? ? ? ? ? ? ? ? ? Fib(1) Fib(0) Fib(2) Fib(1) Fib(0) Fib(2) Fib(1) Fib(3) Fib(4) ? ? ? ? ? ? ? ? ? 2 1 4 2 n=1 sum=2+1 2 2 4 2 n=2-2 4 2 n=0 sum=3+0 ? ? ? ? ? ? ? ? long Fibnacci ( long n ) { StackNode S; Node *w; long sum = 0; //反复执行直到所有终端结点数据累加完 do { while ( n 1 ) { w-n = n; w-tag = 1; S.push ( w ); n--; } //向左递归到底, 边走边进栈 sum = sum + n; //执行求和 while ( !S.IsEmpty( ) ) { w = S.getTop( ); S.Pop( ); if ( w-tag == 1 ) { //改为向右递归 w-tag = 2; S.push ( w ); n = w-n – 2; //F(n)右侧为F(n-2) break; } } } while ( !S.IsEmpty( ) ); return sum; } 递归与回溯 n皇后问题 在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。 1#主对角线 3#主对角线 5#主对角线 ? ? ? 0#次对角线 2#次对角线 4#次对角线 6#次对角线 1#次对角线 3#次对角线 5#次对角线 0#主对角线 2#主对角线 4#主对角线 6#主对角线 ? 0 1 2 3 0 1 2 3 k = i+j k = n+i-j-1 解题思路 安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 ) 在第 j 列安放一个皇后： 如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。 如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。 设置 4 个数组 col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] : md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] : sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] : q[i] 记录第 i 行皇后在第几列 void queen( int i ) { for ( int j = 0; j n; j++ ) { i