javascript解汉诺塔问题-白红宇

javascript解汉诺塔问题

阅读量：7120 次

发布时间：2019-06-28

本文共 5427 字，大约阅读时间需要 18 分钟。

传说某间寺院有三根柱子，在创世之初，第一根柱子串有64个金盘，盘的尺寸由下到上一个比一个小。寺院里的僧侣依照一个古老的预言，每天移动一个盘；大盘不能叠在小盘上面，预言说盘子全部移动到到第三根柱子时，世界就会灭亡。

最少移动步数是随着盘子的个数呈指数增长（2^n-1）的。对指数增长有概念的同学应该能够看出移动64个盘子所需的步数是个天文数字，即使僧侣们每秒可完成一个盘子的移动，也需要5846亿年才能完成，整个宇宙现在也不过137亿年。这个世界灭亡传说的本意大概是在祝福世界不要灭亡吧。

在《猩球崛起》故事中就是用同样的问题来给猩猩们测智商，用了4个盘子。

四个盘子最少需要挪动2^4-1=15步，这只猩猩最快15步就完成了，难怪科学家们要大吃一惊了。

下面是一个有7个盘子的儿童玩具，最少需要2^7-1=127步完成。

最后，用javascript编制一个递归算法，来做一做这个儿童游戏吧：

var hanoi = function(k,src,tmp,dst){

if(k>0){

hanoi(k-1,src,dst,tmp);//把上面k-1个盘子从src通过dst搬到tmp

iCount+=1;

put("iCount = " + iCount + " move disc " + k + " from " + src + " to " + dst);//把最大的盘子从src搬到dst

hanoi(k-1,tmp,src,dst);//把k-1个盘子从tmp通过src搬到dst

}

}

var iCount=0;//计数

var n = 7; //盘子个数

pt("Math.pow(2,"+n+")-1");

hanoi(n,'A','B','C');

put("~~~~~~~~~game over~~~~~~~~~~~~~~~");

调试信息:

Math.pow(2,7)-1 127

iCount = 1 move disc 1 from A to C

iCount = 2 move disc 2 from A to B

iCount = 3 move disc 1 from C to B

iCount = 4 move disc 3 from A to C

iCount = 5 move disc 1 from B to A

iCount = 6 move disc 2 from B to C

iCount = 7 move disc 1 from A to C

iCount = 8 move disc 4 from A to B

iCount = 9 move disc 1 from C to B

iCount = 10 move disc 2 from C to A

iCount = 11 move disc 1 from B to A

iCount = 12 move disc 3 from C to B

iCount = 13 move disc 1 from A to C

iCount = 14 move disc 2 from A to B

iCount = 15 move disc 1 from C to B

iCount = 16 move disc 5 from A to C

iCount = 17 move disc 1 from B to A

iCount = 18 move disc 2 from B to C

iCount = 19 move disc 1 from A to C

iCount = 20 move disc 3 from B to A

iCount = 21 move disc 1 from C to B

iCount = 22 move disc 2 from C to A

iCount = 23 move disc 1 from B to A

iCount = 24 move disc 4 from B to C

iCount = 25 move disc 1 from A to C

iCount = 26 move disc 2 from A to B

iCount = 27 move disc 1 from C to B

iCount = 28 move disc 3 from A to C

iCount = 29 move disc 1 from B to A

iCount = 30 move disc 2 from B to C

iCount = 31 move disc 1 from A to C

iCount = 32 move disc 6 from A to B

iCount = 33 move disc 1 from C to B

iCount = 34 move disc 2 from C to A

iCount = 35 move disc 1 from B to A

iCount = 36 move disc 3 from C to B

iCount = 37 move disc 1 from A to C

iCount = 38 move disc 2 from A to B

iCount = 39 move disc 1 from C to B

iCount = 40 move disc 4 from C to A

iCount = 41 move disc 1 from B to A

iCount = 42 move disc 2 from B to C

iCount = 43 move disc 1 from A to C

iCount = 44 move disc 3 from B to A

iCount = 45 move disc 1 from C to B

iCount = 46 move disc 2 from C to A

iCount = 47 move disc 1 from B to A

iCount = 48 move disc 5 from C to B

iCount = 49 move disc 1 from A to C

iCount = 50 move disc 2 from A to B

iCount = 51 move disc 1 from C to B

iCount = 52 move disc 3 from A to C

iCount = 53 move disc 1 from B to A

iCount = 54 move disc 2 from B to C

iCount = 55 move disc 1 from A to C

iCount = 56 move disc 4 from A to B

iCount = 57 move disc 1 from C to B

iCount = 58 move disc 2 from C to A

iCount = 59 move disc 1 from B to A

iCount = 60 move disc 3 from C to B

iCount = 61 move disc 1 from A to C

iCount = 62 move disc 2 from A to B

iCount = 63 move disc 1 from C to B

iCount = 64 move disc 7 from A to C

iCount = 65 move disc 1 from B to A

iCount = 66 move disc 2 from B to C

iCount = 67 move disc 1 from A to C

iCount = 68 move disc 3 from B to A

iCount = 69 move disc 1 from C to B

iCount = 70 move disc 2 from C to A

iCount = 71 move disc 1 from B to A

iCount = 72 move disc 4 from B to C

iCount = 73 move disc 1 from A to C

iCount = 74 move disc 2 from A to B

iCount = 75 move disc 1 from C to B

iCount = 76 move disc 3 from A to C

iCount = 77 move disc 1 from B to A

iCount = 78 move disc 2 from B to C

iCount = 79 move disc 1 from A to C

iCount = 80 move disc 5 from B to A

iCount = 81 move disc 1 from C to B

iCount = 82 move disc 2 from C to A

iCount = 83 move disc 1 from B to A

iCount = 84 move disc 3 from C to B

iCount = 85 move disc 1 from A to C

iCount = 86 move disc 2 from A to B

iCount = 87 move disc 1 from C to B

iCount = 88 move disc 4 from C to A

iCount = 89 move disc 1 from B to A

iCount = 90 move disc 2 from B to C

iCount = 91 move disc 1 from A to C

iCount = 92 move disc 3 from B to A

iCount = 93 move disc 1 from C to B

iCount = 94 move disc 2 from C to A

iCount = 95 move disc 1 from B to A

iCount = 96 move disc 6 from B to C

iCount = 97 move disc 1 from A to C

iCount = 98 move disc 2 from A to B

iCount = 99 move disc 1 from C to B

iCount = 100 move disc 3 from A to C

iCount = 101 move disc 1 from B to A

iCount = 102 move disc 2 from B to C

iCount = 103 move disc 1 from A to C

iCount = 104 move disc 4 from A to B

iCount = 105 move disc 1 from C to B

iCount = 106 move disc 2 from C to A

iCount = 107 move disc 1 from B to A

iCount = 108 move disc 3 from C to B

iCount = 109 move disc 1 from A to C

iCount = 110 move disc 2 from A to B

iCount = 111 move disc 1 from C to B

iCount = 112 move disc 5 from A to C

iCount = 113 move disc 1 from B to A

iCount = 114 move disc 2 from B to C

iCount = 115 move disc 1 from A to C

iCount = 116 move disc 3 from B to A

iCount = 117 move disc 1 from C to B

iCount = 118 move disc 2 from C to A

iCount = 119 move disc 1 from B to A

iCount = 120 move disc 4 from B to C

iCount = 121 move disc 1 from A to C

iCount = 122 move disc 2 from A to B

iCount = 123 move disc 1 from C to B

iCount = 124 move disc 3 from A to C

iCount = 125 move disc 1 from B to A

iCount = 126 move disc 2 from B to C

iCount = 127 move disc 1 from A to C

~~~~~~~~~game over~~~~~~~~~~~~~~~

转载地址：http://ytnel.baihongyu.com/

你可能感兴趣的文章

有了 Docker，用 JavaScript 框架开发的 Web 站点也能很好地支持网络爬虫的内容抓取...

查看>>

以太坊是什么鬼？！媲美比特币的加密币大揭秘

查看>>

IBM推出跨境支付区块链网络，企业级区块链技术进一步升级

【Solidity】1.一个Solidity源文件的布局 - 深入理解Solidity

T-SQL Enhancement in SQL Server 2005[下篇]

Salesforce即将推出Einstein人工智能CRM平台

查看>>

网易严选App感受Weex开发

查看>>

趋势发布SecureCloud云安全技术架构

查看>>

3PAR副总裁谈09年存储虚拟化

查看>>