ハノイの塔

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: ハノイの塔

Re: ハノイの塔

#13

by BlueRose » 6年前

コード: 

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 へ移動

Re: ハノイの塔

#12

by かずま » 6年前

なんで、質問者が 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関数の呼び出し回数が少なくて済みますね。

Re: ハノイの塔

#11

by かずま » 6年前

#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);

Re: ハノイの塔

#10

by BlueRose » 6年前

コード: 

/* ハノイの塔を解く関数 */
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 へ移動
と余分に出力されてしまいました...。

Re: ハノイの塔

#9

by かずま » 6年前

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

Re: ハノイの塔

#8

by BlueRose » 6年前

コード: 

/* ハノイの塔を解く関数 */
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
が表示されてしまいます...。

Re: ハノイの塔

#7

by かずま » 6年前

BlueRose さんが書きました: ↑
6年前

コード: 

円盤の枚数 = 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 のヒントをもう一度よく見てください。

Re: ハノイの塔

#6

by BlueRose » 6年前

コード: 

/* ハノイの塔を解く関数 */
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 へ移動

Re: ハノイの塔

#5

by かずま » 6年前

コード: 

   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
 -------------------------

Re: ハノイの塔

#4

by かずま » 6年前

BlueRose さんが書きました: ↑
6年前
 一通り修正しました。コンパイラは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 の時の実行結果を貼り付けてください。

Re: ハノイの塔

#3

by BlueRose » 6年前

一通り修正しました。コンパイラは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{
  }
}

Re: ハノイの塔

#2

by かずま » 6年前

コード: 

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); でしょう。
プログラム全体をを書き直して貼り付けてください。
コンパイラは何ですか？

ハノイの塔

#1

by BlueRose » 6年前

　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);
  }
}

ページトップ