帕斯卡·河内塔执行过程

这是一个经典的递归。

分析:这是一个非常好的递归编程的例子。与之前的递归程序不同，他先有一个非递归程序，然后重写为递归形式。如果这个问题不使用递归过程，可能无法启动。让我们以三块金子为例:

要从条形a移动到条形b，您必须在条形c的帮助下进行转换。移动方案为:

A-B

步骤2 A-C

第三步B-C

A-B

第五步C-A

步骤6 C-B

A-B

* * *移动七次完成A极上的三枚金块，按照题目要求的规则移动到B极。

题目要求以同样的方式将N枚金币从A杆移动到B杆:

1.首先(递归地)将A杠上面的n-1块移动到C杠上(使用B杠)；

2.然后把A杠上唯一的一块移到B杠上；

3.然后将C条上的n-1块(递归)移动到B条上(使用A条)。

这是一个递归调用过程。该过程如下:

程序P6-14；

定义变量

n:整数；

过程移动(n:整数；a，b，c:char)；{定义递归过程}

开始

如果n=1，则

writeln('move '，n，' from '，a，' to '，b)

Else {多个切片，递归}

开始

move(n-1，a，c，b)；{递归地将n-1块从A移动到C，并使用杆B进行转换}

writeln('move '，n，' from '，a，' to '，b)；{最后一部电影从A移到b}

移动(n-1，c，a，b)；{递归地将杆C上的n-1移动到杆B上，并使用杆A进行过渡}

结束；

结束；

开始{主程序}

write('输入n:')；

读作(n)；

move(n，' A '，' B '，' C ')；

结束。

运行:

输入n: 3(回车)

将1从A移动到B

将2从A移动到C

将1从B移动到C

将3从A移动到B

将1从C移动到A

将2从C移动到B

将1从A移动到B

程序运行时，输入n的值，除了3，可以选择4，5，6，但千万不要输入64。因为通过推演，如果按照规则移动64枚金币，你要移动2 64-1 = 1.8 * 10 19次。如果每秒移动一次，就需要一万亿年。根据科学计算，地球的“寿命”大约是几十亿到几百亿年。你可以看到地球的毁灭，你也无法完成游戏。即使计算机每秒钟“移动”一亿次，也需要5800年，所以不可能完成游戏。

这样够详细了吧？摘自《Pascal语言中学版第2版，青少年信息学奥林匹克竞赛训练教材》北京理工大学出版社，这个还不错。