アルゴリズムとデータ構造 補足資料9-1 「ハノイの塔」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

ハノイの塔

ハノイの塔 条件１：一度に一枚の円盤だけが移動できる。 条件２：どの円盤もその円盤より小さい円盤の上においてはいけない。 条件３：棒Ｃを補助的な場所として良い。

ハノイの塔：実際にやってみよう （準備） Ａ４の紙を配ります。 （裏紙：再利用紙です。裏側の白い面を使います。） 　（裏紙：再利用紙です。裏側の白い面を使います。） まず、半分に切ってください。 できた2枚のうち、一枚をまた半分に切ってください。 5回くらいでいいです。。。 これも再帰的。。。

ハノイの塔：実際にやってみよう （準備） 半分に切る

ハノイの塔：実際にやってみよう （準備）

5 ハノイの塔：実際にやってみよう （準備） 4 3 2 番号をかいて、 四隅にしるしをつけよう。 ● 4 × 3 ● 2 × 1 ・ 番号をかいて、 四隅にしるしをつけよう。 （奇数のカードの四隅には●、偶数のカードの四隅には×） これは使いません。→

ハノイの塔：実際にやってみよう （準備） 5 ● 4 × 3 ● 2 × 1 ・ 順番に重ねる。

ハノイの塔：実際にやってみよう （準備） 5 ● 4 × 3 ● 2 × 1 ・ 順番に重ねる。 （四隅のしるしが見えるように）

5 ハノイの塔：実際にやってみよう （準備） 4 3 円盤→カード 棒→領域 棒（領域）Ａ 棒（領域）B 棒（領域）C 2 ● 1 × ● ・ 円盤→カード 棒→領域

5 ハノイの塔：実際にやってみよう （準備） 4 3 棒（領域）Ａ 棒（領域）B 棒（領域）C 一度に、一番上の1枚だけ移動できる ● スタート 4 × 3 ● 2 × 1 ・ 一度に、一番上の1枚だけ移動できる どのカードも、そのカードより小さいカードの 　上においてはいけない 領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Ａから領域Ｂに移動させる

5 ハノイの塔：実際にやってみよう （準備） 4 3 棒（領域）Ａ 棒（領域）B 棒（領域）C 一度に、一番上の1枚だけ移動できる ● ゴール 4 × 3 ● 2 × 1 ・ 一度に、一番上の1枚だけ移動できる どのカードも、そのカードより小さいカードの 　上においてはいけない 領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Ａから領域Ｂに移動させる

ハノイの塔：実際にやってみよう （まずは2枚から） 棒（領域）Ａ 棒（領域）B 棒（領域）C 2 × 1 ・ 一度に、一番上の1枚だけ移動できる どのカードも、そのカードより小さいカードの 　上においてはいけない 領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Ａから領域Ｂに移動させる

ハノイの塔：実際にやってみよう （まずは2枚から） 棒（領域）Ａ 棒（領域）B 棒（領域）C スタート 2 × 1 ・ 一度に、一番上の1枚だけ移動できる どのカードも、そのカードより小さいカードの 　上においてはいけない 領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Ａから領域Ｂに移動させる

ハノイの塔：実際にやってみよう （まずは2枚から） 棒（領域）Ａ 棒（領域）B 棒（領域）C AからCへ 移動 2をBに移動させ るにまず、 その上の1を Cに移動させる 2 × 1 ・ 一度に、一番上の1枚だけ移動できる どのカードも、そのカードより小さいカードの 　上においてはいけない 領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Ａから領域Ｂに移動させる

ハノイの塔：実際にやってみよう （まずは2枚から） 棒（領域）Ａ 棒（領域）B 棒（領域）C AからBへ 移動 一番下の2を Bに移動させた 2 × 1 ・ 一度に、一番上の1枚だけ移動できる どのカードも、そのカードより小さいカードの 　上においてはいけない 領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Ａから領域Ｂに移動させる

ハノイの塔：実際にやってみよう （まずは2枚から） 棒（領域）Ａ 棒（領域）B 棒（領域）C CからAへ 移動 Cに退避して いた1を Bに移動させた ゴール！ 2 × 1 ・ 一度に、一番上の1枚だけ移動できる どのカードも、そのカードより小さいカードの 　上においてはいけない 領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Ａから領域Ｂに移動させる

ハノイの塔：実際にやってみよう （つぎは3枚） 棒（領域）Ａ 棒（領域）B 棒（領域）C 3 ● 2 × 1 ・ 実際にやってみよう

ハノイの塔：実際にやってみよう 4 実際にやってみよう ゴールがBかCかは あまり気にせず、4枚、5枚、、、 3 棒（領域）Ａ 棒（領域）B × 3 ● 2 × 1 ・ 実際にやってみよう ゴールがBかCかは あまり気にせず、4枚、5枚、、、

ハノイの塔：解き方 棒（領域）Ａ 棒（領域）B 棒（領域）C 4 × 3 ● 2 × 1 ・ この水色の山をBに動かすには

ハノイの塔：解き方 4 この水色の山をBに動かすには、 まずその上の紫を 3 棒（領域）Ａ 棒（領域）B 棒（領域）C 2 × 1 ● × ・ この水色の山をBに動かすには、 まずその上の紫を

ハノイの塔：解き方 4 この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 3 棒（領域）Ａ 棒（領域）B 棒（領域）C 2 × 3 ● 2 × 1 ・ この水色の山をBに動かすには、 まずその上の紫をCに「移動」して

ハノイの塔：解き方 4 この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし 3 棒（領域）Ａ 棒（領域）B × 3 ● 2 × 1 ・ この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし

ハノイの塔：解き方 4 この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし Cに退避した部分をBに「移動」 棒（領域）Ａ 棒（領域）B 棒（領域）C 4 × 3 ● 2 × 1 ・ この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし Cに退避した部分をBに「移動」

ハノイの塔：プログラム 4 この水色の山をBに動かすには hanoi( 4, “棒A”, “棒B”, “棒C”) 3 棒（領域）Ａ × 3 ● 2 × 1 ・ この水色の山をBに動かすには hanoi( 4, “棒A”, “棒B”, “棒C”)

ハノイの塔：プログラム 4 この水色の山をBに動かすには、 まずその上の紫を hanoi( 3, “棒A”, “棒C”, “棒B”) 3 棒（領域）Ａ 棒（領域）B 棒（領域）C 4 × 3 ● 2 × 1 ・ この水色の山をBに動かすには、 まずその上の紫を hanoi( 3, “棒A”, “棒C”, “棒B”)

ハノイの塔：プログラム 4 この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 棒（領域）Ａ 棒（領域）B 棒（領域）C 4 × 3 ● 2 × 1 ・ この水色の山をBに動かすには、 まずその上の紫をCに「移動」して hanoi( 3, “棒A”, “棒C”, “棒B”);

ハノイの塔：プログラム 4 この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし 棒（領域）Ａ 棒（領域）B 棒（領域）C 4 × 3 ● 2 × 1 ・ この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし hanoi( 3, “棒A”, “棒C”, “棒B”); move(“棒A”, “棒B”);

ハノイの塔：プログラム 4 この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし 棒（領域）Ａ 棒（領域）B 棒（領域）C 4 × 3 ● 2 × 1 ・ この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし Cに退避した部分をBに「移動」 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); } 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”

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(3, “棒A”, “棒B”, “棒C”) ゴールのイメージ 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(2, “棒A”, “棒C”, “棒B”) ゴールのイメージ 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(2, “棒A”, “棒C”, “棒B”) ゴールのイメージ 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(1, “棒A”, “棒B”, “棒C”) ゴールのイメージ 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(1, “棒A”, “棒B”, “棒C”) ゴールのイメージ hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C hanoi(0, “棒A”, “棒C”, “棒B”) 円盤数が0なので、 何もしないで戻る 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒A”, “棒B”, “棒C”) move(“棒A”, “棒B”) 「棒Aから棒Bへ移動」 hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C 棒A 棒B 棒C hanoi(0, “棒C”, “棒B”, “棒A”) 円盤数が0なので、 何もしないで戻る

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) move(“棒A”, “棒C”) 「棒Aから棒Cへ移動」 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒B”, “棒C”, “棒A”) ゴールのイメージ hanoi(1, “棒B”, “棒C”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒B”, “棒C”, “棒A”) ゴールのイメージ hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 1 src 棒B work 棒A hanoi(1, “棒B”, “棒C”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 1 src 棒B work 棒A hanoi(1, “棒B”, “棒C”, “棒A”) hanoi(0, “棒B”, “棒A”, “棒C”) 円盤数が0なので、 何もしないで戻る 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) move(“棒B”, “棒C”) 「棒Bから棒Cへ移動」 hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 1 src 棒B work 棒A hanoi(1, “棒B”, “棒C”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 1 src 棒B work 棒A hanoi(1, “棒B”, “棒C”, “棒A”) 棒A 棒B 棒C hanoi(0, “棒A”, “棒C”, “棒B”) 円盤数が0なので、 何もしないで戻る

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 1 src 棒B work 棒A hanoi(1, “棒B”, “棒C”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒A”, “棒C”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒C を使って 移動 2 src 棒A work 棒B hanoi(2, “棒A”, “棒C”, “棒B”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C move(“棒A”, “棒B”) 「棒Aから棒Bへ移動」 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(2, “棒C”, “棒B”, “棒A”) ゴールのイメージ 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(2, “棒C”, “棒B”, “棒A”) ゴールのイメージ 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒C”, “棒A”, “棒B”) hanoi(1, “棒C”, “棒A”, “棒B”) ゴールのイメージ 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒C”, “棒A”, “棒B”) hanoi(1, “棒C”, “棒A”, “棒B”) ゴールのイメージ hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒A を使って 移動 1 src 棒C work 棒B 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒C”, “棒A”, “棒B”) hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒A を使って 移動 1 src 棒C work 棒B hanoi(0, “棒C”, “棒B”, “棒A”) 円盤数が0なので、 何もしないで戻る 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒C”, “棒A”, “棒B”) move(“棒C”, “棒A”) 「棒Cから棒Aへ移動」 hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒A を使って 移動 1 src 棒C work 棒B 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒C”, “棒A”, “棒B”) hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒A を使って 移動 1 src 棒C work 棒B 棒A 棒B 棒C hanoi(0, “棒B”, “棒A”, “棒C”) 円盤数が0なので、 何もしないで戻る

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒C”, “棒A”, “棒B”) hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒A を使って 移動 1 src 棒C work 棒B 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) move(“棒C”, “棒B”) 「棒Cから棒Bへ移動」 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒A”, “棒B”, “棒C”) ゴールのイメージ hanoi(1, “棒A”, “棒B”, “棒C”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒A”, “棒B”, “棒C”) ゴールのイメージ hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C hanoi(1, “棒A”, “棒B”, “棒C”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(0, “棒A”, “棒C”, “棒B”) 円盤数が0なので、 何もしないで戻る 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) move(“棒A”, “棒B”) 「棒Aから棒Bへ移動」 hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C hanoi(1, “棒A”, “棒B”, “棒C”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C hanoi(1, “棒A”, “棒B”, “棒C”) 棒A 棒B 棒C hanoi(0, “棒C”, “棒B”, “棒A”) 円盤数が0なので、 何もしないで戻る

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 1 src 棒A work 棒C hanoi(1, “棒A”, “棒B”, “棒C”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C hanoi(2, “棒C”, “棒B”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 2 src 棒C work 棒A hanoi(2, “棒C”, “棒B”, “棒A”) 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C 棒A 棒B 棒C

ハノイの塔：実行の様子 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); hanoi(3, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk から 枚の円盤を へ dst 棒B を使って 移動 3 src 棒A work 棒C 完了：呼び出し元（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 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) mn = 2n-1 ハノイの塔：移動回数 円盤を目にもとまらぬ早業（1秒間に100億回） で移動させたら… 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