清华大学c语言程序设计课件,例8.9_清华大学出版社：c语言程序设计课件_txt_大学课件预览_高等教育资讯网...

例8.9 Hanoi(汉诺)塔问题。这是一个古典的数学

问题&＃xff0c;是一个只有用递归方法(而不可能用其他方法)解决的问题。问题是这样的&＃xff1a;古代有一个梵塔&＃xff0c;塔内有3个座A、B、C&＃xff0c;开始时A座上有64个盘子&＃xff0c;盘子大小不等&＃xff0c;大的在下&＃xff0c;小的在上(图7.13)。有一个老和尚想把这64个盘子从A座移到C座&＃xff0c;但每次只允许移动一个盘&＃xff0c;且在移动过程中在3个座上都始终保持大盘在下&＃xff0c;小盘在上。在移动过程中可以利用B座&＃xff0c;要求编程序打印出移动的步骤。

可以肯定地说&＃xff1a;任何一个人(包括“天才”) 都不可能直接写出移动盘子的每一个具体步骤。请读者试验一下按上面的规律将5个盘子从A座移到C座&＃xff0c;能否直接写出每一步骤?老和尚自然会这样想&＃xff1a;假如有另外一个和尚能有办法将63个盘子从一个座移到另一座。那么&＃xff0c;问题就解决了。此时老和尚只需这样做&＃xff1a;

(1) 命令第2个和尚将63个盘子从A座移到B座&＃xff1b;

(2) 自己将1个盘子(最底下的、最大的盘子)从A座移到C座&＃xff1b;

(3) 再命令第2个和尚将63个盘子从B座移到C座。

至此&＃xff0c;全部任务完成了。这就是递归方法。但是&＃xff0c;有一个问题实际上未解决&＃xff1a;第2个和尚怎样才能将63个盘子从A座移到B座?为了解决将63个盘子从A座移到B座&＃xff0c;第2个和尚又想&＃xff1a;如果有人能将62个盘子从一个座移到另一座&＃xff0c;我就能将63个盘子从A座移到B座&＃xff0c;他是这样做的&＃xff1a;

(1) 命令第3个和尚将62个盘子从A座移到C座&＃xff1b;

(2) 自己将1个盘子从A座移到B座&＃xff1b;

(3) 再命令第3个和尚将62个盘子从C座移到B座。

再进行一次递归。如此“层层下放”,直到后来找到第63个和尚&＃xff0c;让他完成将2个盘子从一个座移到另一座&＃xff0c;进行到此&＃xff0c;问题就接近解决了。最后找到第64个和尚&＃xff0c;让他完成将1个盘子从一个座移到另一座&＃xff0c;至此&＃xff0c;全部工作都已落实&＃xff0c;都是可以执行的。可以看出&＃xff0c;递归的结束条件是最后一个和尚只需移一个盘子。否则递归还要继续进行下去。

应当说明&＃xff0c;只有第64个和尚的任务完成后&＃xff0c;第63个和尚的任务才能完成。只有第2到第64个和尚任务完成后&＃xff0c;第1个和尚的任务才能完成。这是一个典型的递归的问题。为使问题简化&＃xff0c;我们先分析将A座上3个盘子移到C座上的过程&＃xff1a;

(1) 将A座上2个盘子移到B座上(借助C)&＃xff1b;

(2) 将A座上1个盘子移到C座上&＃xff1b;

(3) 将B座上2个盘子移到C座上(借助A)。

其中第2步可以直接实现。第1步又可用递归方法分解为&＃xff1a;

1&＃xff0e;1将A上1个盘子从A移到C&＃xff1b;

1&＃xff0e;2将A上1个盘子从A移到B&＃xff1b;

1&＃xff0e;3将C上1个盘子从C移到B。

第3步可以分解为&＃xff1a;

3&＃xff0e;1将B上1个盘子从B移到A上&＃xff1b;

3&＃xff0e;2将B上1个盘子从B移到C上&＃xff1b;

3&＃xff0e;3将A上1个盘子从A移到C上。

将以上综合起来&＃xff0c;可得到移动3个盘子的步骤为

A→C&＃xff0c;A→B&＃xff0c;C→B&＃xff0c;A→C&＃xff0c;B→A&＃xff0c;B→C&＃xff0c;A→C。

共经历7步。由此可推出&＃xff1a;移动n个盘子要经历2n-1步。如移4个盘子经历15步&＃xff0c;移5个盘子经历31步&＃xff0c;移64个盘子经历264-1步。

由上面的分析可知&＃xff1a;将n个盘子从A座移到C座可以分解为以下3个步骤&＃xff1a;

(1) 将A上n-1个盘借助C座先移到B座上。

(2) 把A座上剩下的一个盘移到C座上。

(3) 将n-1个盘从B座借助于A座移到C座上。

上面第1步和第3步&＃xff0c;都是把n-1个盘从一个座移到另一个座上&＃xff0c;采取的办法是一样的&＃xff0c;只是座的名字不同而已。为使之一般化&＃xff0c;可以将第1步和第3步表示为&＃xff1a;

“将“one” 座上n-1个盘移到“two” 座(借助“three” 座)。只是在第①步和第③步中&＃xff0c;one、two、three和A、B、C的对应关系不同。对第①步&＃xff0c;对应关系是one——A&＃xff0c;two——B&＃xff0c;three——C。对第③步&＃xff0c;是&＃xff1a;one——B&＃xff0c;two——C&＃xff0c;three——A。

因此&＃xff0c;可以把上面3个步骤分成两类操作&＃xff1a;

(1) 将n-1个盘从一个座移到另一个座上(n>1)。这就是大和尚让小和尚做的工作&＃xff0c;它是一个递归的过程&＃xff0c;即和尚将任务层层下放&＃xff0c;直到第64个和尚为止。

(2) 将1个盘子从一个座上移到另一座上。这是大和尚自己做的工作。

下面编写程序。分别用两个函数实现以上的两类操作&＃xff0c;用hanoi函数实现上面第1类操作(即模拟小和尚的任务)&＃xff0c;用move函数实现上面第2类操作(模拟大和尚自己移盘)&＃xff0c;函数调用hanoi(n&＃xff0c;one&＃xff0c;two&＃xff0c;three)表示“将n个盘子从“one” 座移到“three” 座的过程(借助“two”针”)。函数调用move(x&＃xff0c;y)表示将1个盘子从x 座移到y 座的过程。x和y是代表A、B、C座之一&＃xff0c;根据每次不同情况分别取A、B、C代入。

程序如下&＃xff1a;

void move(char x&＃xff0c;char y)

&＃xff5b;

printf("%c-->%c\n"&＃xff0c;x&＃xff0c;y)&＃xff1b;

&＃xff5d;

void hanoi(int n&＃xff0c;char one&＃xff0c;char two&＃xff0c;char three)

/*将n个盘从one座借助two座&＃xff0c;移到three座/

&＃xff5b;

if(n&＃xff1d;&＃xff1d;1) move(one&＃xff0c;three)&＃xff1b;

else

&＃xff5b;

hanoi(n-1&＃xff0c;one&＃xff0c;three&＃xff0c;two)&＃xff1b;

move(one&＃xff0c;three)&＃xff1b;

hanoi(n-1&＃xff0c;two&＃xff0c;one&＃xff0c;three)&＃xff1b;

&＃xff5d;

&＃xff5d;

main()

&＃xff5b;

int m&＃xff1b;

printf("input the number of diskes&＃xff1a;")&＃xff1b;

scanf("%d"&＃xff0c;&m)&＃xff1b;

printf("The step to moving %3d diskes&＃xff1a;\n"&＃xff0c;m)&＃xff1b;

hanoi(m&＃xff0c;′A′&＃xff0c;′B′&＃xff0c;′C′)&＃xff1b;

&＃xff5d;

运行情况如下&＃xff1a;

input the number of diskes&＃xff1a;3

The step to moving 3 diskes&＃xff1a;

A-->C

A-->B

C-->B

A-->C

B-->A

B-->C

A-->C

在本程序中move函数并未真正移动盘子&＃xff0c;而只是打印出移盘的方案(从哪一个座移到哪一个座)。