第8讲B 涤胼归函数 .pptVIP

A B C …… 让第3个和尚将62个从C到B 第2个和尚的做法 A B C …… 让第3个和尚将62个从C到B 第2个和尚的做法 第3个和尚的做法 第4个和尚的做法 第5个和尚的做法 第6个和尚的做法 第7个和尚的做法 …… 第63个和尚的做法 第64个和尚仅做：将1个从A移到C A B C 将3个盘子从A移到C的全过程 将2个盘子从A移到B A B C 将3个盘子从A移到C的全过程 将2个盘子从A移到B A B C 将3个盘子从A移到C的全过程 将1个盘子从A移到C A B C 将3个盘子从A移到C的全过程 将1个盘子从A移到C A B C 将3个盘子从A移到C的全过程 将2个盘子从B移到C A B C 将3个盘子从A移到C的全过程 将2个盘子从B移到C A B C 将2个盘子从A移到B的过程 将1个盘子从A移到C A B C 将2个盘子从A移到B的过程 将1个盘子从A移到C A B C 将2个盘子从A移到B的过程 将1个盘子从A移到B A B C 将2个盘子从A移到B的过程 将1个盘子从A移到B A B C 将2个盘子从A移到B的过程 将1个盘子从C移到B A B C 将2个盘子从A移到B的过程 将1个盘子从C移到B A B C 将2个盘子从B移到C的过程 A B C 将2个盘子从B移到C的过程 A B C 将2个盘子从B移到C的过程 A B C 将2个盘子从B移到C的过程 由上面的分析可知：将n个盘子从A座移到C座可以分解为以下3个步骤： (1) 将A上n-1个盘借助C座先移到B座上 (2) 把A座上剩下的一个盘移到C座上 (3) 将n-1个盘从B座借助于Ａ座移到C座上 可以将第(1)步和第(3)步表示为： 将“one”座上n-1个盘移到“two”座(借助“three”座)。 在第(1)步和第(3)步中，one 、two、three和A、B、C的对应关系不同。 对第(1)步，对应关系是one对应A，two对应B，three对应C。 对第(3)步，对应关系是one对应B，two对应C，three对应A。 把上面3个步骤分成两类操作： (1) 将n-1个盘从一个座移到另一个座上（n＞1）。这就是大和尚让小和尚做的工作，它是一个递归的过程，即和尚将任务层层下放，直到第64个和尚为止。 (2) 将1个盘子从一个座上移到另一座上。这是大和尚自己做的工作。 编写程序。 用hanoi函数实现第1类操作（即模拟小和尚的任务） 用move函数实现第2类操作（模拟大和尚自己移盘） 函数调用hanoi(n,one,two.three)表示将n个盘子从“one”座移到“three”座的过程(借助“two”座) 函数调用move(x,y)表示将1个盘子从x 座移到y 座的过程。x和y是代表A、B、C座之一，根据每次不同情况分别取A、B、C代入 #include stdio.h int main() { void hanoi(int n,char one, char two,char three); int m; printf(“the number of diskes:); scanf(%d,m); printf(move %d diskes:\n,m); hanoi(m,A,B,C); } void hanoi(int n,char one,char two, char three) { void move(char x,char y); if(n==1) move(one,three); else { hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); } } void move(char x,char y) { printf(%c--%c\n,x,y); } 递归函数 2012/11/26 一种通过重复将问题分解为同类的子问题从而解决问题的方法 “The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recu