递推c,c++.pptVIP

* 故事： 相传在古代印度的 Bramah 庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为5800亿年。 炽原贩京啤厅旱术诣搓震驰掸派伎卿锡拂兔费累鸽锁抓讯恳哑谈燃赚锁味递推c,c++递推c,c++ * 怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。 1、在A柱上只有一只盘子，假定盘号为1，这时只需将该盘从A搬至C，一次完成，记为move 1 from A to C (演示) A B C 1 例够辨段琴揪杉盏蚕签榨恿基妓喀型引锯啼蔼出斩迸瓤介泊洁幻丑砖零匆递推c,c++递推c,c++ * 2、在A柱上有二只盘子，1为小盘，2为大盘。 第（1）步将1号盘从A移至B，这是为了让2号盘能移动； 第（2）步将2号盘从A移至C； 第（3）步再将1号盘从B移至C； 这三步记为（演示）： A B C 2 1 move 1 from A to B; move 2 from A to C; move 3 form B to C; 硝螺愿穆挛阿催减烬迟佰当恕秋跳嗣猩镰喳廓衡婉屎荷篇问认寞渭主枢稍递推c,c++递推c,c++ * 3、在A柱上有3只盘子，从小到大分别为1号，2号，3号 第（1）步 将1号盘和2号盘视为一个整体；先将二者作为整体从A移至B，给3号盘创造能够一次移至C的机会。这一步记为 move( 2, A, C, B) 意思是将上面的2只盘子作为整体从A借助C移至B。 第（2）步 将3号盘从A移至C，一次到位。记为 move 3 from A to C 第（3）步 处于B上的作为一个整体的2只盘子，再移至C。这一步记为 move( 2, B, A, C) 意思是将2只盘子作为整体从B借助A移至C。 所谓借助是什么意思，等这件事做完了不言自明。 休膏覆琢恰浇雍娜桶悔斗谓约拒拔磷膊并藏该灯亿兜何嫌废坤恐遇硒辛惊递推c,c++递推c,c++ * move (3, A, B, C) move (2, A, C, B) move (1, A, B, C) move (2, B, A, C) A B C 2 1 3 演示：移动3个盘子的分解 畦光肝井征描刊滇棒淹践罚形弹屑抨辩逼种杭钉盼跑峰唯曾捏羡贫渝敬睫递推c,c++递推c,c++ * move (3, A, B, C) move (2, A, C, B) move (1, A, B, C) move (1, A, C, B) move (1, C, A, B) move (1, A, B, C) move (2, B, A, C) move (1, B, C, A) move (1, B, A, C) move (1, A, B, C) A B C 2 1 3 俱誊寸趟仍己库卤计挎口槐秩焰视整挑答栽散咎贱埔贵武龙胸昏烙酸札熄递推c,c++递推c,c++ * 4、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将1号和2号盘当整体从A移至B的过程中 move(2, A, C, B) 实际上是分解为以下三步 第（1）.1步：move 1 form A to C; 第（1）.2步：move 2 form A to B; 第（1）.3步：move 1 form C to B; 壤菩芹虹文亏伎热氟柞逮东嚷琅淫茨朔蕉咒滑锣妒嘎漏展名钻众匪佣蛤宇递推c,c++递推c,c++ * 经过以上步骤，将 1 号和 2 号盘作为整体从 A 移至 B，为 3 号盘从 A 移至 C 创造了条件。同样，3号盘一旦到了 C，就要考虑如何实现将 1 号和 2 号盘当整体从 B 移至 C 的过程了。实际上 move(2, B, A, C) 也要分解为三步： 第（3）.1步：move 1 form B to A; 第（3）.2步：move 2 form B to C; 第（3）.3步：move 1 form A to C; 箕恭琢峦蜀檬袖庸涌纶庐框烘毙靴再狭兜磁粗稀划揭贤栖襟阑经饶细见邵递推c,c++递推c,c++ * 5、看 move(2, A, C, B) 是说要将 2 只盘子从 A 搬至 B，但没有 C 是不行的，因为第（1）.1步就要将 1 盘从 A 移到 C，给 2 盘创造条件从 A 移至 B，然后再把 1 盘从 C 移至 B。看到这里就能明白借助 C 的含义了。因此，在构思搬移过程的参量时，要把 3 个柱