for 分についてです

質問

M 個のものを N こに分割したいとき，その分割する幅
の最適値を求めたいので，とりあえず全探索してみようと思い次ぎような for 文を書いてみました．

for(int n_1 = 0; n_1 < M; n_1 ++){
for(int n_2 = 0; n_2 < M; n_2 ++){
for(int n_3 = 3; n_3 < M; n_3 ++){
...
...
if(){
run()
}
...
...
}
}
}

なんですが，これだと分割する数 N が増えるたび
に for 文をつけたさなくてはならないですよね？

なので，上記のような for 文を N を変数として
自動的に構築するようなプログラムの書き方を教えて
いただけないでしょうか？

簡単なことかも知れないのですが，まだまだプログ
ラムが苦手なので，やさしく教えていただけますと
助かります．

よろしくお願いいたします．

回答No.1

bender · ベストアンサー

ご質問の趣旨にあっているかわからないのですが、私は例えば以下のようなプログラムを考えると思います。

ところで、「M 個のものを N 個に分割する」ことは「M個のものを並べて、その間にN-1個のカンマをうってグループ分けすること」と同じです。例えば、M=4, N=3　のとき、カンマを打てる場所はM-1=4-1=3個、うつカンマの数はN-1=3-1=2個。結果として、3C2=3通りのグループ分けが以下のようにできます。
0, 1, 2 3
0, 1 2, 3
0 1, 2, 3
ということで、各グループの右端のインデックス（以上の場合、上からそれぞれ、0,1,3、0,2,3、1,2,3）を出力するようなプログラムをかけばよいのだと思います。方法としては、左端からグループを一つずつ区切っていくことを繰り返せばよいので（0 1 2 3　が与えられたとき、一つ目のグループは　0　か　0 1　になり、仮に　0　の場合、次は　1 2 3　から２つ目のグループ 1　か 1 2　を区切り、次に...、ということを繰り返す）、以下のような再帰的なプログラムを考えました。再帰的でないプログラムを書くのは少し面倒だと思います。

#include <stdio.h>
const int M=6, N=3;

/* split ...　再帰的関数　　　　　　　　　 */
/* m ... 現在の左端のインデックス */
/* n ... あと何個のグループを選ぶか */
/* array ... 各グループの右端のインデックスを記録 */
void split(int m,int n,int array[]) {
int i;
　/*　残りのもの (M-m)　の数が、必要なグループ数（N-n）より
　　　少ない場合 （すでにグループ分け不可能）*/
if( M-m<N-n )
return;
/* 最後の１グループを作るだけでよいとき （成功) */
else if(n==N-1) { // need to choose only one more
for(i=0; i<N-1; i++)
printf("%2d ",array[i]);
printf("%2d\n",M-1); /* 最後のグループの右端はいつもM-1 */
return;
}
　/* (M-m)個のものから、次のグループをひとつ区切る */
for(i=m; i<M; i++) {
array[n]=i;　/* n番目のグループの右端を i と記録 */
/*　再帰的に（小さくなった）問題を解く */
split(i+1,n+1,array);
}
return;
}
main() {
int array[N-1];
split(0,0,array);
}

ところで、はじめに書いたように、一般に (M-1)C(N-1)のグループ分けができるのですが、この数はとても大きな数になるので、Mが大きくなるにつれて、すぐにこの問題のプログラムは（プログラムの書き方にかかわらず）時間がかかりすぎて終わらないことになると思います。

以上のプログラムに間違いがある場合は、また教えてください。

お礼

どうもありがとうございました！
非常に良く分かりました．
なんとなく再帰的にやることだけ
は分かっていたのですが，具体的
にどうしたら良いのかまでは．．．

計算時間がめちゃくちゃかかって
しまうのが問題なので，それをど
うにかうまいことやってみたいと
思います！！