多柱汉诺塔算法

王守恩

我们设盘的个数为n，柱的根数为m，符合题意的最小挪动步数为s
譬如：m=5根柱，
          (n - w)×2^A - 1=S
          (1 - 0)×2^1 - 1=1
          (2 - 0)×2^1 - 1=3
          (3 - 0)×2^1 - 1=5
          (4 - 0)×2^1 - 1=7
          (5 - 2)×2^2 - 1=11
          (6 - 2)×2^2 - 1=15
          (7 - 2)×2^2 - 1=19
          (8 - 2)×2^2 - 1=23
          (9 - 2)×2^2 - 1=27
          (10 - 2)×2^2 - 1=31
          (11 - 6)×2^3 - 1=39
          (12 - 6)×2^3 - 1=47
          (13 - 6)×2^3 - 1=55
          (14 - 6)×2^3 - 1=63
          (15 - 6)×2^3 - 1=71
          (16 - 6)×2^3 - 1=79
          (17 - 6)×2^3 - 1=87
          (18 - 6)×2^3 - 1=95
          (19 - 6)×2^3 - 1=103
          (20 - 6)×2^3 - 1=111
          (21 - 13)×2^4 - 1=127
          (22 - 13)×2^4 - 1=143
          (23 - 13)×2^4 - 1=159
          (24 - 13)×2^4 - 1=175
          (25 - 13)×2^4 - 1=191
          (26 - 13)×2^4 - 1=207
          (27 - 13)×2^4 - 1=223
          (28 - 13)×2^4 - 1=239
          ………………
       答案本身没有问题，求助各位大神，对算式作化简。

王守恩

我们设盘的个数为n，柱的根数为m，符合题意的最小挪动步数为s
譬如：m=6根柱，
          (n - w)×2^A+1=S
          (1 - 1)×2^1+1=1
          (2 - 1)×2^1+1=3
          (3 - 1)×2^1+1=5
          (4 - 1)×2^1+1=7
          (5 - 1)×2^1+1=9
          (6 - 3)×2^2+1=13
          (7 - 3)×2^2+1=17
          (8 - 3)×2^2+1=21
          (9 - 3)×2^2+1=25
          (10 - 3)×2^2+1=29
          (11 - 3)×2^2+1=33
          (12 - 3)×2^2+1=37
          (13 - 3)×2^2+1=41
          (14 - 3)×2^2+1=45
          (15 - 3)×2^2+1=49
          (16 - 9)×2^3+1=57
          (17 - 9)×2^3+1=65
          (18 - 9)×2^3+1=73
          (19 - 9)×2^3+1=81
          (20 - 9)×2^3+1=89
          (21 - 9)×2^3+1=97
          (22 - 9)×2^3+1=105
          (23 - 9)×2^3+1=113
          (24 - 9)×2^3+1=121
          (25 - 9)×2^3+1=129
          (26 - 9)×2^3+1=137
          (27 - 9)×2^3+1=145
          (28 - 9)×2^3+1=153
          ………………
     答案本身没有问题，求助各位大神，对算式作化简。

王守恩

我们设盘的个数为n，柱的根数为m，符合题意的最小挪动步数为s
譬如：m=7根柱，
          (n - w)×2^A - 1=S
          (1 - 0)×2^1 - 1=1
          (2 - 0)×2^1 - 1=3
          (3 - 0)×2^1 - 1=5
          (4 - 0)×2^1 - 1=7
          (5 - 0)×2^1 - 1=9
          (6 - 0)×2^1 - 1=11
          (7 - 3)×2^2 - 1=15
          (8 - 3)×2^2 - 1=19
          (9 - 3)×2^2 - 1=23
          (10 - 3)×2^2 - 1=27
          (11 - 3)×2^2 - 1=31
          (12 - 3)×2^2 - 1=35
          (13 - 3)×2^2 - 1=39
          (14 - 3)×2^2 - 1=43
          (15 - 3)×2^2 - 1=47
          (16 - 3)×2^2 - 1=51
          (17 - 3)×2^2 - 1=55
          (18 - 3)×2^2 - 1=59
          (19 - 3)×2^2 - 1=63
          (20 - 3)×2^2 - 1=67
          (21 - 3)×2^2 - 1=71
          (22 - 12)×2^3 - 1=79
          (23 - 12)×2^3 - 1=87
          (24 - 12)×2^3 - 1=95
          (25 - 12)×2^3 - 1=103
          (26 - 12)×2^3 - 1=111
          (27 - 12)×2^3 - 1=119
          (28 - 12)×2^3 - 1=127   
          ………………
     答案本身没有问题，求助各位大神，对算式作化简。

王守恩

最后，我们还是想把m=3根柱的算式归纳到这里来。
设盘的个数为n，柱的根数为m，符合题意的最小挪动步数为s
譬如：m=3根柱，
          (n - w)×2^A - 1=S
          (1 - 0)×2^1 - 1=1
          (2 - 0)×2^1 - 1=3
          (3 - 1)×2^2 - 1=7
          (4 - 2)×2^3 - 1=15
          (5 - 3)×2^4 - 1=31
          (6 - 4)×2^5 - 1=63
          (7 - 5)×2^6 - 1=127
          (8 - 6)×2^7 - 1=255
          (9 - 7)×2^8 - 1=511
          ………………
       答案本身没有问题，求助各位大神，对前面的算式作化简。
本文漂亮的解决了多柱汉诺塔算法，用的是两个工具：二进制和杨辉三角。

王守恩

王守恩 发表于 2017-3-2 16:25
最后，我们还是想把m=3根柱的算式归纳到这里来。
设盘的个数为n，柱的根数为m，符合题意的最小挪动步数为s ...

四柱汉诺塔升级版问题:
有四个排成一行的柱子和n个大小不同的盘子，
每次可以将一个盘子移动到相邻的柱子上，但是大盘子不能放在小盘子上面。
请用最小的步数将n个盘子从第一个柱子全部移到第4个盘子。

这是 “数学研发论坛” 共同的财富！我先把题目改一下：
有四个排成一行的柱子和n个大小不同的盘子，
每次可以将一个盘子移动到相邻的柱子上，但是大盘子不能放在小盘子上面。
请用最小的步数将n个盘子从第一个柱子全部移出来。
这是 “数学研发论坛” 共同的财富！大家可有相关的资料提供？谢谢！

王守恩

王守恩 发表于 2020-1-27 14:58
四柱汉诺塔升级版问题:
有四个排成一行的柱子和n个大小不同的盘子，
每次可以将一个盘子移动到相邻的柱 ...

四柱汉诺塔升级版问题
有 4 个排成一行的柱和 n 个大小不同的盘，
每次可以将一个盘移动到相邻的柱上，但是大盘不能放在小盘上面。
请用最小的步数将 n 个盘从第 1 个柱全部移到第 4 个柱

n=01，000+00+0+000+00+00+00+000+3=3
n=02，000+02+0+000+01+02+02+000+3=10
n=03，003+02+0+003+01+02+02+003+3=19
n=04，003+08+2+003+01+02+02+010+3=34
n=05，010+08+2+010+01+02+02+019+3=57
n=06，019+08+0+019+04+08+08+019+3=88
n=07，019+26+2+019+04+08+08+034+3=123
n=08，034+26+2+034+04+08+08+057+3=176
n=09，057+26+2+057+04+08+08+088+3=253
n=10，057+80+8+057+04+08+08+123+3=348
n=11，088+80+2+088+13+26+26+123+3=449
n=12，123+80+2+123+13+26+26+176+3=572

每种移法可以用9个数字来表示
第9个数字(3)表示移动最大盘所需步数
第1,4,8个数字表示利用4根柱移动的步数
第2,3,5,6,7个数字表示利用3根柱移动的步数
特别地，第3个数字表示从第3个柱移回到第1个柱
第1个数字与第4个数字相同，第7个数字与第8个数字相同


每串数从左往右是一种移法，从右(除3)往左是另一种移法，

上面算式中的数字说明如下
003=利用4根柱移动1个盘所需的步数
010=利用4根柱移动2个盘所需的步数
019=利用4根柱移动3个盘所需的步数
034=利用4根柱移动4个盘所需的步数
057=利用4根柱移动5个盘所需的步数
088=利用4根柱移动6个盘所需的步数
123=利用4根柱移动7个盘所需的步数
176=利用4根柱移动8个盘所需的步数

02=利用3根柱移动1个盘所需的步数
08=利用3根柱移动2个盘所需的步数
26=利用3根柱移动3个盘所需的步数
80=利用3根柱移动4个盘所需的步数

01=利用3根柱移动1个盘(1个柱位)所需的步数
04=利用3根柱移动2个盘(1个柱位)所需的步数
13=利用3根柱移动3个盘(1个柱位)所需的步数

还能有比这更省的步数吗？


补充内容 (2020-2-8 09:40):
错啦！别跟我走！《[擂台] 四柱汉诺塔升级版》有正确答案。

王守恩

王守恩 发表于 2017-3-2 09:58
我们设盘的个数为n，柱的根数为m，符合题意的最小挪动步数为s
譬如：m=4根柱，
          (n - w)×2^A+1 ...

给出18#的通项公式。虽然丑，但是是自己的。欢迎批评！

\(\D a(n)=n*2^{\big\lbrack\sqrt{2n}-1\big\rbrack}-\sum_{k=1}^{\big\lbrack\sqrt{2n}\big\rbrack}\frac{k!}{2^{3-k}(k-2)!}\)
         
我们设盘的个数为n，柱的根数为m，符合题意的最小挪动步数为s
譬如：m=4根柱，
          (n - w)×2^A+1=S
          (1 - 1)×2^1+1=1
          (2 - 1)×2^1+1=3
          (3 - 1)×2^1+1=5
          (4 - 2)×2^2+1=9
          (5 - 2)×2^2+1=13
          (6 - 2)×2^2+1=17
          (7 - 4)×2^3+1=25
          (8 - 4)×2^3+1=33
          (9 - 4)×2^3+1=41
          (10 - 4)×2^3+1=49
          (11 - 7)×2^4+1=65
          (12 - 7)×2^4+1=81
          (13 - 7)×2^4+1=97
          (14 - 7)×2^4+1=113
          (15 - 7)×2^4+1=129
          (16 - 11)×2^5+1=161
          (17 - 11)×2^5+1=193
          (18 - 11)×2^5+1=225
          (19 - 11)×2^5+1=257
          (20 - 11)×2^5+1=289
          (21 - 11)×2^5+1=321
          (22 - 16)×2^6+1=385
          (23 - 16)×2^6+1=449
          (24 - 16)×2^6+1=513
          (25 - 16)×2^6+1=577
          (26 - 16)×2^6+1=641
          (27 - 16)×2^6+1=705
          (28 - 16)×2^6+1=769
          ………………

王守恩

王守恩 发表于 2020-1-27 14:58
四柱汉诺塔升级版问题:
有四个排成一行的柱子和n个大小不同的盘子，
每次可以将一个盘子移动到相邻的柱 ...

我们来做这样一道题。
有 4 个排成一行的柱，第 1 个柱上有 n 个大小不同的盘，
每次可以将一个盘移动到相邻的柱上，但是大盘不能放在小盘上面。
请用最小的步数将 n 个盘从第 1 个柱上全部移出来。
a(n)=1, 3, 6, 11, 19, 28, 43, 61, 84,...........