生活随笔
收集整理的這篇文章主要介紹了
汉诺塔非递归算法
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
這兩天講《Web程序設(shè)計(jì)》，用JavaScript寫(xiě)了個(gè)漢諾塔的非遞歸算法，覺(jué)得有點(diǎn)意思，放在這里吧！
傳統(tǒng)的遞歸算法：?
<html?xmlns="http://www.w3.org/1999/xhtml">? <head>? <meta?http-equiv="Content-Type"?content="text/html;?charset=utf-8"?/>? <title>Hanoi?Tower?(Recursive?algorithm)?-?漢諾塔（遞歸算法）</title>? <style?type="text/css">? i?{ ?????color:?#0000ff; ?} ?P?{ ?????text-align:?center; ?} ? </style>? <script?type="text/javascript">? var?step=0; ? function?MoveOnePlate(n,?loca1,?loca2) ?{ ? ????document.write("第"?+?++step?+?"步：移動(dòng)第<i>"?+?n?+?"</i>個(gè)盤(pán)子，從"?+?loca1?+?"到"?+?loca2?+?"<br?/>"); ? } ??function?MovePlates(n,?s,?m,?d) ?{ ? ????if(n==1) ? ??????MoveOnePlate(n,?s,?d); ?????else ?????{ ?????????MovePlates(n-1,?s,?d,?m); ?????????MoveOnePlate(n,?s,?d); ?????????MovePlates(n-1,?m,?s,?d); ?????} ?} ? </script>? </head>? ? <body>? <p>Hanoi?Tower?(Recursive?algorithm)?-?漢諾塔（遞歸算法）<br?/>Mengliao?Software?Studio(Baiyu)?-?夢(mèng)遼軟件工作室（白宇）<br?/>? Copyright?2011,?All?right?reserved.?-?版權(quán)所有(C)?2011<br?/>2011.03.31</p>? <script?type="text/javascript">? ????n=parseInt(prompt("請(qǐng)輸入盤(pán)子的數(shù)量：",?3),?10); ? ????if?(isNaN(n)?||?n<1?||?n>16) ? ????{ ?????????alert("請(qǐng)輸入介于1到16的自然數(shù)！"); ?????????location.reload(); ?????} ?????else ?????{ ? ????????document.write("共"?+?n?+?"個(gè)盤(pán)子，需移動(dòng)"?+?(Math.pow(2,?n)-1)?+?"步：<br?/><br?/>"); ? ????????MovePlates(n,?"<i>源點(diǎn)</i>",?"<i>臨時(shí)</i>",?"<i>目標(biāo)</i>"); ? ????} ? </script>? </body>? </html>? 這個(gè)遞歸算法就不詳細(xì)說(shuō)了，核心代碼只有5、6行。
下面是非遞歸算法：?
<html?xmlns="http://www.w3.org/1999/xhtml">? <head>? <meta?http-equiv="Content-Type"?content="text/html;?charset=utf-8"?/>? <title>Hanoi?Tower?(Non-recursive?algorithm)?-?漢諾塔（非遞歸算法）</title>? <style?type="text/css">? i?{ ?????color:?#ff0000; ?} ?p?{ ?????text-align:?center; ?} ? </style>? <!-- ?漢諾塔非遞歸算法： ?(1)、若問(wèn)題規(guī)模n為偶數(shù)，按順時(shí)針?lè)较蛞来螖[放s,?m,?d為環(huán)，若n為奇數(shù)，則為s,?d,?m； ?(2)、將盤(pán)子由小到大逐個(gè)編號(hào)并放置在s上，即最小的盤(pán)子編號(hào)為1，放在最上面； ?(3)、按順時(shí)針?lè)较虬丫幪?hào)為1的盤(pán)子從當(dāng)前的位置移動(dòng)到下一位置； ?(4)、把另外兩個(gè)位置（即除去1號(hào)盤(pán)子所在的位置）中非空的那個(gè)上的一個(gè)圓盤(pán)移到空的位置上，如果另外兩個(gè)位置都非空，則移動(dòng)編號(hào)較小的那一個(gè)； ?(5)、重復(fù)進(jìn)行(3)和(4)，直到移動(dòng)的次數(shù)等于2^n-1。 ? -->? <script?type="text/javascript">? var?step=0; ? function?MoveOnePlate(n,?loca1,?loca2) ?{ ? ????document.write("第"?+?++step?+?"步：移動(dòng)第<i>"?+?n?+?"</i>個(gè)盤(pán)子，從"?+?loca1?+?"到"?+?loca2?+?"<br?/>"); ? } ??function?MovePlates(n,?s,?m,?d) ?{ ?????//定義位置 ? ????var?loop=new?Array(3); ? ????loop[0]=new?Array(n); ?????loop[1]=new?Array(n); ?????loop[2]=new?Array(n); ?????//定義位置描述字符串?dāng)?shù)組(n為偶數(shù)的情況) ? ????var?loca=new?Array(s,?m,?d); ? ????if?(n%2!=0)?//n為奇數(shù)的情況 ?????{ ?????????loca[1]=d; ?????????loca[2]=m; ?????} ?????//初始化源位置上的盤(pán)子 ? ????for(var?i=0;?i<n;?i++) ? ????????loop[0][i]=n-i; ?????//記錄各個(gè)位置上盤(pán)子的數(shù)量 ? ????var?loopLen=new?Array(n,?0,?0); ? ????var?count=Math.pow(2,?n)-1;?//移動(dòng)次數(shù)，即循環(huán)退出條件 ? ????var?firstPlate=0;?//1號(hào)盤(pán)子的位置 ? ????do ?????{ ?????????//將1號(hào)盤(pán)子順時(shí)針移動(dòng)到后1個(gè)位置 ?????????MoveOnePlate(1,?loca[firstPlate],?loca[(firstPlate+1)%3]);?//顯示移動(dòng)過(guò)程 ?????????loop[(firstPlate+1)%3][loopLen[(firstPlate+1)%3]]=1;?//移動(dòng) ?????????loopLen[firstPlate]--;?//修改1號(hào)盤(pán)子舊位置上盤(pán)子的數(shù)量 ? ????????firstPlate=(firstPlate+1)%3;?//修改1號(hào)盤(pán)子的位置 ? ????????loopLen[firstPlate]++;?//修改1號(hào)盤(pán)子新位置上盤(pán)子的數(shù)量 ?????????count--;?//記錄移動(dòng)次數(shù) ?????????//移動(dòng)另外的兩個(gè)位置上的盤(pán)子 ?????????if(count!=0)?//避免最后一次移動(dòng)后仍然移動(dòng)而導(dǎo)致錯(cuò)誤 ?????????{ ?????????????//確定另外兩個(gè)位置如何移動(dòng) ?????????????if?(loopLen[(firstPlate+1)%3]==0?||?loopLen[(firstPlate+2)%3]!=0?&& ? ????????????????loop[(firstPlate+2)%3][loopLen[(firstPlate+2)%3]-1]?<?loop[(firstPlate+1)%3][loopLen[(firstPlate+1)%3]-1]?) ? ????????????{?//1號(hào)盤(pán)子的后第1個(gè)位置為空，或者無(wú)空位置且1號(hào)盤(pán)子后第2個(gè)位置編號(hào)較小，此時(shí)將1號(hào)盤(pán)子后第2個(gè)位置的盤(pán)子移動(dòng)到1號(hào)盤(pán)子后第1個(gè)位置上 ?????????????????MoveOnePlate(loop[(firstPlate+2)%3][loopLen[(firstPlate+2)%3]-1],?loca[(firstPlate+2)%3],?loca[(firstPlate+1)%3]);?//顯示移動(dòng)過(guò)程 ?????????????????loop[(firstPlate+1)%3][loopLen[(firstPlate+1)%3]]=loop[(firstPlate+2)%3][loopLen[(firstPlate+2)%3]-1];?//移動(dòng) ?????????????????loopLen[(firstPlate+2)%3]--;?//修改該盤(pán)子舊位置上盤(pán)子的數(shù)量 ?????????????????loopLen[(firstPlate+1)%3]++;?//修改該盤(pán)子新位置上盤(pán)子的數(shù)量 ?????????????} ?????????????else ?????????????{?//1號(hào)盤(pán)子的后第2個(gè)位置為空，或者無(wú)空位置且1號(hào)盤(pán)子后第1個(gè)位置編號(hào)較小，此時(shí)將1號(hào)盤(pán)子后第1個(gè)位置的盤(pán)子移動(dòng)到1號(hào)盤(pán)子后第2個(gè)位置上 ?????????????????MoveOnePlate(loop[(firstPlate+1)%3][loopLen[(firstPlate+1)%3]-1],?loca[(firstPlate+1)%3],?loca[(firstPlate+2)%3]);?//顯示移動(dòng)過(guò)程 ?????????????????loop[(firstPlate+2)%3][loopLen[(firstPlate+2)%3]]=loop[(firstPlate+1)%3][loopLen[(firstPlate+1)%3]-1];?//移動(dòng) ?????????????????loopLen[(firstPlate+1)%3]--;?//修改該盤(pán)子舊位置上盤(pán)子的數(shù)量 ?????????????????loopLen[(firstPlate+2)%3]++;?//修改該盤(pán)子新位置上盤(pán)子的數(shù)量 ?????????????} ?????????????count--;?//記錄移動(dòng)次數(shù) ?????????} ?????}?while(count!=0) ?} ? </script>? </head>? ? <body>? <p>Hanoi?Tower?(Non-recursive?algorithm)?-?漢諾塔（非遞歸算法）<br?/>Mengliao?Software?Studio(Baiyu)?-?夢(mèng)遼軟件工作室（白宇）<br?/>? Copyright?2011,?All?right?reserved.?-?版權(quán)所有(C)?2011<br?/>2011.03.31</p>? <script?type="text/javascript">? ????n=parseInt(prompt("請(qǐng)輸入盤(pán)子的數(shù)量：",?3),?10); ? ????if?(isNaN(n)?||?n<1?||?n>16) ? ????{ ?????????alert("請(qǐng)輸入介于1到16的自然數(shù)！"); ?????????location.reload(); ?????} ?????else ?????{ ? ????????document.write("共"?+?n?+?"個(gè)盤(pán)子，需移動(dòng)"?+?(Math.pow(2,?n)-1)?+?"步：<br?/><br?/>"); ? ????????MovePlates(n,?"<i>源點(diǎn)</i>",?"<i>臨時(shí)</i>",?"<i>目標(biāo)</i>"); ? ????} ? </script>? </body>? </html>? 非遞歸算法略微復(fù)雜些，代碼里面有詳細(xì)的注釋和說(shuō)明。
這里還有一個(gè)使用JavaScript數(shù)組對(duì)象的push()和pop()方法的非遞歸版本，可以簡(jiǎn)化程序，道理是一樣的。
非遞歸算法版本2：?
<html?xmlns="http://www.w3.org/1999/xhtml">? <head>? ????<meta?http-equiv="Content-Type"?content="text/html;?charset=utf-8"?/>? ????<title>Hanoi?Tower?(Non-recursive?algorithm,?Version?2)?-?漢諾塔（非遞歸算法，版本2）</title>? ????<style?type="text/css">? ????????i ?????????{ ?????????????color:?#ff0080; ?????????} ?????????p ?????????{ ?????????????text-align:?center; ?????????} ? ????</style>? ????<!-- ?漢諾塔非遞歸算法： ?(1)、若問(wèn)題規(guī)模n為偶數(shù)，按順時(shí)針?lè)较蛞来螖[放s,?m,?d為環(huán)，若n為奇數(shù)，則為s,?d,?m； ?(2)、將盤(pán)子由小到大逐個(gè)編號(hào)并放置在s上，即最小的盤(pán)子編號(hào)為1，放在最上面； ?(3)、按順時(shí)針?lè)较虬丫幪?hào)為1的盤(pán)子從當(dāng)前的位置移動(dòng)到下一位置； ?(4)、把另外兩個(gè)位置（即除去1號(hào)盤(pán)子所在的位置）中非空的那個(gè)上的一個(gè)圓盤(pán)移到空的位置上，如果另外兩個(gè)位置都非空，則移動(dòng)編號(hào)較小的那一個(gè)； ?(5)、重復(fù)進(jìn)行(3)和(4)，直到移動(dòng)的次數(shù)等于2^n-1。 ? -->? ????<script?type="text/javascript">? ????????var?step?=?0; ? ????????function?MoveOnePlate(n,?loca1,?loca2)?{ ? ????????????document.write("第"?+?++step?+?"步：移動(dòng)第<i>"?+?n?+?"</i>個(gè)盤(pán)子，從"?+?loca1?+?"到"?+?loca2?+?"<br?/>"); ? ????????} ??????????function?MovePlates(n,?s,?m,?d)?{ ?????????????//定義位置 ? ????????????var?loop?=?new?Array([],?[],?[]); ? ????????????//定義位置描述字符串?dāng)?shù)組(n為偶數(shù)的情況) ? ????????????var?loca?=?new?Array(s,?m,?d); ? ????????????if?(n?%?2?!=?0)?//n為奇數(shù)的情況 ?????????????{ ?????????????????loca[1]?=?d; ?????????????????loca[2]?=?m; ?????????????} ?????????????//初始化源位置上的盤(pán)子 ? ????????????for?(var?i?=?0;?i?<?n;?i++) ? ????????????????loop[0].push(n?-?i); ? ????????????var?count?=?Math.pow(2,?n)?-?1;?//移動(dòng)次數(shù)，即循環(huán)退出條件 ? ????????????var?firstPlate?=?0;?//1號(hào)盤(pán)子的位置 ? ????????????do?{ ?????????????????//將1號(hào)盤(pán)子順時(shí)針移動(dòng)到后1個(gè)位置 ?????????????????MoveOnePlate(1,?loca[firstPlate],?loca[(firstPlate?+?1)?%?3]);?//顯示移動(dòng)過(guò)程 ?????????????????loop[(firstPlate?+?1)?%?3].push(loop[firstPlate].pop());?//從舊位置移動(dòng)到新位置 ? ????????????????firstPlate?=?(firstPlate?+?1)?%?3;?//修改1號(hào)盤(pán)子的位置 ? ????????????????count--;?//記錄移動(dòng)次數(shù) ?????????????????//移動(dòng)另外的兩個(gè)位置上的盤(pán)子 ?????????????????if?(count?!=?0)?//避免最后一次移動(dòng)后仍然移動(dòng)而導(dǎo)致錯(cuò)誤 ?????????????????{ ?????????????????????//確定另外兩個(gè)位置如何移動(dòng) ? ????????????????????if?(loop[(firstPlate?+?1)?%?3].length?==?0?||?loop[(firstPlate?+?2)?%?3].length?!=?0?&&?loop[(firstPlate?+?2)?%?3][loop[(firstPlate?+?2)?%?3].length?-?1]?<?loop[(firstPlate?+?1)?%?3][loop[(firstPlate?+?1)?%?3].length?-?1])?{ ? ????????????????????????//1號(hào)盤(pán)子的后第1個(gè)位置為空，或者無(wú)空位置且1號(hào)盤(pán)子后第2個(gè)位置編號(hào)較小，此時(shí)將1號(hào)盤(pán)子后第2個(gè)位置的盤(pán)子移動(dòng)到1號(hào)盤(pán)子后第1個(gè)位置上 ?????????????????????????MoveOnePlate(loop[(firstPlate?+?2)?%?3][loop[(firstPlate?+?2)?%?3].length?-?1],?loca[(firstPlate?+?2)?%?3],?loca[(firstPlate?+?1)?%?3]);?//顯示移動(dòng)過(guò)程 ?????????????????????????loop[(firstPlate?+?1)?%?3].push(loop[(firstPlate?+?2)?%?3].pop());?//從舊位置移動(dòng)到新位置 ?????????????????????} ?????????????????????else?{ ?????????????????????????//1號(hào)盤(pán)子的后第2個(gè)位置為空，或者無(wú)空位置且1號(hào)盤(pán)子后第1個(gè)位置編號(hào)較小，此時(shí)將1號(hào)盤(pán)子后第1個(gè)位置的盤(pán)子移動(dòng)到1號(hào)盤(pán)子后第2個(gè)位置上 ?????????????????????????MoveOnePlate(loop[(firstPlate?+?1)?%?3][loop[(firstPlate?+?1)?%?3].length?-?1],?loca[(firstPlate?+?1)?%?3],?loca[(firstPlate?+?2)?%?3]);?//顯示移動(dòng)過(guò)程 ?????????????????????????loop[(firstPlate?+?2)?%?3].push(loop[(firstPlate?+?1)?%?3].pop());?//從舊位置移動(dòng)到新位置 ?????????????????????} ?????????????????????count--;?//記錄移動(dòng)次數(shù) ?????????????????} ?????????????}?while?(count?!=?0) ?????????} ? ????</script>? </head>? <body>? ????<p>? ????????Hanoi?Tower?(Non-recursive?algorithm,?Version?2)?-?漢諾塔（非遞歸算法，版本2）<br?/>? ????????Mengliao?Software?Studio(Baiyu)?-?夢(mèng)遼軟件工作室（白宇）<br?/>? ????????Copyright?2011,?All?right?reserved.?-?版權(quán)所有(C)?2011<br?/>? ????????2011.04.04</p>? ????<script?type="text/javascript">? ????????n?=?parseInt(prompt("請(qǐng)輸入盤(pán)子的數(shù)量：",?3),?10); ? ????????if?(isNaN(n)?||?n?<?1?||?n?>?16)?{ ? ????????????alert("請(qǐng)輸入介于1到16的自然數(shù)！"); ?????????????location.reload(); ?????????} ?????????else?{ ? ????????????document.write("共"?+?n?+?"個(gè)盤(pán)子，需移動(dòng)"?+?(Math.pow(2,?n)?-?1)?+?"步：<br?/><br?/>"); ? ????????????MovePlates(n,?"<i>源點(diǎn)</i>",?"<i>臨時(shí)</i>",?"<i>目標(biāo)</i>"); ? ????????} ? ????</script>? </body>? </html>? 這里是三個(gè)算法網(wǎng)頁(yè)源文件的連接：
http://mengliao.blog.51cto.com/attachment/201104/876134_1301907387.rar
本文轉(zhuǎn)自 BlackAlpha 51CTO博客，原文鏈接：http://blog.51cto.com/mengliao/534053，如需轉(zhuǎn)載請(qǐng)自行聯(lián)系原作者
總結(jié)
以上是生活随笔為你收集整理的汉诺塔非递归算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
