ハノイの塔ハノイの塔ハノイの塔ハノイの塔

アルゴリズムとデータ構造 補足資料 9-1

「ハノイの塔」

横浜国立大学

理工学部

数物・電子情報系学科

富井尚志

ハノイの塔

ハノイの塔

• 条件１：一度に一枚の円盤だけが移動で きる。

• 条件２：どの円盤もその円盤より小さい 円盤の上においてはいけない。

• 条件３：棒Ｃを補助的な場所として良い

。

ハノイの塔：実際にやってみよう

（準備）

• Ａ４の紙を配ります。

（裏紙：再利用紙です。裏側の白い面を使いま す。）

• まず、半分に切ってください。

– できた 2 枚のうち、一枚をまた半分に切ってください。

•

できた

枚のうち、一枚をまた半分に切ってください。

–

できた

枚のうち、一枚をまた半分に切ってください。

»

できた

枚のうち、一枚をまた半分に切ってください。

» 5

回くらいでいいです。。。

»

これも再帰的。。。

半分に切 る

ハノイの塔：実際にやってみよう

（準備）

ハノイの塔：実際にやってみよう

（準備）

ハノイの塔：実際にやってみよう

（準備）

これは使いません。→

番号をかいて、

四隅にしるしをつけよう。

（奇数のカードの四隅には 、偶数のカードの四隅には

）

5

● ●

● ●

3

● ●

● ●

1

・ ・

4

× ×

×

×

2

× ×

×

×

ハノイの塔：実際にやってみよう

（準備）

順番に重ねる。

5

● ●

●

4

× ×

×

×

3

● ●

● ● 2

× ×

×

× 1

・ ・

・ ・

ハノイの塔：実際にやってみよう

（準備）

順番に重ねる。

（四隅のしるしが見えるように）

5

● ●

● ●

4

× ×

×

×

3

● ●

● ●

2

× ×

×

×

1

・ ・

・ ・

棒（領域）Ａ

ハノイの塔：実際にやってみよう

（準備）

円盤→カード 棒→領域

5

● ●

● ●

4

× ×

×

×

3

● ●

● ●

2

× ×

×

×

1

・ ・

・ ・

棒（領域） B 棒（領域） C

棒（領域）Ａ

ハノイの塔：実際にやってみよう

（準備）

• 一度に、一番上の 1 枚だけ移動できる

• どのカードも、そのカードより小さいカードの 上においてはいけない

• 領域 C を補助的な場所として使用してよい

最終的に、カードの束を、領域Ａから領域Ｂに移動させる

5

● ●

● ●

4

× ×

×

×

3

● ●

● ●

2

× ×

×

×

1

・ ・

・ ・

棒（領域） B 棒（領域） C

スタート

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：実際にやってみよう

（準備）

• 一度に、一番上の 1 枚だけ移動できる

• どのカードも、そのカードより小さいカードの 上においてはいけない

• 領域 C を補助的な場所として使用してよい

最終的に、カードの束を、領域Ａから領域Ｂに移動させる

5

● ●

● ●

4

× ×

×

×

3

● ●

● ●

2

× ×

×

×

1

・ ・

・ ・

ゴール

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：実際にやってみよう

（まずは 2 枚から）

• 一度に、一番上の 1 枚だけ移動できる

• どのカードも、そのカードより小さいカードの 上においてはいけない

• 領域 C を補助的な場所として使用してよい

最終的に、カードの束を、領域Ａから領域Ｂに移動させる

2

× ×

×

× 1

・ ・

・ ・

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：実際にやってみよう

（まずは 2 枚から）

• 一度に、一番上の 1 枚だけ移動できる

• どのカードも、そのカードより小さいカードの 上においてはいけない

• 領域 C を補助的な場所として使用してよい

最終的に、カードの束を、領域Ａから領域Ｂに移動させる

2

× ×

×

×

1

・ ・

・ ・

スタート

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：実際にやってみよう

（まずは 2 枚から）

• 一度に、一番上の 1 枚だけ移動できる

• どのカードも、そのカードより小さいカードの 上においてはいけない

• 領域 C を補助的な場所として使用してよい

最終的に、カードの束を、領域Ａから領域Ｂに移動させる

2

× ×

×

×

1

・ ・

・ ・

A

から

へ 移動

2

を

に移動させ るにまず、

その上の

を

に移動させる

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：実際にやってみよう

（まずは 2 枚から）

• 一度に、一番上の 1 枚だけ移動できる

• どのカードも、そのカードより小さいカードの 上においてはいけない

• 領域 C を補助的な場所として使用してよい

最終的に、カードの束を、領域Ａから領域Ｂに移動させる

2

× ×

×

×

1

・ ・

・ ・

A

から

へ 移動

一番下の

を

に移動させた

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：実際にやってみよう

（まずは 2 枚から）

• 一度に、一番上の 1 枚だけ移動できる

• どのカードも、そのカードより小さいカードの 上においてはいけない

• 領域 C を補助的な場所として使用してよい

最終的に、カードの束を、領域Ａから領域Ｂに移動させる

2

× ×

×

×

1

・ ・

・ ・

C

から

へ 移動

C

に退避して いた

を

B

に移動させた

ゴール！

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：実際にやってみよう

（つぎは 3 枚）

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

実際にやってみよう

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：実際にやってみよう

実際にやってみよう ゴールが B か C かは

あまり気にせず、 4 枚、 5 枚、、、

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：解き方

この水色の山を B に動かすには

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：解き方

この水色の山を B に動かすには、

まずその上の紫を

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：解き方

この水色の山を B に動かすには、

まずその上の紫を C に「移動」して

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：解き方

この水色の山を B に動かすには、

まずその上の紫を C に「移動」して 一番下を B に動かし

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：解き方

この水色の山を B に動かすには、

まずその上の紫を C に「移動」して 一番下を B に動かし

C に退避した部分を B に「移動」

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：プログラム

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

この水色の山を B に動かすには

hanoi( 4, “ 棒 A”, “ 棒 B”, “ 棒 C”)

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：プログラム

この水色の山を B に動かすには、

まずその上の紫を

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

hanoi( 3, “ 棒 A”, “ 棒 C”, “ 棒 B”)

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：プログラム

この水色の山を B に動かすには、

まずその上の紫を C に「移動」して

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

hanoi( 3, “ 棒 A”, “ 棒 C”, “ 棒 B”);

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：プログラム

この水色の山を B に動かすには、

まずその上の紫を C に「移動」して 一番下を B に動かし

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

hanoi( 3, “ 棒 A”, “ 棒 C”, “ 棒 B”);

move(“ 棒 A”, “ 棒 B”);

棒（領域）Ａ 棒（領域） B 棒（領域） C

ハノイの塔：プログラム

この水色の山を B に動かすには、

まずその上の紫を C に「移動」して 一番下を B に動かし

C に退避した部分を B に「移動」

4

× ×

×

×

3

● ●

● ●2

× ×

×

× 1

・ ・

・ ・

hanoi( 3, “ 棒 A”, “ 棒 C”, “ 棒 B”);

move(“ 棒 A”, “ 棒 B”);

hanoi(3, “ 棒 C”, “ 棒 B”, “ 棒 A”);

ハノイの塔：プログラム

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);

} }

src : “ 棒 A” dst: “ 棒 B” work: “ 棒 C”

ndisk

枚

ハノイの塔：プログラム

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);

} }

src : “ 棒 A” dst: “ 棒 B” work: “ 棒 C”

ndisk

枚

ndisk-1

枚

ハノイの塔：プログラム

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);

} }

src : “ 棒 A” dst: “ 棒 B” work: “ 棒 C”

ndisk

枚

枚

ハノイの塔：プログラム

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);

} }

src : “ 棒 A” dst: “ 棒 B” work: “ 棒 C”

ndisk

枚

枚

ハノイの塔：プログラム

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);

} }

src : “ 棒 A” dst: “ 棒 B” work: “ 棒 C”

ndisk

枚

枚

ハノイの塔：プログラム

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);

} }

src : “ 棒 A” dst: “ 棒 B” work: “ 棒 C”

ndisk

枚

枚

ハノイの塔：プログラム

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);

} }

src : “ 棒 A” dst: “ 棒 B” work: “ 棒 C”

ndisk

枚

ndisk-1

枚

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

棒

棒

棒

hanoi(3, “

棒

棒

棒

ゴールのイメージ

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

棒

棒

棒

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

棒

棒

棒

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

hanoi(2, “

棒

棒

棒

ゴールのイメージ

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

hanoi(2, “

棒

棒

棒

ゴールのイメージ

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

hanoi(1, “棒A”, “棒B”, “棒C”)

棒

棒

棒

hanoi(1, “

棒

棒

棒

ゴールのイメージ

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

hanoi(1, “棒A”, “棒B”, “棒C”)

棒

棒

棒

hanoi(1, “

棒

棒

棒

ゴールのイメージ

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(1, “棒A”, “棒B”, “棒C”)

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “棒A”, “棒C”, “棒 B”)

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

棒

棒

棒

hanoi(0, “

棒

棒

棒

円盤数が

なので、

何もしないで戻る

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(1, “棒A”, “棒B”, “棒C”)

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “棒A”, “棒C”, “棒 B”)

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

棒

棒

棒

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(1, “棒A”, “棒B”, “棒C”)

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “棒A”, “棒C”, “棒 B”)

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

棒

棒

棒

move(“

棒

棒

「棒

から棒

へ移動」

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(1, “棒A”, “棒B”, “棒C”)

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “棒A”, “棒C”, “棒 B”)

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

棒

棒

棒

hanoi(0, “

棒

棒

棒

円盤数が

なので、

何もしないで戻る

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

hanoi(1, “棒A”,“棒B”, “棒 C”) C

棒

棒

棒

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

move(“

棒

棒

「棒

から棒

へ移動」

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

hanoi(1, “棒B”, “棒C”, “棒A”)

hanoi(1, “

棒

棒

棒

ゴールのイメージ

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

hanoi(1, “棒B”, “棒C”, “棒A”)

hanoi(1, “

棒

棒

棒

ゴールのイメージ

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

B work

棒

A

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

hanoi(1, “棒B”, “棒C”, “棒A”)

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

B work

棒

A

hanoi(0, “

棒

棒

棒

円盤数が

なので、

何もしないで戻る

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

hanoi(1, “棒B”, “棒C”, “棒A”)

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

B work

棒

A move(“

棒

棒

「棒

から棒

へ移動」

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

hanoi(1, “棒B”, “棒C”, “棒A”)

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

B work

棒

A

hanoi(0, “

棒

棒

棒

円盤数が

なので、

何もしないで戻る

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

hanoi(1, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

B work

棒

A

hanoi(1, “棒B”, “棒C”, “棒 A”)

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

B

hanoi(2, “棒A”, “棒C”, “棒 B”)

棒

棒

棒

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

hanoi(2, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

C

を使って 移動

src

棒

A work

棒

han B

2 oi(

棒 , “

“ A”, C” 棒 棒 , “

B”)

棒

棒

棒

ハノイの塔：実行の様子

hanoi(3, “

棒

棒

棒

if(ndisk>=1){

hanoi(ndisk-1, src, work, dst);

move(src, dst);

hanoi(ndisk-1, work, dst, src);

}

ndisk

から

枚の円盤を

へ

dst

棒

B

を使って 移動

src

棒

A work

棒

C

棒

棒

棒