5

再帰を使用してハノイの塔を解くための Java コードを次に示します。

/**here is a stack of N disks on the first of three poles (call
them A, B and C) and your job is to move the disks from pole A to pole B without
ever putting a larger disk on top of a smaller disk.*/ 

public class Hanoi {

    public static void main(String[] args) {
        playHanoi (2,"A","B","C");
    }

    //move n disks from position "from" to "to" via "other"
    private static void playHanoi(int n, String from , String other, String to) {
        if (n == 0)
            return;
        if (n > 0)
        playHanoi(n-1, from, to, other);
        System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);
        playHanoi(n-1, other, from, to);
    }

}

印刷方法をどこに置くかは重要ですか? また、私はこのようにすることができます：

    playHanoi(n-1, from, to, other);
    playHanoi(n-1, other, from, to);
    System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);
4

2 に答える 2

11

このように問題を解決Tower of Hanoyすることは、仕事をどのように成し遂げたいかという戦略を定義することに他なりません。そしてあなたのコード：

    playHanoi(n-1, from, to, other);
    System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);
    playHanoi(n-1, other, from, to);

基本的に、次のように戦略を定義します。

  1. n-1 個のディスクを「from」 (ソース タワー) から「other」 (中間タワー)に移動します。
  2. 次に、n番目のディスクを「from」 (ソース タワー) から「to」 (宛先タワー) に移動します。
  3. 最後に、n-1 個のディスクを"other" (中間タワー) から"to" (宛先タワー) に移動します。

あなたprinfは基本的に2番目のステップを行います。

次のようなコードを記述した場合:

    playHanoi(n-1, from, to, other);
    playHanoi(n-1, other, from, to);
    System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);

それからあなたは基本的にやっています：

  1. n-1 個のディスクを「from」 (ソース タワー) から「other」 (中間タワー)に移動します。

  2. 次に、n-1 個のディスクを"other" (中間タワー) から"to" (宛先タワー) に移動します。

  3. 最後に、n番目のディスクを「from」 (ソース タワー) から「to」 (宛先タワー) に移動します。

    この戦略では、2番目のステップ ( n-1 個のディスクすべて を"other"から"to" に移動) を実行した後、3番目のステップ ( n番目のディスクを"from" から " to " に移動) が無効になります! Tower of Hanoy大きなディスクを小さなディスクの上に置くことはできないからです！

したがって、2 番目のオプション (戦略) を選択すると、無効な戦略につながるため、それを行うことはできません!

于 2013-05-11T04:08:13.053 に答える
1

それは確かに重要です。再帰呼び出しの後のすべては、その再帰が巻き戻された後に実行されるため (およびその前のすべて)、出力が無意味な順序になっていることに気付く場合があります。

関数呼び出しの後のステートメントは、関数が戻るまで実行されないことに注意してください。

于 2013-05-11T03:46:56.817 に答える