计算机程序设计基础（谌卫军）第08章_递归算法.pptVIP

1 2 3 4 5 6 7 最后的结果： a 0 1 2 3 4 5 6 下标 具体实现：几重循环语句？ 参考程序：略…… int bsearch(int b[], int x, int L, int R) { int mid; if(L R) return(-1); mid = (L + R)/2; if(x == b[mid]) return mid; else if(x b[mid]) return bsearch(b, x, L, mid-1); else return bsearch(b, x, mid+1, R); } 8.2.4 汉诺(Hanoi)塔问题 相传在古印度Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵守以下规则：每次只允许移动一只盘，且大盘不得落在小盘上（简单吗？若每秒移动一只盘子，需5800亿年） A B C 怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。 1、在A柱上只有一只盘子，假定盘号为1， 这时只需将该盘直接从A搬至C，记为 move from A to C A B C 1 2、在A柱上有二只盘子，1为小盘2为大盘。 分三步进行： A B C 2 1 move from A to B; move from A to C; move form B to C; 3、在A柱上有3只盘子，从小到大分别为1号，2号，3号。怎么移？ A B C 2 1 3 分七步！  分三步进行： move 2 discs from A to B using C； move from A to C； move 2 discs from B to C using A ； A B C 2 1 3 4、在A柱上有 n 个盘子, 从小到大分别为1号、2号、3 号、…、n号。 第 1 步：将1号、2号、…、n-1号盘作为一个整体， 在C的帮助下，从A移至B； 第 2 步：将n号盘从A移至C； 第 3 步：再将1号、2号、…、n-1号盘作为一个整 体，在A的帮助下，从B移至C；  这三步记为： move n-1 discs from A to B using C； move 1 discs from A to C； move n-1 discs from B to C using A ； 递归形式！ 定义函数move(int n, char L, char M, char R); 表示 move n discs from L to R using M； 如果 n = 1，即表示 move from L to R； 移动的是谁？ #include stdio.h void move(int n, char L, char M, char R); void main( ) { int n; printf(请输入一个整数：); scanf(%d, n); move(n, A, B, C); } // L: Left post, M: Middle post, R: Right post void move(int n, char L, char M, char R) { if(n == 1) printf(move #1 from %c to %c\n, L, R); else { move(n-1, L, R, M); printf(move #%d from %c to %c\n, n, L, R); move(n-1, M, L, R); } } 请输入一个整数：3 move #1 from A