探秘汉诺塔学习.pptx

《探秘汉诺塔学习.pptx》由会员分享，可在线阅读，更多相关《探秘汉诺塔学习.pptx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6464个金盘个金盘 印度教的主神梵天在创造世界时做了三根柱子，在其中一根柱子上，从下到上地穿好了由大到小的64个金盘，就是所谓的汉诺塔。不论白天黑夜，总有僧侣在按照法则移动这些金盘：一次只移动一个，小盘必须在大盘上面。僧侣们预言，当所有的金盘都移动到第三根柱子上时，整个世界就会在一声霹雳中灰飞烟灭。第1页/共13页圆环1 圆环2圆环3圆环4圆环5圆环6圆环7圆环8所有圆环移动到目标柱上 一次一环，大不压小 目标柱过渡柱起始柱第2页/共13页 同桌合作一人移动一次,两个人轮流数填好任务单第3页/共13页 小组合作一人移动一次,四个人轮流数填好任务单第4页/共13页第5页/共13页 没有大胆的猜

2、测，就做不出伟大的发现 牛顿第6页/共13页第7页/共13页第8页/共13页过渡柱目标柱第9页/共13页递归非递归第10页/共13页环数最少移动步数第一步移动位置任务单1246531目标柱3过渡柱目标柱过渡柱目标柱过渡柱目标柱过渡柱目标柱目标柱过渡柱过渡柱目标柱目标柱过渡柱目标柱过渡柱目标柱目标柱过渡柱过渡柱目标柱过渡柱目标柱目标柱过渡柱过渡柱目标柱过渡柱目标柱过渡柱过渡柱目标柱目标柱过渡柱过渡柱目标柱6331157=1+1+1=3+1+3=7+1+7=15+1+15=31+1+31第11页/共13页递归算法递归算法移出1环：1移出2环：1+1+1=3移出3环：3+1+3=7移出4环：7+1+7=15移出5环：15+1+15=31移出6环：31+1+31=63移出7环：63+1+63=127移出8环：127+1+127=255非递归算法非递归算法移出1环：21-1=1移出2环：22-1=1移出3环：23-1=7移出4环：24-1=15移出5环：25-1=31移出6环：26-1=63移出7环：27-1=127移出8环：28-1=255第12页/共13页感谢您的观看。第13页/共13页