本帖最后由 王守恩 于 2017-3-2 12:41 编辑
我们设盘的个数为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
………………
答案本身没有问题，求助各位大神，对算式作化简。
本帖最后由 王守恩 于 2017-3-2 19:51 编辑
最后，我们还是想把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-2-6 18:29 编辑
王守恩 发表于 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):
错啦！别跟我走！《[擂台] 四柱汉诺塔升级版》有正确答案。
本帖最后由 王守恩 于 2020-2-8 09:44 编辑
王守恩 发表于 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-2-11 10:06 编辑
王守恩 发表于 2020-1-27 14:58
四柱汉诺塔升级版问题:
有四个排成一行的柱子和n个大小不同的盘子，
每次可以将一个盘子移动到相邻的柱 ...
我们来做这样一道题。
有 4 个排成一行的柱，第 1 个柱上有 n 个大小不同的盘，
每次可以将一个盘移动到相邻的柱上，但是大盘不能放在小盘上面。
请用最小的步数将 n 个盘从第 1 个柱上全部移出来。
a(n)=1, 3, 6, 11, 19, 28, 43, 61, 84,...........