質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.33%

ハノイの塔の実装方法

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 4,387
退会済みユーザー

退会済みユーザー

ハノイの塔の実装方法がわからず困っています。
https://p--q.blogspot.jp/2014/06/python13.html
のリンクの通りコードを書くと

# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
    if n == 1:
        print("{}→{}".format(x, y))
    else:
        hanoi(n-1, x, z, y)
        print("{}→{}".format(x, y))
        hanoi(n-1, z, y, x)

print(hanoi(3, "A", "C", "B"))


で、このファイルを実装すると

 A→C
 A→B
 C→B
 A→C
 B→A
 B→C
 A→C


のように7回出力されます。
理解できないのが、なぜfor文やwhile文を使っていないのに
この場合、

else:
        hanoi(n-1, x, z, y)
        print("{}→{}".format(x, y))
        hanoi(n-1, z, y, x)


が何回も呼ばれるのかということです。
http://www13.plala.or.jp/kymats/study/C++/Hanoi/Hanoi.html
のURLを見ると
#####
n-1 枚の円盤を棒Aから棒Bへ移動する場合と
棒Bから棒Aへ移動する場合は交互に訪れる。
#####
という部分を実装しているとは思うのですが、
このリンクのサイトの図の
■3枚の円盤を移動する手順
のどの部分が#####で囲った説明を表現しているのかもわかりません。
なぜ hanoiメソッドで表現されるシンプルなコードでハノイの塔が実装できるのでしょうか?

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • 退会済みユーザー

    2017/07/07 11:34

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 3

checkベストアンサー

+1

hanoi(3, "A", "C", "B")
    // 3 != 1:  goto else
    hanoi(2, "A", "B", "C")
    |   // 2 != 1:  goto else
    |   hanoi(1, "A", "C", "B")
    |   |   // 1 == 1:  goto if
    |   |   print("A -> C")         // A -> C
    |   print("A -> B")             // A -> B
    |   hanoi(1, "C", "B", "A")
    |   |   // 1 == 1:  goto if
    |   |   print("C -> B")         // C -> B
    print("A -> C")                 // A -> C
    hanoi(2, "B", "C", "A")
    |   // 2 != 1:  goto else
    |   hanoi(1, "B", "A", "C")
    |   |   // 1 == 1:  goto if
    |   |   print("B -> A")         // B -> A
    |   print("B -> C")             // B -> C
    |   hanoi(1, "A", "C", "B")
    |   |   // 1 == 1:  goto if
    |   |   print("A -> C")         // A -> C

なぜ hanoiメソッドで表現されるシンプルなコードでハノイの塔が実装できるのでしょうか?

解法自体が単純なルールで表現できるからです.

  1. スタートにあるn枚のうち,上からn-1枚を「なんとかして」一時領域に移す(n == 1の時は何もしない)
  2. スタートに残ったものをゴールに移す
  3. すでにゴールにある円盤は無視していい(この先ゴールにある円盤より大きい円盤を動かすことはない)ので,残った n-1 枚を移動する問題と考えて手続き 1 に戻る

コードと照らし合わせると,2つのprint文が手続き 2,else句の一度目の再帰が「なんとかして」部分,二度目の再帰が手続き 3 に相当するはずです.

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/07 13:35

    ありがとうございます。ハノイの塔の仕組みが理解できました!
    何点か質問がありまして、
    3.一時領域をスタート,スタートを一時領域として(役割を交換して),1に戻る
    に関してですが、スタート,スタートを一時領域 とはどういう意味でしょうか?
    また、1.スタートにあるn枚のうち,上からn-1枚を一時領域に移す ですが
    1のプロセスでn-1枚の全部を一時領域に移すのも何プロセスかありますよね?そのため、else:
    の中で、hanoi(n-1, x, z, y)・hanoi(n-1, z, y, x)と呼び出しているということなのでしょうか?

    キャンセル

  • 2017/07/07 14:41

    > スタート,スタートを一時領域 とはどういう意味でしょうか?

    基本的なハノイの塔って,場所(棒)が3つありますよね?
    スタート:最初に n 枚が置いてある場所(質問文中では棒A)
    ゴール:最終的に移動したい場所(質問文中では棒C)
    一時領域:スタートでもゴールでもない場所(質問文中では棒B)

    目的はスタートからゴールに全ての円盤を移すことですが,「小さい円盤の上には大きい円盤を置けない」という制約から,どうしても一時的に円盤を待避しておく場所(一時領域)が必要になります.

    > 1のプロセスでn-1枚の全部を一時領域に移すのも何プロセスかありますよね?そのため、else:
    の中で、hanoi(n-1, x, z, y)・hanoi(n-1, z, y, x)と呼び出しているということなのでしょうか?

    そうです.
    ここの部分,少し記述を修正します.

    キャンセル

0

再起呼び出しをしているからです。
実行をトレースしてみてください。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/07 10:24

    再起呼び出しをしているのはわかります。
    ただ、else: 文の中の
    hanoi(n-1, x, z, y) と hanoi(n-1, z, y, x) の引数が変わっているのが理解できなくて。最初のhanoiメソッドでは x, z, y と引数を渡しているのに、2番目のhanoiメソッドでは z, y, x と引数を渡していてなぜその順番が変わっているのでしょうか?

    キャンセル

  • 2017/07/07 10:30

    ハノイの塔のアルゴリズムがわかっているならわかるはず。わからないなら調べましょう。

    キャンセル

0

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.33%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る