• ベストアンサー

組分けをプログラムで表現するには??

例えば3人の場合、{3}、{1,2}、{1,1,1}の3組に。 5人場合、{5}、{1,4}、{2,3}、{1,1,3}、{1,2,2}、{1,1,1,2}、{1,1,1,1,1}の7組に。 人数(n=)を入力すると上のような組分けと組がいくつ出来たかを表示させるプログラム(Cか出来ればmathematicaで)を作りたいのですが、なかなか作成できません。もしよろしければアルゴリズムなど何か少しでもアドバイス頂けると幸いです。(Cの場合、上のような{●,●}をどのように表すと良いでしょうか)

質問者が選んだベストアンサー

  • ベストアンサー
  • kapura
  • ベストアンサー率50% (48/95)
回答No.3

細かい話ですが、No.2の回答の最後の文で、@[n/2]-1ではなく@[n/2]+1ですね 以下はPerlのプログラムですが参考になるでしょうか。 # 間違いというか、たまたま動作しているところがあるかも use strict; my @all = ([[1]]); # 人数iの場合の全リスト (@iと表すとする) を第i-1要素にもつ配列 (@1で初期化) my $n; # 人数 do { print "Enter the number of people: "; # 人数nを入力してもらう chomp($n = <STDIN>); } while ($n !~ /^[1-9]\d*$/); # 入力が自然数でなければ再入力 if ($n == 1) { print "{1}\n"; exit } # nが1の場合は{1}を表示してプログラム終了 (@1は{1}のみ) foreach my $i (2..$n) { # @iを求める (iは2からnまで順に変化させる) my @tmp; foreach (@{$all[$i-2]}) { push @tmp, [1, @$_] } $all[$i-1] = \@tmp; # @iを@i-1の左端に1をつけ加えたもので初期化 if ($i > 3) { # 既知の@i-jを利用して、@iにリストを追加する (jは2から[i/2]まで順に変化させる) foreach my $j (2..int($i/2)) { foreach (@{$all[$i-1-$j]}) { # @i-jの全リストをチェックして、左端の数がj以上であれば if ($_->[0] >= $j) { push @{$all[$i-1]}, [$j, @$_] } } } } push @{$all[$i-1]}, [$i]; # @iに{i}を追加する } foreach (@{$all[$n-1]}) { # @nの全リストを表示 print "{", join(", ", @$_), "}\n"; } print scalar @{$all[$n-1]}, " lists\n";

全文を見る
すると、全ての回答が全文表示されます。

その他の回答 (4)

  • BLUEPIXY
  • ベストアンサー率50% (3003/5914)
回答No.5

//一応作ってみました /* ある数nを分割する(正数の和で表す表し方の)数を求める 例 4:4,1+3,2+2,1+1+2,1+1+1の5通り */ #include <stdio.h> #include <stdlib.h> #include <malloc.h> int *LIST; /* 数の組み合わせのリスト */ int COUNT=0; /* 組み合わせの件数 */ int LEVEL=-1; /* 分割するレベル */ void print (void){ int i; printf("{ "); for(i=0;i<=LEVEL;i++){ printf("%d ",LIST[i]); } printf("}\n"); } void part(int n){ int i, first; /* first は、リストの最後の1個前の数値 */ if(n<1) return ; // LEVEL++; /* 分割する数が1増えた */ LIST[++LEVEL]=n; /* リストの最後に付け足す */ print(); /* 組み合わせを表示 */ COUNT++; /* 件数をカウント */ first=(LEVEL==0) ? 1 : LIST[LEVEL-1]; for(i=first;i<=n/2;i++){ LIST[LEVEL]=i; /* リストの最後を置き換える */ part(n-i); } LEVEL--; return; } void main(void){ int N; N=5; LIST=(int *)calloc(N, sizeof(int)); if(LIST==NULL){ fprintf(stderr, "作業メモリが確保できませんでした。\n"); exit(EXIT_FAILURE); } part(N); printf("%d通り\n", COUNT); free(LIST); exit(EXIT_SUCCESS); }

taka_o
質問者

お礼

このように丁寧なプログラムまで書いて頂きありがとうございます!感謝いたします!

全文を見る
すると、全ての回答が全文表示されます。
  • kapura
  • ベストアンサー率50% (48/95)
回答No.4

すみません。既に気付かれていると思いますが、訂正も不適切ですね。 「@nを得るには@n-1, @n-2, ..., @n-[n/2]が得られている必要がある」,{[n/2], [n/2] or [n/2]+1}は「@n-[n/2]の中で左端の数が[n/2]以上のリストの左端に[n/2]をつけ加えたもの」ですね。

taka_o
質問者

お礼

良かった、これで納得です!ありがとうございました!

全文を見る
すると、全ての回答が全文表示されます。
  • kapura
  • ベストアンサー率50% (48/95)
回答No.2

# 既に以下のようなことはわかっているのかもしれませんが・・ n人の場合の全リストを@nと表して、どのリストも昇順になっているとすると @1: {1} @2: {1, 1}, {2} @3: {1, 1, 1}, {1, 2}, {3} @4: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}, {4} @5: {1, 1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 4}, {2, 3}, {5} ... @n: {1, ...}, ..., ← @n-1のリストの左端に1をつけ加えたもの   {2, ...}, ..., ← @n-2の中で左端の数が2以上のリストの左端に2をつけ加えたもの   {3, ...}, ..., ← @n-3の中で左端の数が3以上のリストの左端に3をつけ加えたもの   ...,   {[n/2], [n/2] or [n/2]+1}, ← @[n/2]の中で左端の数が[n/2]以上のリストの左端に[n/2]をつけ加えたもの (nが偶数なら{[n/2], [n/2]}、奇数なら{[n/2], [n/2]+1})   {n} という風に見ることができるのではないでしょうか。この考え方でいけば、@nを得るのに @n-1, @n-2, ..., @[n/2]-1(, @[n/2]) が先に得られている必要があると思います ([]はガウス記号)。

taka_o
質問者

お礼

早速の回答ありがとうございます!とても参考になりそうです。

全文を見る
すると、全ての回答が全文表示されます。
  • ngsvx
  • ベストアンサー率49% (157/315)
回答No.1

思いつきです。 10の組み合わせを考えると、 10 10, 9 . . . 6, 4 6, 3, 2, 1 . . . 1,1,1,1,1,1,1,1,1,1 ですよね? つまり、最初の数はnを1まで減算していき、 それぞれに、(n-1)のパターンを加えればいいかと。 n=10のとき、減算して6まできたとすると、 6, .... ですが、...の部分は10-6=4で4の組み合わせのパターンがくればいい気がします。 4のパターンは、 4 3,1,1 2,2 1,1,1,1 ですから、これに6を付け加えて、 6,4 6,3,1,1 6,2,2 6,1,1,1,1 となります。 同じように次は先頭が5になり、10-5=5のパターンを加えていきます。 こんな感じでどうでしょうか?

taka_o
質問者

お礼

なるほど、早速の回答ありがとうございます!参考になります。

全文を見る
すると、全ての回答が全文表示されます。

関連するQ&A

  • 値によって組み分けを作成するプログラムについて

    こんにちは。 プログラミングでつまってしまったため質問させて頂きます。 プログラミング言語はC++です(visual c++ではありません)。 ■作成したいプログラム A,B,C,D,Eがある。 AとBの類似度は91% 以下同様に AとCは89% AとDは79% AとEは77% BとCは93% BとDは97% ・・・のように続いていく.. (*ABが似ている、BCが似ている。だからと言ってACが似ているとは言えない。) この中で、類似度が閾値以上である場合は同じ組とする。 ただし、複数のパターンが考えられる場合は組の数が一番すくなくなるように作る。 ■プログラムの動作イメージ 例1: 閾値=0.90 //入力データ 01 = 0.91; OK 02 = 0.90; OK 03 = 0.78; NG 04 = 0.83; NG 12 = 0.94; OK 13 = 0.78; NG 14 = 0.77; NG 23 = 0.78; NG 24 = 0.69; NG 34 = 0.94; OK OKなのは,01,02,12,34 つまり以下のような出力が得られる >>0,1,2 >>3,4 --------------------------------------- 例2: 閾値=0.90 //入力データ 01 = 0.91; OK 02 = 0.90; OK 03 = 0.94; OK 04 = 0.83; NG 12 = 0.95; OK 13 = 0.78; NG 14 = 0.77; NG 23 = 0.78; NG 24 = 0.69; NG 34 = 0.94; OK OKなのは,01,02,03,12,34 つまり 0,1,2 3,4 or 0,3 1,2 4 となった場合は、組数の少ない上を選択する。 従って以下のような出力が得られる。 >>0,1,2 >>3,4 --------------------------------------- 例3: 閾値=0.90 //入力データ 01 = 0.91; OK 02 = 0.90; OK 03 = 0.78; NG 04 = 0.83; NG 12 = 0.77; NG 13 = 0.78; NG 14 = 0.77; NG 23 = 0.78; NG 24 = 0.69; NG 34 = 0.94; OK OKなのは,01,02,34 この場合は、01と02は閾値を超えているが、12は閾値を超えていないため、 0,1,2を同じ組とはできない。 従って以下の2パターンが考えられる。 0,1 2 3,4 or 0,2 1 3,4 この場合は組の数は同じなのでどちらが出力されてもOK。 番号の若いものから出力されるとすると以下のような出力が得られる。 >>0,1 >>2 >>3,4 ------------------------------------------------------ 以上のようなプログラムを作成したいです。 自分で考えてみたのプログラムが以下のものです。 01,02,12,34は閾値を超えているということまではできたのですが、その後のグループの作り方のところで詰まってしまいました。 そこで、上記のような動作をするプログラムについて教えていただきたいです。 よろしくお願い致します。 int main(){ //閾値 double THRESHOLD = 0.9; //dataを格納する配列 double in_data[5][5] = {0}; //group_flagを格納する配列 bool group_flag[5][5] = {0}; in_data[0][1] = 0.91; in_data[0][2] = 0.90; in_data[0][3] = 0.78; in_data[0][4] = 0.83; in_data[1][2] = 0.94; in_data[1][3] = 0.78; in_data[1][4] = 0.77; in_data[2][3] = 0.78; in_data[2][4] = 0.69; in_data[3][4] = 0.94; //組の番号を格納する配列    //group[3]=2だったら、データ3はグループ2に入る int group[5]; int i=5; //データ数 int num=0; for(int n=0; n<=i; n++){ for(int m=n+1; m<i ;m++){ cout << "in_data[" << n << "][" << m << "]=" << in_data[n][m] << endl; if(in_data[n][m] >= THRESHOLD){ cout << "OK" << endl; group_flag[n][m] = 1; } } } for(int n=0; n<=i; n++){ for(int m=n+1; m<i ;m++){ if(group_flag[n][m] == 1){ cout << n << m <<endl; } } } }

  • Cプログラム

    c言語で「正整数Nを入力後、N個の実数を入力し、それらの平均値と最大値を表示するプログラム」を教えてください。

  • 反転のプログラムについて

    プログラムの質問で「入力された正の整数において、桁の順序を反転したプログラムを作れ。321→123、32100→123など。0の時は0と表示させろ」という問題がどうしてもわかりません。講師の人が10で割ればいいと言ってるんですがいまいちわかっていません。使ってるのはVisual Stadio 2005のC++です。教えてもらえませんか?ついでに 「M以上N以下の正の整数で、素数であるものを小さい方から表示するプログラムを作れ」も教えてもらえれば幸いです。アドバイスでも結構ですのでよろしくお願いします

  • このプログラム見てほしいです!!

    #include <stdio.h> int gcd2(int a, int b) { if (!b) return a; return gcd2(b, a%b); } int main() { int a, b, c; printf("2つの任意の整数を入力せよ:"); scanf("%d %d",&a,&b); c=gcd2(a,b); printf("最小公倍数は%d\n",a*b/c); printf("最大公約数は%d\n",c); return 0; } で、最小公約数を出すことはできたのですが、全ての公約数を表示させたいんです!!どうやったらいいのでしょうか??プログラミングまだ初心者なので、ちょっと行き詰ってしまいました。。。 お時間があればでいいのですが、もう一つわからないプログラムがあります。 自然数nを入力し、x^2+y^2=z^2 (x<y)を満たすようなn以下の自然数の組(x,y,z)がいくつあるのかを出力するプログラムなのですが、全くわからず行き詰っています。。どなたかお時間があれば教えて頂きたいです。 色々と申し訳ありません。お願いします(__)

  • プログラムが上手く動作しません。

    質問です。 1.整数を1個入力し、その数を3で割った余りが0ならば"Good morning"、1ならば"Good evening"、2ならば"Good afternoon"と出力するプログラムを作成せよ。ただしswhitc文を用いること。 という問題で私は #include <stdio.h> main() {      int a;      printf("整数a:");      scanf("%d",&a);      switch(a%3)      {      case '0':           printf("Good morning \n");           break;      case '1':           printf("Good evening \n");           break;      case '2':           printf("Good afternoon \n");           break;      } } と考えましたが実行しても入力はできますがprintfが表示されません。 どこが間違っているのでしょうか?ちゃんとコンパイルはできるのですが・・・。 2.10個の整数値をキー入力し、合計と平均値を計算してその結果を表示するプログラムを書きなさい。 #include <stdio.h> main() {      int a[11],b,c,i;      for(i=1;i<11;i++)      {           printf("整数%d:\n",i);           scanf("%d",&a[i]);      }      for(i=1;i<11;i++)           b+=a[i];      c=b/10;      printf("合計値は%d",b);      printf("平均値は%d",c); } というプログラムを考えましたが、計算結果がめちゃくちゃになってしまいます。 これもどこを直したらいいべきでしょうか?

  • C++のプログラム

    C言語の問題を授業で出されたのですがさっぱり分かりません。教えて下さい。 1.キーボードから整数nを入力して、1+2+…+nを求めるプログラムを作れ。 2.キーボードから整数nを入力して、1*2*…*nを求めるプログラムを作れ。 3.キーボードから10個の実数を入力し、それらの平均を求めるプログラムを作   れ。 4.円錐の体積を求めるプログラムを作れ。 注:円錐体積V=π*r*r*h/3 5.キーボードから文字列を入力し、それを逆さまにするプログラムを作れ。例えば、”dog”を逆さまにすると”god”になる。 6.キーボードから一つの整数を入力し、それは奇数か偶数かを判断するプログラムを作れ。 ちなみに6番は /* iftst.c */ #include <stdio.h> void main(void) { int n; printf("n="); scanf("%d",&n); if(n%2 == 0){ printf("偶数です\n"); } else{ printf("奇数です\n"); } } で合っているのでしょうか?

  • キーボードの入力としてOSに渡すプログラム

    キーボードの入力としてOSに渡すプログラムを作りたいんですが、どうすればいいでしょうか? 具体的には メモ帳などに入力のカーソルを出してる状態で、 プログラムを起動するとプログラムであらかじめ指定しておいたキーが押されたものとしてメモ帳に入力されるようなプログラムなのですがどうやればいいでしょうか? 自動入力といった感じのものなのですが。 C言語でコンソールアプリあたりで作ろうと思っているのですが使用できる関数やアルゴリズムなど教えてください。

  • このプログラムみてもらえますか?

    課題は標準入力から正整数aを読み込み、aが素数であるか否か判定するプログラムを作れ、です。 #include <stdio.h> int main(void) { int a,b,c; for(;;){ printf("正整数を入力して下さい。\n"); scanf("%d",&a); c=a%b; for(b=2;b=a-1;b=b+1){ if(c==0) printf("素数でない。\n"); break; } printf("素数です。\n"); break; return(0); } } コンパイルはできますが、実行すると9が「素数です」と表示されます^^; よろしくおねがいします。

  • プログラム言語に上下関係ってありますか?

    プログラム言語に上下関係ってありますか? 私は、普段プログラミングするとき、表計算ソフトとの連携が容易であり、 グラフ化が簡単にできると理由から、Excelに付属のるVBAを使います。 しかしながら、私の中ではVBAはExcelに毛が生えた程度で、 極めて初心者用のプログラムだと思っています。 やはりC言語やMathematicaの方がプロ仕様という感じがして、 レベルが上のように思います。 そのため、他人にそのプログラムは何で書きましたか? 聞かれたときに、「VBAです」と答えるのですが、「何だVBAか」と思われていないかと 少し引けを感じてしまいます。 でも、実際、どうなんでしょうか? 勝手に私の中でVBAよりC言語やMathematicaの方が偉いと思っているだけなのでしょうか? それとも実際に、ほとんど人が同じように思っているのでしょうか?

  • 二進数にするプログラム

    C言語の問題なんですが、なかなかできません。 途中までやったんですがこれからどうすればいいか分かりません。 1、まず、整数をどんどん入力し、最後に負の数を入力する。負の数が入力されると、これまで入力された数を逆順で表示するプログラムを作成する。 2、1でできたものを利用して、何か数字が入力されたら、それを二進数に直すプログラムを作成する。ただし、二進数の桁数は1000桁以内とする。 ここまでやったんですがこれからどうすればいいか分かりません。 どなたか知恵を貸してくれませんか? #include<stdio.h> int main() { int z[1000],Z,i; printf("正の整数を入力してください:\n"); for(i=0;1<1000;i++); { scanf("%d",&z[i]); if(z[i]<0) break; } Z=i; for(i=0;i<Z/2;i++) { int temp=z[i]; z[i]=z[Z-1-i]; z[Z-1-i]=temp; } printf("入力した要素を逆順に並べると:\n"); for(i=0;i<Z;i++) printf("%d\n",z[i]); return(0); }

このQ&Aのポイント
  • brother p touch edditorで文字入力時のタイムラグが5秒ほどあります。解決方法を教えてください。
  • お使いの環境はmac osです。接続はインストールされたソフトです。
  • この問題に関してブラザー製品について質問です。
回答を見る