http://q.hatena.ne.jp/1189233802

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

回答の条件
  • 1人2回まで
  • 登録:2007/09/09 21:19:59
  • 終了:2007/09/16 21:20:04

回答(2件)

id:mj99 No.1

mj99回答回数138ベストアンサー獲得回数382007/09/10 19:41:16

ポイント35pt

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

#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(入替なし)

id:Mug No.2

Mug回答回数15ベストアンサー獲得回数32007/09/11 01:39:58

ポイント35pt

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

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

(以下で約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は初心者レベルなので書き方・定義の仕方・使い方などがおかしい部分があるかも知れません。

  • id:castiron
    イメージとしては樹形図なのですがどういう条件で戻ってくるのかが分からなくて
    とっかかりすらつかめていないです。
  • id:castiron
    意味のない条件だと思いますが別に3桁でも4桁でも少ない桁でもかまいません。
    後今思ったのですが今後作成した数字を偶数が5つ並んだもの、4つ並んだものを検索する予定です。
    でもこれって実現不可能な(めちゃくちゃ実行に時間がかかる)プログラムですか?
    スマートな方法だとどんな流れのプログラムになるのでしょうか?
  • id:KUROX
    再帰構造って今の時代でもスマートな書き方なのかな。

    再帰構造だとスタックつむと思うんで昔は遅くなったと
    思いますが、今のパソコンのパワーだったら大丈夫のような。
  • id:castiron
    数字を作るのは別に今の段階でも出来ているのでどうせなら再帰構造で
    簡単にできないのかなぁと思った次第です。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません