ハノイの塔

[BlueRose]

　n枚の円盤からなるハノイの塔のパズルを解くプログラムを再帰的プログラムで尚且つ円盤を移動する処理関数（honoi関数とする）を引数3つ(上からk枚の円盤, 始めに円盤が挿さっている棒from, 次の移動先の棒to)で実現するやり方のヒントを教えて下さい。
以下のコードは途中まで出来たものです。円盤の枚数は動的に当てはめていくので、棒from, toをどう定義していけばよいのか...。

コード:

#include <stdio.h>

/* プロトタイプ宣言 */
void hanoi(int, int, int);

/* メイン処理 */
int main(){
  int n; //円盤の枚数
  int from, to; //円盤が挿入されている棒、次の移動先の棒

  printf("円盤の枚数 = ");
  scanf("%d", &n);

  hanoi(n, from, to);


  return 0;
}

/* ハノイの塔を解く関数 */
void hanoi(int k, int from, int to){
  int other; //from, to以外の棒

  other = 6 - from - to;
  if(k == 1){
    printf("棒 from の 1 番上の円盤を棒 to へ移動\n");
  }
  if(k > 1){
    hanoi(k-1, from, other);
  }
  if(k > 1){
    hanoi(1, from, to);
    printf("棒 %d から棒 %d へ移動\n", from, to);
  }
  if(k > 1){
    hanoi(k-1, other, to);
  }
}

[かずま]

コード:

void hanoi(int n, int from, int to)
{
	枚数が 0枚なら、何もしないで戻る
	int other = 6 - from - to;	// 棒の番号が 1, 2, 3 だから、その他はこれ
	k-1枚の円盤を from から other に移動
	1枚の円盤を from から to へ移動
	k-1枚の円盤を other から to に移動
}

未初期化の変数の値を引数にして関数を呼び出すのは間違っています。
main での呼び出しは、hanoi(n, 1, 3); でしょう。
プログラム全体をを書き直して貼り付けてください。
コンパイラは何ですか？

[BlueRose]

一通り修正しました。コンパイラはc言語です。環境はMacOs10.14.1です。

コード:

#include <stdio.h>

/* プロトタイプ宣言 */
void hanoi(int, int, int);

/* メイン処理 */
int main(){
  int n; //円盤の枚数

  printf("円盤の枚数 = ");
  scanf("%d", &n);

  hanoi(n, 1, 3);

  return 0;
}

/* ハノイの塔を解く関数 */
void hanoi(int k, int from, int to){
  int other = 6 - from - to; //from, to以外の棒

  if(k == 1){
    printf("棒 from の 1 番上の円盤を棒 to へ移動\n");
  }else if(k > 1){
    hanoi(k-1, from, other);
    hanoi(1, from, to);
    hanoi(k-1, other, to);
    printf("棒 %d から棒 %d へ移動\n", from, to);
  }else{
  }
}

[かずま]

一通り修正しました。コンパイラはc言語です。環境はMacOs10.14.1です。

プログラミング言語は C。
コンパイラは gcc ですね。

コード:

	枚数が 0枚なら、何もしないで戻る
	if (k == 0) return;

	k-1枚の円盤を from から other に移動
	hanod(k - 1, from, other);

	1枚の円盤を from から to へ移動
	printf("棒%d から棒%d へ移動", from, to)

n = 3 の時の実行結果を貼り付けてください。

[かずま]

コード:

   1         2         3

   H         |         |
  HHH        |         |
 HHHHH       |         |
 -------------------------

   |         |         |
  HHH        |         |
 HHHHH       |         H
 -------------------------

   |         |         |
   |         |         |
 HHHHH      HHH        H
 -------------------------

   |         |         |
   |         H         |
 HHHHH      HHH        |
 -------------------------

   |         |         |
   |         H         |
   |        HHH      HHHHH
 -------------------------

   |         |         |
   |         |         |
   H        HHH      HHHHH
 -------------------------

   |         |         |
   |         |        HHH
   H         |       HHHHH
 -------------------------

   |         |         H
   |         |        HHH
   |         |       HHHHH
 -------------------------
 

[BlueRose]

コード:

/* ハノイの塔を解く関数 */
void hanoi(int k, int from, int to){
    int other = 6 - from - to; //from, to以外の棒

    if(k == 0){
      return;
    }else{
      hanoi(k-1, from, other);
      printf("棒 %d から棒 %d へ移動\n", from, to);
    }
}

・n = 3 の時の実行結果

コード:

円盤の枚数 = 3
棒 1 から棒 3 へ移動
棒 1 から棒 2 へ移動
棒 1 から棒 3 へ移動

[かずま]

コード:

円盤の枚数 = 3
棒 1 から棒 3 へ移動
棒 1 から棒 2 へ移動
棒 1 から棒 3 へ移動

その実行結果を絵にすると、

コード:

   1         2         3

   H         |         |
  HHH        |         |
 HHHHH       |         |
 -------------------------

棒1 から棒3 へ移動
   |         |         |
  HHH        |         |
 HHHHH       |         H
 -------------------------

棒1 から棒2 へ移動
   |         |         |
   |         |         |
 HHHHH      HHH        H
 -------------------------

棒1 から棒3 へ移動
   |         |         |
   |         |       HHHHH
   |        HHH        H
 -------------------------

n = 3 の時、#5 のように移動は 7回です。
#2 のヒントをもう一度よく見てください。

[BlueRose]

コード:

/* ハノイの塔を解く関数 */
void hanoi(int k, int from, int to){
    int other = 6 - from - to; //from, to以外の棒

    if(k == 0){
      return;
    }else{
      hanoi(k-1, from, other);
      hanoi(1, from, to);
      hanoi(k-1, other, to);
      printf("棒 %d から棒 %d へ移動\n", from, to);//(1)
    }
    
}

(1)のprintf文はどこに挿入すれば良いでしょうか。
実行すると

コード:

円盤の枚数 = 3
Segmentation fault: 11

が表示されてしまいます...。

[かずま]

1枚の円盤の移動は、hanoi関数の呼び出しではなく、printfで表示するだけです。

[BlueRose]

コード:

/* ハノイの塔を解く関数 */
void hanoi(int n, int from, int to){
    int other = 6 - from - to; //from, to以外の棒

    if(n == 0)return;
    if(n > 1)
      hanoi(n-1, from, other);
    if(n > 1)
      hanoi(1, from, to);
      printf("棒 %d から棒 %d へ移動\n", from, to);
    if(n > 1)
      hanoi(n-1, other, to);
}

実行すると

コード:

円盤の枚数 = 3
棒 1 から棒 3 へ移動
棒 1 から棒 2 へ移動
棒 1 から棒 2 へ移動
棒 3 から棒 2 へ移動
棒 1 から棒 3 へ移動
棒 1 から棒 3 へ移動
棒 2 から棒 1 へ移動
棒 2 から棒 3 へ移動
棒 2 から棒 3 へ移動
棒 1 から棒 3 へ移動

と余分に出力されてしまいました...。

[かずま]

#2 と #4 の説明にタイポがありました。
k を n に、hanod を hanoi に訂正します。

#2 と #4 と #9 の説明をちゃんと読んでくれていないようなので、再掲します。

コード:

void hanoi(int n, int from, int to)
{
	枚数が 0枚なら、何もしないで戻る
	int other = 6 - from - to;	// 棒の番号が 1, 2, 3 だから、その他はこれ
	n-1枚の円盤を from から other に移動
	1枚の円盤を from から to へ移動
	n-1枚の円盤を other から to に移動
}

「n-1枚の円盤を from から other に移動」は、hanoi(n - 1, from, other);
「1枚の円盤を from から to へ移動」は、printf("棒%d から棒%d へ移動", from, to);

[かずま]

なんで、質問者が if (n > 1) を書きたがるのかと考えたら、
次のようなコードを書きたいのじゃないかと思い当たりました。

コード:

void hanoi(int n, int from, int to)
{
	int other = 6 - from - to;
	枚数 n が 1より大きければ、n-1枚の円盤を from から other に移動
	1枚の円盤を from から to へ移動
	枚数 n が 1より大きければ、n-1枚の円盤を other から to に移動
}

こちらのほうが、hanoi関数の呼び出し回数が少なくて済みますね。

[BlueRose]

コード:

void hanoi(int n, int from, int to){
  int other = 6 - from - to; //from, to以外の棒

    if(n == 0)return;
    if(n > 1)
      hanoi(n-1, from, other);
      printf("棒 %d から棒 %d へ移動\n", from, to);
    if(n > 1)
      hanoi(n-1, other, to);
}

度重なる返答ありがとうございました。
無事に解決しました。

コード:

円盤の枚数 = 3
棒 1 から棒 3 へ移動
棒 1 から棒 2 へ移動
棒 3 から棒 2 へ移動
棒 1 から棒 3 へ移動
棒 2 から棒 1 へ移動
棒 2 から棒 3 へ移動
棒 1 から棒 3 へ移動