人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

http://q.hatena.ne.jp/1189233802
の解を得るためのアプローチとしてプログラムを作成して実際に数字を列挙して該当するものをピックアップするプログラムを作成しようと考えました。
しかし、10個のカード(作りやすくするため0?9)の並べ方を全て列挙する場合
ループを使って書き出すのは簡単にできたのですがこれを再帰構造を用いて実現したいです。
どのようにすればよいでしょうか?
使用言語はC言語とさせてください。


●質問者: castiron
●カテゴリ:学習・教育 趣味・スポーツ
✍キーワード:C言語 アプローチ カード ピックアップ プログラム
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● mj99
●35ポイント

配列にカードが入っていて、それを入れ替える方法で作ってみました。

#include <stdio.h>
#include <memory.h>

void main();
void shuffle(int*, int);
void proc(const int*);

#define COUNT 10 // カードの枚数

void main()
{
 int i;
 int c[COUNT];

 /* カード初期化(1?の連番)*/
 for(i = 0; i < COUNT; i++) {
 c[i] = i + 1;
 }

 /* 実行 */
 shuffle(c, 0);
}

/* カード入替処理 */
void shuffle(int* c, int v)
{
 int i, w;

 /* レベルが最深なら復帰 */
 if(v+1 == COUNT) {
 proc(c); // カード出力処理
 return ;
 }
 
 /* 入替無しで再帰 */
 shuffle(c, v+1); 

 /* カードを一箇所入れ替えて再帰 */
 w = c[v];
 for(i = v+1; i < COUNT; i++) {
 c[v] = c[i]; c[i] = w; // 入れ替える
 shuffle(c, v+1);
 c[i] = c[v]; c[v] = w; // 元にもどす
 }
}

/* カード出力処理 */
void proc(const int* c)
{
 static int n = 1; // 行番号
 int i;

 printf("%10d:\t", n++);
 for(i = 0; i < COUNT; i++) {
 printf("%d", c[i]);
 printf("%c",(i+1)!=COUNT?'\t':'\n'); 
 }
}


カード10枚の処理をテキストに出力(3628800行)

ファイルサイズ:120MB

処理時間:30秒


----

簡単にロジックを書いておきます。

下記はカードが4枚の場合


レベル0:一桁目(各パターンに対してレベル1を実行)

(0):1,2,3,4(入替なし)

(1):2,1,3,4(1と2を入替)

(2):3,2,1,4(1と3を入替)

(3):4,2,3,1(1と4を入替)


レベル1:二桁目(各パターンに対してレベル2を実行)

(0-0):1,2,3,4(入替なし)

(0-1):1,3,2,4(2と3を入替)

(0-2):1,4,3,2(2と4を入替)


レベル2:三桁目(各パターンに対してレベル3を実行)

(0-0-0):1,2,3,4(入替なし)

(0-0-1):1,2,4,3(3と4を入替)


レベル3:四桁目(各パターンに対して出力処理)

(0-0-0-0):1,2,3,4(入替なし)


2 ● Mug
●35ポイント

再帰呼び出しで作ってみました。

私も再帰なら樹形図だろ?と思いました。

(以下で約10秒でした。)

#include <stdio.h>

void main();
void calc(int cards, int fixedSize, char used);
void check(int cards[]);


#define size 10

/* メイン */
void main() {
int cards[size]; // 数値の入れ物
char used[size]; // 数値が使用済みかどうか
int i;
/* 初期化 */
for(i = 0; i < size; i++) {
cards[i] = -1; // 別に3や8などでもよい(fixedSizeがあるから)
used[i] = 0; // 未使用(0)にセット
}
calc(cards, 0, used);
}

/* 再帰関数 */
void calc(int cards, int fixedSize, char used) {
int i;
if(fixedSize < size) {
for(i = 0; i < size; i++) { // 0から9までで
if(used[i] == 0) { // その数字が未使用なら
used[i] = 1; // 使用済みにして
cards[fixedSize] = i; // その数字を代入して
calc(cards, (fixedSize + 1), used); // 次の桁について再帰
used[i] = 0; // 終わったらその数字を未使用に戻す
}
}
} else {
check(cards); // 全桁確定してたらチェック
}
}

/* チェック */
void check(int cards[]) {
static int n = 1; // 行番号
int i;
printf("%d\t", n++);
for(i = 0; i < size; i++) {
printf("%d", cards[i]);
}
printf("\n");
}

【考え方】

(1)長さ10の配列cardsを用意し、ここには数字を重複しないように入れます。

添字0から9まで全てに有効な数字が入ったら、それが並び替えパターンの1つを表します。

(2)再帰関数は、(1)の配列cardsのうち、f個(つまり添字(f-1)まで)に有効な数字が入っている状態で呼ばれたなら、それ以前(添字0から(f-1))と重複しない数字についてループ(=樹形図の分岐)します。

その配列cardsの(f+1)番目(添字f)に対してループさせた数字を代入し、再帰呼び出しします。

例えば、配列cardsが[5,2,3,0,1,7,4,未確定,未確定,未確定]の状態で再帰関数を実行したならば、6,8,9について3回ループし、1周目では[5,2,3,0,1,7,4,6,未確定,未確定]、2周目では[5,2,3,0,1,7,4,8,未確定,未確定]、3周目では[5,2,3,0,1,7,4,9,未確定,未確定]として再帰します。

(3)(2)でいう重複しない数字を見つけるために、配列の確定している部分について毎回ループするのはコスト増なので、「この数字は使われているかどうか」配列usedを別に用意します。

例えば(2)の配列cardsが[5,2,3,0,1,7,4,未確定,未確定,未確定]のとき、usedは[1,1,1,1,1,1,0,1,0,0]となっています。

なので、樹形図の分岐をするためには、usedについてループをしつつ、未使用である数字のときに再帰すればよいことになります。


【イメージ】

樹形図は、根元は10分岐,次は9分岐,8分岐・・・最後は1分岐のイメージです。

(途中から)
└[6,9,1,0,3]
├[6,9,1,0,3,2]
│├[6,9,1,0,3,2,4]
││├[6,9,1,0,3,2,4,5]
│││├[6,9,1,0,3,2,4,5,7]
││││└[6,9,1,0,3,2,4,5,7,8]
│││└[6,9,1,0,3,2,4,5,8]
│││ └[6,9,1,0,3,2,4,5,8,7]
││├[6,9,1,0,3,2,4,7]
│││└(以下省略)
││└[6,9,1,0,3,2,4,8]
││ └(以下省略)
│├[6,9,1,0,3,2,5] ↓ここから下も省略
│├[6,9,1,0,3,2,7]
│└[6,9,1,0,3,2,8]
├[6,9,1,0,3,4]
├[6,9,1,0,3,5]
├[6,9,1,0,3,7]
└[6,9,1,0,3,8]


【感想】

もともとはJAVAで書き、Cで作り直すのに苦労しました。

Cは初心者レベルなので書き方・定義の仕方・使い方などがおかしい部分があるかも知れません。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ