ハノイの塔 - 横浜国立大学 富井研究室

アルゴリズムとデータ構造
補足資料9-1
「ハノイの塔」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
ハノイの塔
ハノイの塔
• 条件1:一度に一枚の円盤だけが移動できる。
• 条件2:どの円盤もその円盤より小さい円盤
の上においてはいけない。
• 条件3:棒Cを補助的な場所として良い。
ハノイの塔:実際にやってみよう
(準備)
• A4の紙を配ります。
(裏紙:再利用紙です。裏側の白い面を使いま
す。)
• まず、半分に切ってください。
– できた2枚のうち、一枚をまた半分に切ってください。
• できた2枚のうち、一枚をまた半分に切ってください。
– できた2枚のうち、一枚をまた半分に切ってください。
» できた2枚のうち、一枚をまた半分に切ってください。
» 5回くらいでいいです。。。
» これも再帰的。。。
ハノイの塔:実際にやってみよう
(準備)
半分に切
る
ハノイの塔:実際にやってみよう
(準備)
ハノイの塔:実際にやってみよう
(準備)
●
●
×
5
●
×
●
4
●
×
●
3
×
●
×
×
2
●
×
・
・
1
×
・
・
番号をかいて、
四隅にしるしをつけよう。
(奇数のカードの四隅には●、偶数のカードの四隅には×)
これは使いません。→
ハノイの塔:実際にやってみよう
(準備)
●
●
5
×
×
4
●●
●
×
●
3×
×
●
●
×
2・
×
・
×
1
・
・
順番に重ねる。
ハノイの塔:実際にやってみよう
(準備)
●
×
●
×
●
×・
●
×
・
・
×
●
・
×
●
5
312
4
×
●
×
●
順番に重ねる。
(四隅のしるしが見えるように)
ハノイの塔:実際にやってみよう
(準備)
●
×
●
×
●
×・
●
×
・
・
×
●
・
×
●
5
312
4
×
●
×
●
棒(領域)A
円盤→カード
棒→領域
棒(領域)B
棒(領域)C
ハノイの塔:実際にやってみよう
(準備)
スタート
●
×
●
×
●
×・
●
×
・
・
×
●
・
×
●
5
312
4
×
●
×
●
棒(領域)A
棒(領域)B
棒(領域)C
•一度に、一番上の1枚だけ移動できる
•どのカードも、そのカードより小さいカードの
上においてはいけない
•領域Cを補助的な場所として使用してよい
最終的に、カードの束を、領域Aから領域Bに移動させる
ハノイの塔:実際にやってみよう
(準備)
●
×
ゴール
●
×
●
×・
●
・×
・
×
●
・
×
●
5
312
4
×
●
棒(領域)A
×
●
棒(領域)B
棒(領域)C
•一度に、一番上の1枚だけ移動できる
•どのカードも、そのカードより小さいカードの
上においてはいけない
•領域Cを補助的な場所として使用してよい
最終的に、カードの束を、領域Aから領域Bに移動させる
ハノイの塔:実際にやってみよう
(まずは2枚から)
×
×
2・
×
・
×
1
・
・
棒(領域)A
棒(領域)B
棒(領域)C
•一度に、一番上の1枚だけ移動できる
•どのカードも、そのカードより小さいカードの
上においてはいけない
•領域Cを補助的な場所として使用してよい
最終的に、カードの束を、領域Aから領域Bに移動させる
ハノイの塔:実際にやってみよう
(まずは2枚から)
スタート
×
・
・
×
×
・
1
2
・
×
棒(領域)A
棒(領域)B
棒(領域)C
•一度に、一番上の1枚だけ移動できる
•どのカードも、そのカードより小さいカードの
上においてはいけない
•領域Cを補助的な場所として使用してよい
最終的に、カードの束を、領域Aから領域Bに移動させる
ハノイの塔:実際にやってみよう
(まずは2枚から)
AからCへ
移動
×
×
・
2
2をBに移動させ
るにまず、
その上の1を
Cに移動させる
×
・
1
×
棒(領域)A
・
棒(領域)B
・
棒(領域)C
•一度に、一番上の1枚だけ移動できる
•どのカードも、そのカードより小さいカードの
上においてはいけない
•領域Cを補助的な場所として使用してよい
最終的に、カードの束を、領域Aから領域Bに移動させる
ハノイの塔:実際にやってみよう
(まずは2枚から)
AからBへ
移動
×
×
・
2
一番下の2を
Bに移動させた
×
棒(領域)A
・
1
×
棒(領域)B
・
・
棒(領域)C
•一度に、一番上の1枚だけ移動できる
•どのカードも、そのカードより小さいカードの
上においてはいけない
•領域Cを補助的な場所として使用してよい
最終的に、カードの束を、領域Aから領域Bに移動させる
ハノイの塔:実際にやってみよう
(まずは2枚から)
CからAへ
移動
×
・
・
×
Cに退避して
いた1を
Bに移動させた
ゴール!
棒(領域)A
×
・
1
2
・
×
棒(領域)B
棒(領域)C
•一度に、一番上の1枚だけ移動できる
•どのカードも、そのカードより小さいカードの
上においてはいけない
•領域Cを補助的な場所として使用してよい
最終的に、カードの束を、領域Aから領域Bに移動させる
ハノイの塔:実際にやってみよう
(つぎは3枚)
●
●
3
×
●
×
2
●
×
・
×
・
・
・
1
棒(領域)A
棒(領域)B
棒(領域)C
実際にやってみよう
ハノイの塔:実際にやってみよう
×
×
4
●
×
●
3×
×
●
×
2・
●
×
・
×
1
・
棒(領域)A
・
棒(領域)B
棒(領域)C
実際にやってみよう
ゴールがBかCかは
あまり気にせず、4枚、5枚、、、
ハノイの塔:解き方
×
×
4
●
×
●
3×
×
●
×
2・
●
×
・
×
1
・
棒(領域)A
・
棒(領域)B
棒(領域)C
この水色の山をBに動かすには
ハノイの塔:解き方
×
×
4
●
×
●
3×
×
●
×
2・
●
×
・
×
1
・
棒(領域)A
・
棒(領域)B
棒(領域)C
この水色の山をBに動かすには、
まずその上の紫を
ハノイの塔:解き方
×
×
●
4
×
●
3
×
●
×
×
2・
●
×
1
・
棒(領域)A
棒(領域)B
・
×
・
棒(領域)C
この水色の山をBに動かすには、
まずその上の紫をCに「移動」して
ハノイの塔:解き方
×
×
●
4
×
●
3
×
×
●
×
2・
●
×
1
・
棒(領域)A
棒(領域)B
・
×
・
棒(領域)C
この水色の山をBに動かすには、
まずその上の紫をCに「移動」して
一番下をBに動かし
ハノイの塔:解き方
×
×
4
●
×
●
3×
×
●
×
2・
●
×
1
・
棒(領域)A
・
×
・
棒(領域)B
棒(領域)C
この水色の山をBに動かすには、
まずその上の紫をCに「移動」して
一番下をBに動かし
Cに退避した部分をBに「移動」
ハノイの塔:プログラム
×
×
4
●
×
●
3×
×
●
×
2・
●
×
・
×
1
・
棒(領域)A
・
棒(領域)B
棒(領域)C
この水色の山をBに動かすには
hanoi( 4,
“棒A”, “棒B”, “棒C”)
ハノイの塔:プログラム
×
×
4
●
×
●
3×
×
●
×
2・
●
×
・
×
1
・
棒(領域)A
・
棒(領域)B
棒(領域)C
この水色の山をBに動かすには、
まずその上の紫を
hanoi( 3, “棒A”, “棒C”, “棒B”)
ハノイの塔:プログラム
×
×
●
4
×
●
3
×
●
×
×
2・
●
×
1
・
棒(領域)A
棒(領域)B
・
×
・
棒(領域)C
この水色の山をBに動かすには、
まずその上の紫をCに「移動」して
hanoi( 3, “棒A”, “棒C”, “棒B”);
ハノイの塔:プログラム
×
×
●
4
×
●
3
×
×
●
×
2・
●
×
1
・
棒(領域)A
棒(領域)B
・
×
・
棒(領域)C
この水色の山をBに動かすには、
まずその上の紫をCに「移動」して
hanoi( 3, “棒A”, “棒C”, “棒B”);
一番下をBに動かし
move(“棒A”, “棒B”);
ハノイの塔:プログラム
×
×
4
●
×
●
3×
×
●
×
2・
●
×
1
・
棒(領域)A
・
×
・
棒(領域)B
棒(領域)C
この水色の山をBに動かすには、
まずその上の紫をCに「移動」して
hanoi( 3, “棒A”, “棒C”, “棒B”);
一番下をBに動かし
move(“棒A”, “棒B”);
Cに退避した部分をBに「移動」
ハノイの塔:プログラム
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
おっと、その前に
ゴミは必ず、各自持ち帰ってください。
ハノイの塔:プログラム
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
ndisk枚
src : “棒A”
dst: “棒B”
work: “棒C”
ハノイの塔:プログラム
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
ndisk-1枚
ndisk枚
src : “棒A”
dst: “棒B”
work: “棒C”
ハノイの塔:プログラム
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
ndisk-1枚
ndisk枚
src : “棒A”
dst: “棒B”
work: “棒C”
ハノイの塔:プログラム
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
ndisk-1枚
ndisk枚
src : “棒A”
dst: “棒B”
work: “棒C”
ハノイの塔:プログラム
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
ndisk-1枚
ndisk枚
src : “棒A”
dst: “棒B”
work: “棒C”
ハノイの塔:プログラム
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
ndisk-1枚
ndisk枚
src : “棒A”
dst: “棒B”
work: “棒C”
ハノイの塔:プログラム
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
ndisk-1枚
ndisk枚
src : “棒A”
dst: “棒B”
work: “棒C”
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(3, “棒A”, “棒B”, “棒C”)
ゴールのイメージ
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(2, “棒A”, “棒C”, “棒B”)
ゴールのイメージ
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(2, “棒A”, “棒C”, “棒B”)
ゴールのイメージ
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
hanoi(1, “棒A”, “棒B”, “棒C”)
ゴールのイメージ
棒A
棒B
棒C
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
hanoi(1, “棒A”, “棒B”, “棒C”)
ゴールのイメージ
src
から dst
棒C
へ work
を使って
棒B 移動
hanoi(1, “棒A”, “棒B”, “棒C”)
src
棒B
棒A
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒A
2 枚の円盤を
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒A”, “棒B”, “棒C”)
ndisk
src
hanoi(0, “棒A”, “棒C”, “棒B”)
円盤数が0なので、
何もしないで戻る
棒A
棒B
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒A”, “棒B”, “棒C”)
ndisk
src
棒A
棒B
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
move(“棒A”, “棒B”)
src
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
src
棒B
棒A
hanoi(1, “棒A”, “棒B”, “棒C”)
「棒Aから棒Bへ移動」
棒A
2 枚の円盤を
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒A”, “棒B”, “棒C”)
ndisk
src
棒A
棒B
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
棒C
hanoi(ndisk-1, work, dst, src);
hanoi(0, “棒C”, “棒B”, “棒A”)
円盤数が0なので、
}
何もしないで戻る
ハノイの塔:実行の様子
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
hanoi(3, “棒A”, “棒B”, “棒C”)
hanoi(1, “棒A”, “棒B”, “棒C”)
ndisk
src
棒A
棒B
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
move(“棒A”, “棒C”)
「棒Aから棒Cへ移動」
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
hanoi(1, “棒B”, “棒C”, “棒A”)
ゴールのイメージ
棒A
棒B
棒C
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒B”, “棒C”, “棒A”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
hanoi(1, “棒B”, “棒C”, “棒A”)
ゴールのイメージ
src
から dst
棒C
へ work
を使って
棒B 移動
hanoi(1, “棒B”, “棒C”, “棒A”)
src
棒B
棒A
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒A
2 枚の円盤を
hanoi(1, “棒B”, “棒C”, “棒A”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒C
1 枚の円盤を
棒B
から dst
棒C
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒B”, “棒C”, “棒A”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒B”, “棒C”, “棒A”)
ndisk
src
hanoi(0, “棒B”, “棒A”, “棒C”)
円盤数が0なので、
何もしないで戻る
棒A
棒B
棒C
1 枚の円盤を
棒B
から dst
棒C
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
move(“棒B”, “棒C”)
src
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
src
棒B
棒A
hanoi(1, “棒B”, “棒C”, “棒A”)
「棒Bから棒Cへ移動」
棒A
2 枚の円盤を
hanoi(1, “棒B”, “棒C”, “棒A”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒C
1 枚の円盤を
棒B
から dst
棒C
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒B”, “棒C”, “棒A”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒B”, “棒C”, “棒A”)
ndisk
src
棒A
棒B
1 枚の円盤を
棒B
から dst
棒C
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
棒C
hanoi(ndisk-1, work, dst, src);
hanoi(0, “棒A”, “棒C”, “棒B”)
円盤数が0なので、
}
何もしないで戻る
ハノイの塔:実行の様子
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒B”, “棒C”, “棒A”)
hanoi(3, “棒A”, “棒B”, “棒C”)
hanoi(1, “棒B”, “棒C”, “棒A”)
ndisk
src
棒A
棒B
棒C
1 枚の円盤を
棒B
から dst
棒C
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒A”, “棒C”, “棒B”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒A
から dst
棒C
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
move(“棒A”, “棒B”)
「棒Aから棒Bへ移動」
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(2, “棒C”, “棒B”, “棒A”)
ゴールのイメージ
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(2, “棒C”, “棒B”, “棒A”)
ゴールのイメージ
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
hanoi(1, “棒C”, “棒A”, “棒B”)
ゴールのイメージ
棒A
棒B
棒C
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒C”, “棒A”, “棒B”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
hanoi(1, “棒C”, “棒A”, “棒B”)
ゴールのイメージ
src
から dst
棒B
へ work
を使って
棒A 移動
hanoi(1, “棒C”, “棒A”, “棒B”)
src
棒B
棒C
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒A
2 枚の円盤を
hanoi(1, “棒C”, “棒A”, “棒B”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒C
1 枚の円盤を
棒C
から dst
棒A
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒C”, “棒A”, “棒B”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒C”, “棒A”, “棒B”)
ndisk
src
hanoi(0, “棒C”, “棒B”, “棒A”)
円盤数が0なので、
何もしないで戻る
棒A
棒B
棒C
1 枚の円盤を
棒C
から dst
棒A
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
move(“棒C”, “棒A”)
src
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
src
棒B
棒C
hanoi(1, “棒C”, “棒A”, “棒B”)
「棒Cから棒Aへ移動」
棒A
2 枚の円盤を
hanoi(1, “棒C”, “棒A”, “棒B”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒C
1 枚の円盤を
棒C
から dst
棒A
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒C”, “棒A”, “棒B”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒C”, “棒A”, “棒B”)
ndisk
src
棒A
棒B
1 枚の円盤を
棒C
から dst
棒A
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
棒C
hanoi(ndisk-1, work, dst, src);
hanoi(0, “棒B”, “棒A”, “棒C”)
円盤数が0なので、
}
何もしないで戻る
ハノイの塔:実行の様子
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒C”, “棒A”, “棒B”)
hanoi(3, “棒A”, “棒B”, “棒C”)
hanoi(1, “棒C”, “棒A”, “棒B”)
ndisk
src
棒A
棒B
棒C
1 枚の円盤を
棒C
から dst
棒A
へ work
を使って
棒B 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
move(“棒C”, “棒B”)
「棒Cから棒Bへ移動」
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
hanoi(1, “棒A”, “棒B”, “棒C”)
ゴールのイメージ
棒A
棒B
棒C
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
hanoi(1, “棒A”, “棒B”, “棒C”)
ゴールのイメージ
src
から dst
棒B
へ work
を使って
棒A 移動
hanoi(1, “棒A”, “棒B”, “棒C”)
src
棒B
棒C
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒A
2 枚の円盤を
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒A”, “棒B”, “棒C”)
ndisk
src
hanoi(0, “棒A”, “棒C”, “棒B”)
円盤数が0なので、
何もしないで戻る
棒A
棒B
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
move(“棒A”, “棒B”)
src
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
src
棒B
棒C
hanoi(1, “棒A”, “棒B”, “棒C”)
「棒Aから棒Bへ移動」
棒A
2 枚の円盤を
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
hanoi(1, “棒A”, “棒B”, “棒C”)
ndisk
src
棒A
棒B
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
棒C
hanoi(ndisk-1, work, dst, src);
hanoi(0, “棒C”, “棒B”, “棒A”)
円盤数が0なので、
}
何もしないで戻る
ハノイの塔:実行の様子
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
hanoi(1, “棒A”, “棒B”, “棒C”)
hanoi(3, “棒A”, “棒B”, “棒C”)
hanoi(1, “棒A”, “棒B”, “棒C”)
ndisk
src
棒A
棒B
棒C
1 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
hanoi(2, “棒C”, “棒B”, “棒A”)
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ndisk
src
2 枚の円盤を
棒C
から dst
棒B
へ work
を使って
棒A 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
棒A
棒B
棒C
ハノイの塔:実行の様子
hanoi(3, “棒A”, “棒B”, “棒C”)
ndisk
src
3 枚の円盤を
棒A
から dst
棒B
へ work
を使って
棒C 移動
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
完了:呼び出し元(main関数)に戻る
棒A
棒B
棒C
ハノイの塔:移動回数
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst);
move(src, dst);
hanoi(ndisk-1, work, dst, src);
}
}
hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ
せるのに必要な移動回数):mnと置く
ハノイの塔:移動回数
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst); mn-1回の移動
move(src, dst);
1回の移動
hanoi(ndisk-1, work, dst, src ); mn-1回の移動
}
}
hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ
せるのに必要な移動回数):mnと置く
ハノイの塔:移動回数
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst); mn-1回の移動
move(src, dst);
1回の移動
hanoi(ndisk-1, work, dst, src ); mn-1回の移動
}
}
hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ
せるのに必要な移動回数):mnと置く、と、
mn = 2 x mn-1 +1
ハノイの塔:移動回数
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst); mn-1回の移動
move(src, dst);
1回の移動
hanoi(ndisk-1, work, dst, src ); mn-1回の移動
}
}
hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ
せるのに必要な移動回数):mnと置く、と、
mn = 2n-1
ハノイの塔:移動回数 O(2n)
void hanoi(int ndisk, char *src, char *dst, char *work)
{
if(ndisk>=1){
hanoi(ndisk-1, src, work, dst); mn-1回の移動
move(src, dst);
1回の移動
hanoi(ndisk-1, work, dst, src ); mn-1回の移動
}
}
hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ
せるのに必要な移動回数):mnと置く、と、
mn = 2n-1
ハノイの塔:移動回数 O(2n)
n
2n-1
2
3
3
7
4
15
8
255
16
65,535
32
4,294,967,295
64
およそ1019
100
およそ1030
1,000
およそ10300
hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ
せるのに必要な移動回数):mnと置く、と、
mn = 2n-1
ハノイの塔:移動回数 O(2n)
n
2n-1
2
3 x 10-10秒: 0.3ナノ秒
3
7 x 10-10秒: 0.7ナノ秒
4
15 x 10-10秒: 1.5ナノ秒
8
255 x 10-10秒: 26ナノ秒
16
65,535 x 10-10秒: 6.6マイクロ秒
32
4,294,967,295 x 10-10秒: 0.4秒
64
およそ109秒:およそ57年
100
およそ1020秒:およそ1兆年:宇宙の歴史100回分
1,000 およそ10290秒:およそ10282年:宇宙の歴史10272回分
円盤を目にもとまらぬ早業(1秒間に100億回)
で移動させたら…
mn = 2n-1