汉诺塔问题求解。相传在古印度圣庙中，有一种被称为汉诺塔（Hanoi）的游戏。该游戏是在一块铜板装置上，有3根杆（编号A、B、C），在A杆自下而上、由大到小按顺序放置64个金盘（如下图）。游戏的目标：把

汉诺塔问题求解。相传在古印度圣庙中，有一种被称为汉诺塔（Hanoi）的游戏。该游戏是在一块铜板装置上，有3根杆（编号A、B、C），在A杆自下而上、由大到小按顺序放置64个金盘（如下图）。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。请编写程序，实现从键盘上输入一个小于等于64的正整数表示金盘数，打印出移动的步骤。XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【分析】依题意可将其抽象为一个数学问题，如上图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移动一个盘子且大盘子不能在小盘子上面，求移动的步骤。其间，可以利用B柱子作为中间过渡。XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当n=1时XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第1次1号盘A----﹥C　　js=1次XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当n=2时XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第1次1号盘A----﹥BXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第2次2号盘A----﹥CXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第3次1号盘B----﹥C　　js=3次XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当n=3时XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第1次1号盘A----﹥CXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第2次2号盘A----﹥BXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第3次1号盘C----﹥BXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第4次3号盘A----﹥CXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第5次1号盘B----﹥AXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第6次2号盘B----﹥CXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第7次1号盘A----﹥C　　js=7次XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

不难发现规律：1个圆盘移动的次数是2的1次方减1XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2个圆盘移动的次数是2的2次方减1XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3个圆盘移动的次数是2的3次方减1XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

------XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

n个圆盘移动的次数2的n次方减1XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

故：移动次数为2n-1XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【算法描述】XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

通过上面的分析不难发现，本例问题求解应通过函数递归调用来实现。可以简单分为三个步骤。XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第一步：把n-1个盘子由A移到BXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第二步：把第n个盘子由A移到CXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第三步：把n-1个盘子由B移到CXxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

（1）自定义一个递归函数mov（），其包含四个参数分别表示金盘个数、A杆、B杆与C杆上的个数，并且该函数的函数体包含自调用语句；XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

（2）由主函数调用mov（）函数，且金盘总数由键盘输入，最后输出每一步的过程；XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

（3）输出结果，结束程序。XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【参考程序】XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【运行情况】XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

XxU100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库