常 つね 玩具 おもちゃ 版 ばん 塔 とう 有 ゆう 3个圆盘的汉诺塔 とう 的 てき 移 うつり 4个圆盘的汉诺塔 とう 的 てき 移 うつり 汉诺塔 とう （：河 かわ 是 ぜ 根 ね 据 すえ
有 ゆう 三根 みつね 有 ゆう 穿孔 せんこう 尺寸 しゃくすん 由 よし 下 か 到 いた 上 じょう 依 よ 次 じ 要求 ようきゅう 列 れつ 将 しょう 所有 しょゆう 移 うつり 至 いたり
每次 まいじ 只 ただ 能 のう 移 うつり 大 だい 不能 ふのう 小 しょう 面 めん 提示 ていじ 可 か 将 しょう 置 おけ 将 はた 移出 いしゅつ 的 てき 重 おも 新 しん 移 うつり 回 かい 但 ただし 都 と 上述 じょうじゅつ
问：如何 いか 移 うつり 最少 さいしょう 要 よう 移 うつり 多少 たしょう 次 じ
这里有 ゆう 汉诺塔 とう 在 ざい 面 めん ，可 か 以来 いらい 体 からだ 可 か 置 おけ 不同 ふどう 取 と 最 さい 提示 ていじ 解 かい 支持 しじ 任意 にんい 初 はつ 始 はじめ 状 じょう 取 と 最 さい 佳 けい 移 うつり 径 みち
最早 もはや 發明 はつめい 問題 もんだい 的 てき 人 じん 是 ぜ 法 ほう 國 こく 數學 すうがく 家 か 愛 あい 德 とく 華 はな 盧 の
傳說 でんせつ 越 こし 南 みなみ 河内 かわうち 某 ぼう 間 あいだ 寺院 じいん 有 ゆう 三 さん 根 ね 銀 ぎん 棒 ぼう 上 うえ 串 くし 盤 ばん 寺院 じいん 裡 うら 的 てき 僧 そう 照 あきら 一 いち 個 こ 古老 ころう 的 てき 預言 よげん 以上 いじょう 述 じゅつ 規則 きそく 移動 いどう 盤 ばん 子 こ 預言 よげん 說 せつ 當 とう 盤 ばん 子 こ 移動 いどう 完 かん 世界 せかい 滅亡 めつぼう 傳說 でんせつ 叫 さけべ 梵天 ぼんてん 寺 てら 之 の 塔 とう 問題 もんだい 但 ただし 不知 ふち 道 どう 是 ぜ 盧 の 自 じ 創 そう 的 てき 傳說 でんせつ 還 かえ 是 ぜ 他 た 他人 たにん 啟發 けいはつ
若 わか 傳說 でんせつ 屬 ぞく 實 み 僧 そう 需要 じゅよう
2
64
−
1
{\displaystyle 2^{64}-1}
步 ふ 才能 さいのう 完成 かんせい 任務 にんむ 若 わか 他 た 每秒 まいびょう 可 か 完成 かんせい 一 いち 個 こ 盤 ばん 子 こ 的 てき 移動 いどう 需要 じゅよう 億 おく 年 ねん 才能 さいのう 完成 かんせい 整 せい 個 こ 宇宙 うちゅう 現在 げんざい 過 か 億 おく 年 ねん
這個傳說 でんせつ 有 ゆう 若干 じゃっかん 變體 へんたい 寺院 じいん 換 かわ 成 なる 修道院 しゅうどういん 僧 そう 成 なり 修士 しゅうし 等 とう 等 とう 寺院 じいん 的 てき 地點 ちてん 紛 まがえ 所以 ゆえん 被 ひ 命名 めいめい 為 ため 河 かわ 亦 また 有 ゆう 金 かね 盤 ばん 是 ぜ 創世 そうせい 時 どき 所 しょ 造 づくり 僧侶 そうりょ 天 てん 移動 いどう 一 いち 盤 ばん 之 これ 類 るい 的 てき 背景 はいけい 設定 せってい
如取 N=64，最少 さいしょう 64 −1 次 じ 即 そく 億 おく 年 ねん 目前 もくぜん 宇宙 うちゅう 大 だい 爆 ばく 論 ろん 的 てき 宇宙 うちゅう 的 てき 年齡 ねんれい 億 おく 年 ねん
在 ざい 真 ま 具 ぐ 中 ちゅう 一般 いっぱん 最少 さいしょう 次 じ 最少 さいしょう 次 じ 最少 さいしょう 次 じ 是 ぜ 一 いち 每 まい 天 てん 移 うつり 他 た 最多 さいた 移 うつり 最少 さいしょう 次 じ 即 そく 超 ちょう 一 いち 百 ひゃく 万 まん 次 じ
解法 かいほう 的 てき 基本 きほん 思想 しそう 是 ぜ 假 かり 三 さん 塔 とう 有 ゆう
N
{\displaystyle N}
目 もく 把 わ 部 ぶ 移 うつり 到 いた 塔 とう 那 な 把 わ 塔 とう 的 てき
N
−
1
{\displaystyle N-1}
移 うつり 塔 とう 再 さい 把 わ 塔 とう 剩 あま 下 した 的 てき 大 だい 到 いた 最 さい 后 きさき 把 わ 塔 とう 的 てき
N
−
1
{\displaystyle N-1}
移 うつり 到 いた
如此递归地 ち 使用 しよう 下 か 去 さ 解 かい
在 ざい 語 ご 言 げん 中 ちゅう
public class HW {
public static java . util . Scanner sc = new java . util . Scanner ( System . in );
public static void Towers ( int n , char a , char b , char c ){
if ( n == 1 ){
System . out . println ( "移動 いどう + n + "從 したがえ + a + "到 いた + c );
}
else {
Towers ( n -1 , a , c , b );
System . out . println ( "移動 いどう + n + "從 したがえ + a + "到 いた + c );
Towers ( n -1 , b , a , c );
}
}
public static void main ( String [] args ) {
int n = sc . nextInt ();
Towers ( n , 'A' , 'B' , 'C' );
}
}
C++ 语言实现：
#include <iostream>
using namespace std ;
void Towers ( int n , char a , char b , char c ){
if ( n == 1 ){
cout << "Move disk " << n << " from" << a << " to " << c << endl ;
}
else {
Towers ( n -1 , a , c , b );
cout << "Move disk " << n << " from" << a << " to " << c << endl ;
Towers ( n -1 , b , a , c );
}
}
int main ( int argc , char * argv []) {
int n ;
cin >> n ;
Towers ( n , 'A' , 'B' , 'C' );
cout << endl ;
}
以 Python 语言实现：
def hanoi ( n , a , b , c ):
if n == 1 :
print ( a , '-->' , c )
else :
hanoi ( n - 1 , a , c , b )
hanoi ( 1 , a , b , c )
hanoi ( n - 1 , b , a , c )
# 调用
if __name__ == '__main__' :
hanoi ( 5 , 'A' , 'B' , 'C' )
以 Erlang 语言求 もとめ 解 かい
- module ( hanoi ).
- export ([ hanoi / 1 ]).
hanoi ( N ) when N > 0 ->
do_hanoi ({ N , 1 , 3 }).
do_hanoi ({ 0 , _, _}) ->
done ;
do_hanoi ({ 1 , From , To }) ->
io : format ( "From ~p , To ~p~n " , [ From , To ]);
do_hanoi ({ N , From , To }) ->
do_hanoi ({ N - 1 , From , by ( From , To )}),
do_hanoi ({ 1 , From , To }),
do_hanoi ({ N - 1 , by ( From , To ), To }).
by ( From , To ) ->
[ Result |_] = [ 1 , 2 , 3 ] -- [ From , To ],
Result .
以 Haskell 语言实现：
hanoi :: Integer -> String -> String -> String -> [( String , String )]
hanoi 0 _ _ _ = []
hanoi 1 from _ to = [( from , to )]
hanoi x from buffer to =
hanoi ( x - 1 ) from to buffer ++ hanoi 1 from buffer to ++ hanoi ( x - 1 ) buffer from to
任意 にんい 初 はつ 始 はじめ 結構 けっこう 的 てき 解法 かいほう [ 编辑 ] 為 ため 了 りょう 從 したがえ 任意 にんい 初 はつ 始 はじめ 結構 けっこう 中 ちゅう 最 さい 佳 けい 解 かい 算法 さんぽう 可 か 一般 いっぱん 化 か
以 Scheme 語 ご 言 げん 表示 ひょうじ
; Let conf be a list of the positions of the disks in order of increasing size.
; Let the pegs be identified by the numbers 0, 1 and 2.
( define ( hanoi conf t )
( let (( c ( list->vector conf )))
( define ( move h f t )
( vector-set! c h t )
( printf "move disk ~s from peg ~s to peg ~s~n" h f t ))
( define ( third-peg f t ) ( - 3 f t ))
( define ( hanoi h t )
( if ( > h 0 )
( let (( h ( sub1 h )))
( let (( f ( vector-ref c h )))
( if ( not ( = f t ))
( let (( r ( third-peg f t )))
( hanoi h r )
( move h f t )))
( hanoi h t )))))
( hanoi ( vector-length c ) t )))
在 ざい 語 ご 言 げん 中 ちゅう
public class Hanoi {
public static void main ( String [] args ) {
// TODO Auto-generated method stub
System . out . println ( hanoiFunc ( 7 ));
}
public static int hanoiFunc ( int i ) {
int sum = 0 ;
if ( i == 1 ) {
sum += i ;
}
else {
sum = 2 * hanoiFunc ( i - 1 ) + 1 ;
}
return sum ;
}
}
在 ざい 語 ご 言 げん 中 ちゅう
int conf [ HEIGHT ]; /* Element conf[d] gives the current position of disk d. */
void move ( int d , int t ) {
/* move disk d to peg t */
conf [ d ] = t ;
}
void hanoi ( int h , int t ) {
if ( h > 0 ) {
int f = conf [ h -1 ];
if ( f != t ) {
int r = 3 - f - t ;
hanoi ( h -1 , r );
move ( h -1 , t );
}
hanoi ( h -1 , t );
}
}
可 か 表示 ひょうじ 塔 とう 在 ざい 表示 ひょうじ 的 てき 会 かい 更 さら 加地 かじ 直 ただし 清 きよし 理解 りかい 上 じょう 有 ゆう 一 いち 点 てん
现在规定， 每 まい 每 ごと
注 ちゅう 不 ふ 考 こう 柱 ばしら 子 こ 之 の 没 ぼつ 有意 ゆうい 来 らい 回 かい 移 うつり 情 じょう
对于只 ただ 有 ゆう 可 か 表示 ひょうじ
对于有 ゆう 的 てき 塔 とう 可 か 表示 ひょうじ
相互 そうご 的 てき 三 さん 三角形 さんかっけい 了 りょう
每 まい 初 はつ 有 ゆう 被 ひ 移 うつり
对于每 ごと 一 いち 端 はし 的 てき 小 しょう 三角形 さんかっけい 表示 ひょうじ 的 てき 一 いち 方法 ほうほう
外 そと 表示 ひょうじ 在 ざい
对于 h+1 个盘子 こ 子 こ 的 てき 三角形 さんかっけい 然 しか 后 きさき 稍 やや 微 ほろ 改 あらため 下 か
这个大 だい 的 てき 子 こ 情 じょう
所以 ゆえん 当 とう 有 ゆう
按照从小到 いた 大 だい 的 てき 到 いた 右 みぎ 地 ち 列 れつ 出 で 的 てき 的 てき 位置 いち 最 さい 外面 がいめん 的 てき 三角形 さんかっけい 的 てき 表示 ひょうじ 了 りょう 最大 さいだい 的 てき 上面 うわつら 由 よし 次 じ 小 しょう 表示 ひょうじ 着 ぎ 最大 さいだい 的 てき 的 てき 移 うつり 式 しき
同 どう 理 り 在 ざい 一 いち 次次 つぎつぎ 小 しょう 表示 ひょうじ 着 ぎ 次 じ 大 だい 的 てき 的 てき 移 うつり 式 しき 下 か 去 さ 可 か 表示 ひょうじ 出 で
具有 ぐゆう 谢尔宾斯基 もと 三角形 さんかっけい 的 てき 通常 つうじょう 具有 ぐゆう 子 こ 的 てき 有 ゆう
3
n
{\displaystyle 3^{n}}
点 てん 每 ごと 点 てん 都 と 有 ゆう 但 ただし 是 ぜ 在 ざい 顶点 的 まと 的 てき 只 ただ 有 ゆう 有 ゆう 接着 せっちゃく 所以 ゆえん 是 ぜ 下 か 都 と 可 か 最小 さいしょう 的 てき 移 うつり 柱 ばしら 子中 こなか 的 てき 一 いち 多数 たすう 情 じょう 是 ぜ 可 か 柱 ばしら 子 こ 子 こ 除 じょ 了 りょう 所有 しょゆう 的 てき 都 と 在 ざい 一 いち 子 こ 上 じょう 的 てき 表示 ひょうじ 着 ぎ 所有 しょゆう 的 てき 都 と 在 ざい 即 そく 可 か 或 ある 柱 はしら 上 じょう 堆 うずたか 子 こ 只 ただ 要 よう 三 さん
n
+
1
{\displaystyle n+1}
子 こ 的 てき 可 か 表示 ひょうじ
n
{\displaystyle n}
子 こ 的 てき 三 さん 在 ざい 一 いち 起 おこり 的 てき 因 よし 方便 ほうべん 地 ち 表示 ひょうじ 了 りょう 每 ごと 每 ごと 一 いち 小 しょう 的 てき 次 じ 小 しょう 的 てき 所以 ゆえん 有 ゆう
3
n
+
1
{\displaystyle 3^{n}+1}
点 てん 基本 きほん 都 と 有 ゆう 顶点 只 ただ 有 ゆう
在 ざい 数 すう 比 ひ 的 てき 塔 とう 的 てき 和 わ 分 ぶん 形 がた 相似 そうじ 了 りょう
如果使用 しよう 最 さい 麻 あさ 移 うつり 式 しき 即 そく 不 ふ 走 はし 重 じゅう 路 ろ 移 うつり 式 しき 需要 じゅよう
3
64
−
1
{\displaystyle 3^{64}-1}
次 つぎ 移 うつり 每秒 まいびょう 移 うつり 一 いち 次 じ 需要 じゅよう 的 てき 超 ちょう
10
23
{\displaystyle 10^{23}}
年 とし
在 ざい 不 ふ 考 こう 使用 しよう 路 ろ 径 みち 的 てき 情 じょう 去 さ 除 じょ 有 ゆう 的 てき 表示 ひょうじ 出 で 当 とう 有 ゆう
就是没 ぼつ 有 ゆう 去 さ 意 い 多 た 余 あまり 的 てき 的 てき 将 はた 去 さ 除 じょ 没 ぼつ 有 ゆう 使用 しよう 的 てき 移 うつり 法 ほう 到 いた 当 とう 有 ゆう
顺便一 いち 提 ひさげ 最 さい 非 ひ 重 じゅう 径 みち 可 か 除 じょ 到 いた 的 てき 路 ろ 径 みち 得 え 到 いた
也可以得出 で 哈密顿回路 ろ ：
该图较为清楚 せいそ 地表 ちひょう
对于任意 にんい 的 てき 全部 ぜんぶ 在 ざい 将 しょう 所有 しょゆう 移 うつり
对于任意 にんい 的 てき 分布 ぶんぷ 情 じょう 只 ただ 有 ゆう
对于任意 にんい 的 てき 分布 ぶんぷ 情 じょう 都 みやこ 有一 ゆういち 者 しゃ 将 しょう 所有 しょゆう 移 うつり 任意 にんい
对于任意 にんい 的 てき 分布 ぶんぷ 情 じょう 只 ただ 有 ゆう
设
N
h
{\displaystyle N_{h}}
是 これ 将 はた 有 ゆう
h
{\displaystyle h}
子 こ 的 てき 塔 とう 将 はた 所有 しょゆう 可 か 出 で
N
1
=
1
{\displaystyle N_{1}=1}
N
h
+
1
=
(
N
h
)
2
+
(
N
h
)
3
{\displaystyle N_{h+1}=(N_{h})^{2}+(N_{h})^{3}}
这里的 てき
N
h
∈
{
2
,
12
,
1872
,
6563711232
,
.
.
.
.
}
{\displaystyle N_{h}\in \{2,12,1872,6563711232,....\}}
在 ざい A125295 上 うえ
在 ざい 有 ゆう 子 こ 所 しょ 数 すう 的 てき 公式 こうしき 但 ただし 子 こ 以上 いじょう 時 じ 情 じょう 形 がた 複雜 ふくざつ 許多 きょた 在 ざい 年 ねん 時 じ 分別 ふんべつ 提出 ていしゅつ 了 りょう 基本 きほん 上相 かみや 同 どう 的 てき 一 いち 算法 さんぽう [ 1] 則 そく 在 ざい 年 ねん 證明 しょうめい 了 りょう 演算 えんざん 法 ほう 在 ざい 個 こ 柱 はしら 子 こ 時 じ 最 さい 佳 けい 解 かい [ 2] 但 ただし 算法 さんぽう 在 ざい 個 こ 柱 はしら 子 こ 以上 いじょう 是 ぜ 否 ひ 是 ぜ 最 さい 佳 けい 解 かい 未知 みち Frame-Stewart 演算 えんざん 法 ほう 本質 ほんしつ 上 じょう 的 てき 可 か 簡單 かんたん
令 れい
f
(
n
,
k
)
{\displaystyle f(n,k)}
有 ゆう
k
{\displaystyle k}
子 こ 移 うつり 一 いち 柱 はしら 子 こ 上 じょう 需要 じゅよう 的 てき 步数 ほすう 对于任 にん 何 なん 移 うつり 法 ほう 必定 ひつじょう 会 かい 先 さき 将 はた
m
(
1
≤
m
≤
n
−
1
)
{\displaystyle m(1\leq m\leq n-1)}
再 さい 将 しょう 第 だい
n
{\displaystyle n}
到 いた 第 だい
n
−
m
{\displaystyle n-m}
下 か 的 てき
k
−
1
{\displaystyle k-1}
子 こ 移 うつり 到 いた 目 め 子 こ 上 じょう 最 さい 后 きさき 将 しょう
m
{\displaystyle m}
在中 ざいちゅう 子 こ 上 じょう 的 てき 移 うつり 目 め 子 こ 上 じょう 所 しょ 操作 そうさ 步数 ほすう
2
f
(
m
,
k
)
+
f
(
n
−
m
,
k
−
1
)
{\displaystyle 2f(m,k)+f(n-m,k-1)}
进行最 さい 易 えき 得 とく
f
(
n
,
k
)
=
m
i
n
m
∈
[
1
,
n
−
1
]
(
2
f
(
m
,
k
)
+
f
(
n
−
m
,
k
−
1
)
)
{\displaystyle f(n,k)=\mathrm {min} _{m\in [1,n-1]}\;(2f(m,k)+f(n-m,k-1))}
2011年 ねん 電 でん 影 かげ 猿 さる 人 じん 爭 そう 革命 かくめい 出現 しゅつげん 河 かわ 試 ためし 猩猩 しょうじょう 的 てき 智 さとし 商 しょう 影 かげ 猩球崛起2 》中 なか 也有 やゆう 的 てき
^ Stewart, B.M.; Frame, J.S. Solution to advanced problem 3819. American Mathematical Monthly. March 1941, 48 (3): 216–9. JSTOR 2304268 doi:10.2307/2304268 ^ Bousch, T. La quatrieme tour de Hanoi. Bull. Belg. Math. Soc. Simon Stevin. 2014, 21 : 895–912.
一个盘子的情况
两个盘子
三个盘子的汉诺塔
三个盘子的汉诺塔 -
三个盘子的汉诺塔的哈密顿回路
![{\displaystyle f(n,k)=\mathrm {min} _{m\in [1,n-1]}\;(2f(m,k)+f(n-m,k-1))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8801c54a08173d6206b9e102c4ad48d09569af1c)
