←検索窓の楽しみ方
  ショッピングモール  掲示板ランキング


【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板1こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.4368

組み合わせの列挙
投稿者---C初心者(2005/07/23 16:11:38)


はじめまして。C初心者です。
いきなり質問なのですが下のプログラムは
0から8までの中間ノードの組み合わせ(ルート)を列挙するものです。
今、考えているのはこのプログラムを改良して
中間ノードのいずれかに2や3といった特定のノードが
組み合わせられているルートだけを列挙するものを考えています。
アドバイス、参考プログラムなどよろしくお願いします。

#include <stdio.h>

#define N  100

int main(void)
{
    int a[N], n, r, i;
       
    n = 7
          for ( r = 1 ; r <= n ; r++)
          if (n < N && r <= n) {
            for (i = 1; i <= n; i++) a[i] = i;
            do {printf(" 0 ");
                for (i = 1; i <= r; i++) 
                printf(" %d ", a[i]);
                printf(" %d\n", n+1 );
            } while (next_perm(a, n, r));
        }
        
    return 0;

}

int next_perm(int *a, int n, int r)
{
    for ( ; r > 0; r--) {
        int i = r, t = a[r];
        while (++i <= n)
            if (a[i] > t) { a[r] = a[i]; a[i] = t; return 1; }
        for (i = r; i < n; i++) a[i] = a[i+1];
        a[n] = t;
    }
    return 0;
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:組み合わせの列挙 4370 まきじ 2005/07/23 19:09:01
<子記事> Re:組み合わせの列挙 4371 アンドロオイド 2005/07/23 21:16:48
<子記事> Re:組み合わせの列挙 4386 C初心者 2005/07/27 12:48:24


No.4370

Re:組み合わせの列挙
投稿者---まきじ(2005/07/23 19:09:01)


>do{ } while (next_perm(a, n, r));

の前に、列挙したい条件に一致する場合に、フラグを、ON/OFF する様な
処理を入れれば良いと思います。

2、3 が含まれるルートを列挙するのであれば、a[i] に 2 あるいは 3 が
あればフラグを ON にする。

# next_perm() を、工夫すればより効率的にできるかも知れませんが・・
# 私には、解りません。


この投稿にコメントする

削除パスワード

No.4373

Re:組み合わせの列挙
投稿者---C初心者(2005/07/23 21:33:44)


それはif文でいけますか?
確かにnext_permをいじったほうが良さそう
なのですが、どういじればよいのか私も分からないので…



この投稿にコメントする

削除パスワード

No.4374

Re:組み合わせの列挙
投稿者---まきじ(2005/07/23 22:05:44)


>それはif文でいけますか?

if 文 と変数ひとつを追記すれば良いと思います。
# 私は、それで一応できました。


この投稿にコメントする

削除パスワード

No.4377

Re:組み合わせの列挙
投稿者---C初心者(2005/07/24 03:54:59)


自分もif文でいろいろ試してみたのですが
上手くいきません。
もしよければ、まきじさんの作った
プログラムをのせて頂けないでしょうか。
よろしくお願いします。



この投稿にコメントする

削除パスワード

No.4380

Re:組み合わせの列挙
投稿者---まきじ(2005/07/24 11:47:53)


>プログラムをのせて頂けないでしょうか。

for (i = 1; i <= n; i++) if(a[i] == 2 || a[i] == 3) flg = 1;

を追記して、flg が 1 の時は、表示する様にしました。


この投稿にコメントする

削除パスワード

No.4382

Re:組み合わせの列挙
投稿者---C初心者(2005/07/24 14:32:44)


>for (i = 1; i <= n; i++) if(a[i] == 2 || a[i] == 3) flg = 1;
できました!!
ifの後にflgの変数で判断したり、
for文を前につけたり思いつかなかったです。
こうやって見るとなるほどと思うことはできても
思いつかないのでまだまだダメですね。
ホントにお世話になりました。ありがとうございます。


この投稿にコメントする

削除パスワード

No.4371

Re:組み合わせの列挙
投稿者---アンドロオイド(2005/07/23 21:16:48)


next_permが何者かはわからないが、
名前からすると順列を求める関数のようですね。

求めたいのは組合せ、それとも順列?


この投稿にコメントする

削除パスワード

No.4372

Re:組み合わせの列挙
投稿者---C初心者(2005/07/23 21:29:34)


求めたいのは組み合わせです。
名前は自分が意味が分かる程度にしかつけてないので
分かりにくかったと思います。
すみません。


この投稿にコメントする

削除パスワード

No.4375

Re:組み合わせの列挙
投稿者---まきじ(2005/07/23 22:12:53)


>求めたいのは組み合わせです。

0 から 8 間の、ルートなので、1 から 7 の並び方が
いくつあるか、ということだと思います。
だから、組み合わせ(nCr) ではなく 順列(nPr) の用な気がしまが?
7P1 から 7P7 まで、全通り求めてるのではないでしょうか?


この投稿にコメントする

削除パスワード

No.4378

Re:組み合わせの列挙
投稿者---C初心者(2005/07/24 04:01:24)


順列は例えば
1 4 7 という並びがあれば
7 4 1 や 1 7 4 はダメですよね?
組み合わせの考えでいくと
上の3パターンは全て違うものと判断すると思います。
なので組み合わせを考えると思っていましたが
逆に憶えていたでしょうか??
間違えてたらすみません。


この投稿にコメントする

削除パスワード

No.4379

Re:組み合わせの列挙
投稿者---まきじ(2005/07/24 11:43:45)


>1 4 7 という並びがあれば
>7 4 1 や 1 7 4 はダメですよね?

は、組み合わせです。

>逆に憶えていたでしょうか??

だと思います。


この投稿にコメントする

削除パスワード

No.4381

Re:組み合わせの列挙
投稿者---C初心者(2005/07/24 14:18:01)


やっぱり逆に憶えてましたか。
ホント初歩的なことでお手数かけました。
申し訳ないです…



この投稿にコメントする

削除パスワード

No.4386

Re:組み合わせの列挙
投稿者---C初心者(2005/07/27 12:48:24)


すみません。下のnext_perm(int *a, int n, int r)を
いじるほうでできないでしょうか。
できればソースを載せてもらえればと思います。
蒸し返すような質問ですみません。
よろしくお願いします。

<pre>
int next_perm(int *a, int n, int r)
{
for ( ; r > 0; r--) {
int i = r, t = a[r];
while (++i <= n)
if (a[i] > t) { a[r] = a[i]; a[i] = t; return 1; }
for (i = r; i < n; i++) a[i] = a[i+1];
a[n] = t;
}
return 0;
}
</pre>



この投稿にコメントする

削除パスワード

No.4387

Re:組み合わせの列挙
投稿者---まきじ(2005/07/27 22:41:26)


>すみません。下のnext_perm(int *a, int n, int r)を
>いじるほうでできないでしょうか。
>できればソースを載せてもらえればと思います。

単純に、
>for (i = 1; i <= n; i++) if(a[i] == 2 || a[i] == 3) flg = 1;
を next_perm() でやっても、main() やるのと変わらない。

私は、next_perm() のアルゴリズム自体を変えて、全件をチェックせずに
済む方法があるかも知れないと思いました。

組み合わせを求める段階で、条件に一致する数値がでてきたら
その組み合わせは以降、計算しないみたいな感じ。

# バックトラック法 かな・・・
# 私は、それをコーディングする力はありません。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧




掲示板提供:Real Integrity