VJ 1432：

汉诺塔。塔有n根柱子，有m个圆盘按顺序（大在下，小在上）套在第1个柱子上，算出将第1个柱子上的m个圆盘移动到第n根柱子至少要多少次。（1次移1盘，大的必须在小的下面，每次移动柱子中最上方的盘子）。求已知m和n后求解的最小步數。（答案取181818181818的模）

这道题答案很奇怪。网上所有贴出来ac的程序【据说包括标程】run：
5 10
答案都是35.

但似乎：
5 10
应该为
31；
[见UVA http://online-judge.uva.es/p/v104/10444.html]
---
6 13
应该为
41

我精神上a了~基本上上確認AC的程序是錯誤的。AC的題解這麼說：

n柱Hanoi Tower问题，由于nm都很大，所以不可能用DP来解决，只能通过n柱Hanoi Tower的有规律数列来计算。该数列是由2^0-2^(m-1)组成，第i个数字有1+(i-1)*(n-3)个。数列之和就是在n柱汉诺塔上移动m个 盘子所需要的最少次数。

EN維基上這麼說：

Four Pegs or Beyond

Though it is not known exactly how many moves must be made, there are some asymptotic results. There is also a "presumed-optimal solution" given by the Frame-Stewart algorithm. The related open Frame-Stewart conjecture claims that the Frame-Stewart algorithm always gives an optimal solution. The optimality of the Frame-Stewart algorithm has been computationally verified for up to 30 disks. ^[3]

For other variants of the four-peg Tower of Hanoi problem, see Paul Stockmeyer's survey paper. ^[4]

 Frame-Stewart algorithm

The Frame-Stewart algorithm, giving a presumably-optimal solution for four (or even more) pegs, is described below:

• Let n be the number of disks.
• Let r be the number of pegs.
• Define T(n,r) to be the number of moves required to transfer n disks using r pegs

The algorithm can be described recursively:

1. For some k, , transfer the top k disks to a single other peg, taking T(k,r) moves.
2. Without disturbing the peg that now contains the top k disks, transfer the remaining n − k disks to the destination peg, using only the remaining r − 1 pegs, taking T(n − k,r − 1) moves.
3. Finally, transfer the top k disks to the destination peg, taking T(k,r) moves.

The entire process takes 2T(k,r) + T(n − k,r − 1) moves. Therefore, the count k should be picked for which this quantity is minimum.
This algorithm (with the above choice for k) is presumed to be optimal, and no counterexamples are known.

很明顯我的結果是：

用算法求出的所需次数表：
横行表示盘的数目，竖列表示柱子个数，表内内容为所需步数。
1    2    3    4    5    6    7    8    9    10

1    3    7    15    31    63    127    255    511    1023    【3个柱子】
1    3    5    9    13    17    25    33    41    49
1    3    5    7    11    15    19    23    27    31
1    3    5    7    9    13    17    21    25    29
1    3    5    7    9    11    15    19    23    27
1    3    5    7    9    11    13    17    21    25
1    3    5    7    9    11    13    15    19    23
1    3    5    7    9    11    13    15    17    21

【根据i柱求j盘：
f[i,j]=min(2*f[i,k]+f[i-1,j-k]) 据en维基百科】
我找到的规律是，数列增加值总是一个2的方幂的数列，每个数出现的次数写成方阵:
增加值表

PS：

塔的 \    增加    |2    4    8    16    32    64    128    256    512    1024
数目  \    值        |----------------------------------------
3                |1    1        1        1        1         1        1           1        1        1   
4                |2    3        4        5        6         8        9        10        11
5                |3    6        10    15       21       28      36
6                |4    10      20    35       56      84      120
7                |5    15      35    70      126     210    330

具體來說：

實驗結果：

偏移值表：

結果是，例如1000個柱子時從1000 2995我的答案和標程就不同了。

很懷疑標程的規律到底看了多久~有多少檢驗。

正在企圖發信給lk。

phoeagon