探秘汉诺塔学习教案.pptx

探秘汉诺塔探秘汉诺塔第一页，共13页。6464个金盘个金盘 印度教的主神梵天在创造世界时做了三根柱子印度教的主神梵天在创造世界时做了三根柱子(zh zi)(zh zi)，在其中一根柱子，在其中一根柱子(zh zi)(zh zi)上，从下到上地穿好了由大到小的上，从下到上地穿好了由大到小的6464个金盘，就是所谓的汉诺塔。个金盘，就是所谓的汉诺塔。不论白天黑夜，总有僧侣在按照法则移动这些金盘：一次只移动一个，小盘必须在大盘上面。僧侣们预言不论白天黑夜，总有僧侣在按照法则移动这些金盘：一次只移动一个，小盘必须在大盘上面。僧侣们预言(yyn)(yyn)，当所有的金盘都移动到第三根柱子上时，整个世界就会在一声霹雳中灰飞烟灭。，当所有的金盘都移动到第三根柱子上时，整个世界就会在一声霹雳中灰飞烟灭。第1页/共13页第二页，共13页。圆环1 圆环2圆环3圆环4圆环5圆环6圆环7圆环8所有(suyu)圆环移动到目标柱上 一次一环，大不压小 目标(mbio)柱过渡(gud)柱起始柱第2页/共13页第三页，共13页。同桌合作(hzu)一人移动一次,两个人轮流数填好任务单第3页/共13页第四页，共13页。小组合作一人移动一次,四个人轮流(lnli)数填好任务单第4页/共13页第五页，共13页。第5页/共13页第六页，共13页。没有大胆的猜测没有大胆的猜测(cic)(cic)，就做不出伟大的，就做不出伟大的发现发现 牛顿牛顿第6页/共13页第七页，共13页。第7页/共13页第八页，共13页。第8页/共13页第九页，共13页。过渡柱目标(mbio)柱第9页/共13页第十页，共13页。递归非递归第10页/共13页第十一页，共13页。环数最少移动步数第一步移动位置任务(rn wu)单1246531目标(mbio)柱3过渡(gud)柱目标柱过渡柱目标柱过渡柱目标柱过渡柱目标柱目标柱过渡柱过渡柱目标柱目标柱过渡柱目标柱过渡柱目标柱目标柱过渡柱过渡柱目标柱过渡柱目标柱目标柱过渡柱过渡柱目标柱过渡柱目标柱过渡柱过渡柱目标柱目标柱过渡柱过渡柱目标柱6331157=1+1+1=3+1+3=7+1+7=15+1+15=31+1+31第11页/共13页第十二页，共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页。