アルゴリズムとデータ構造 補足資料9-1 「ハノイの塔」

Presentation on theme: "アルゴリズムとデータ構造 補足資料9-1 「ハノイの塔」"— Presentation transcript:

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

2 ハノイの塔

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29 ハノイの塔：プログラム 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”);

30 ハノイの塔：プログラム 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); }

31 おっと、その前に ゴミは必ず、各自持ち帰ってください。

32 ハノイの塔：プログラム 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”

33 ハノイの塔：プログラム 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”

34 ハノイの塔：プログラム 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”

35 ハノイの塔：プログラム 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”

36 ハノイの塔：プログラム 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”

37 ハノイの塔：プログラム 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”

38 ハノイの塔：プログラム 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”

39 ハノイの塔：実行の様子 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

40 ハノイの塔：実行の様子 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

41 ハノイの塔：実行の様子 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

42 ハノイの塔：実行の様子 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

43 ハノイの塔：実行の様子 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

44 ハノイの塔：実行の様子 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

45 ハノイの塔：実行の様子 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

46 ハノイの塔：実行の様子 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

47 ハノイの塔：実行の様子 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

48 ハノイの塔：実行の様子 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

49 ハノイの塔：実行の様子 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

50 ハノイの塔：実行の様子 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なので、 何もしないで戻る

51 ハノイの塔：実行の様子 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

52 ハノイの塔：実行の様子 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

53 ハノイの塔：実行の様子 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

54 ハノイの塔：実行の様子 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

55 ハノイの塔：実行の様子 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

56 ハノイの塔：実行の様子 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

57 ハノイの塔：実行の様子 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

58 ハノイの塔：実行の様子 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なので、 何もしないで戻る

59 ハノイの塔：実行の様子 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

60 ハノイの塔：実行の様子 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

61 ハノイの塔：実行の様子 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

62 ハノイの塔：実行の様子 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

63 ハノイの塔：実行の様子 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

64 ハノイの塔：実行の様子 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

65 ハノイの塔：実行の様子 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

66 ハノイの塔：実行の様子 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

67 ハノイの塔：実行の様子 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

68 ハノイの塔：実行の様子 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

69 ハノイの塔：実行の様子 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

70 ハノイの塔：実行の様子 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

71 ハノイの塔：実行の様子 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

72 ハノイの塔：実行の様子 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なので、 何もしないで戻る

73 ハノイの塔：実行の様子 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

74 ハノイの塔：実行の様子 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

75 ハノイの塔：実行の様子 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

76 ハノイの塔：実行の様子 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

77 ハノイの塔：実行の様子 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

78 ハノイの塔：実行の様子 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

79 ハノイの塔：実行の様子 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

80 ハノイの塔：実行の様子 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

81 ハノイの塔：実行の様子 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なので、 何もしないで戻る

82 ハノイの塔：実行の様子 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

83 ハノイの塔：実行の様子 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

84 ハノイの塔：実行の様子 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

85 ハノイの塔：実行の様子 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

86 ハノイの塔：実行の様子 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

87 ハノイの塔：移動回数 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と置く

88 ハノイの塔：移動回数 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と置く

89 ハノイの塔：移動回数 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

90 ハノイの塔：移動回数 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

91 ハノイの塔：移動回数 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

92 ハノイの塔：移動回数 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

93 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