0~9のくじ全てを引くために必要な試行回数を求めるプログラミング

Question

0~9のくじ全てを引くために必要な試行回数を求めるプログラミング

C言語で、0~9のくじがあるとき、久慈は何回でも引けるとし、それぞれの数字が出る確率はすべて等しいものとする。すべての数字を引くまでに何回くじを引けばよいか。という問題に関してです。
rand関数を用いるという点は分かるのですがそれをどのように適用するのかが分かりません。

シャープinclude<stdio.h>
シャープinclude<stdlib.h>
シャープinclude<time.h>
int main(void){
int a,i,kuji[9];
srand((unsigned) time(NULL));

for(i=0; i<9; i++){
kuji[i]=0;
}

for(i=0; i<10; i++){ a=(int)(rand()/(RAND_MAX+1.0)*9);
kuji[a]=0
}
ここまででくじを作ったつもりなのですがこの先が全く手を付けられません。
分かる人がいらっしゃいましたらご回答お願いいたします。

Answer 1

int a,i,kuji[9];

0~9の10種類なので，Kuji[9]ではきっと足りないのではないかと見えます．

---

どんな方法だろうが，10種類のそれぞれを引いたかどうかを覚えておく変数さえ用意すれば，

• くじを引く
• くじを引いた回数を+1する．
• 引いた種類に関して，「その種類を引いた」ことを覚える
• 全てのくじを引いたなら終了

というのを繰り返せばよいように思います．

終了までに何回くじ引きを繰り返すのか？は未知なので，

for(i=0; i<10; i++)

といった，「一定回数だけ」ループさせるようなやり方ではダメでしょう．
while的なのを使って書くと良いかと思います．

//0から9のどれかを返す
int Kuji()
{
    //※この実装は，すげーてきとーです．
    //「それぞれの数字が出る確率はすべて等しいものとする」に関して頑張った処理を実装されたい．
    return (rand()>>2) % 10;
}

int main()
{
    unsigned short Flags = 0;   //各値のくじを引いたかどうかを下位10bitを使って覚える用の変数
    unsigned int N = 0; //くじを引いた回数カウンタ
    srand( (unsigned)time(NULL) );
    do
    {
        ++N;
        Flags |= ( 1 << Kuji() );
    }
    while( Flags != 0x3FF );    //10種全てのくじを引いたら終了

    printf( "N = %u\n", N );    //くじを引いた回数を表示
    return 0;
}

Comments

[Shotayanagi]

ご回答ありがとうございます！
本当に助かりました！
まだプログラミングを勉強し始めたばかりで、
0-9の値を返す戻り値のrand()を右に2ビットシフトして10で割った時の剰余を返す。がなぜそうなるかいまいち理解できていないのですが、宜しければ教えていただけませんか？？また、Flags！=0x3FFの仕組みを教えていただけると幸いです。
理解力が乏しく申し訳ないです…
よろしくお願いします。

[fana]

> 2ビットシフトして10で割った時の剰余

てきとーです．
（疑似乱数の方法次第では下位のビットの精度がどうの…，という話があったりするので，てきとーに下位2ビットを捨ててみました．なので，別にシフトしなくてもよいです．）
10で割った余りとするのは，余りというのが0-9のいずれかになるからですね．

> Flags！=0x3FF

Flagsの下位10ビットを，くじの各値を引いたかどうかを覚える手段として利用しています．最初は全てのビットの値は0で，引いた値に対応する箇所のビットの値を1にすることで覚えています．
10個全てのビットが1になったときのFlagsの値というのが0x3FFです．

[Shotayanagi]

なるほど！とても分かりやすくて助かります！
質問多くて申し訳ないのですが
Flags |=(1 << kuji() );
というのはなぜkuji()の値を左にシフトするのでしょうか？？

[fana]

> 引いた値に対応する箇所のビットの値を1にする

を行っています．
「kuji()の値を左にシフト」ではなく，「1を，Kuji()の値だけ左にシフト」です．
(1 << kuji() )の値は，
・Kuji()が0を返した場合は(シフトしないことになるので) 0x001
・Kuji()が1を返した場合には 0x002
・Kuji()が2を返した場合には 0x004
　...
・Kuji()が8を返した場合には 0x100
・Kuji()が9を返した場合には 0x200
となります．
【「(最下位ビット側から) Kuji()+1 番目」のビットだけが１で他の全てのビットの値が0】な値です．
（16進数で書いてますが，２進数で書いてみればわかりやすいでしょう）

[Shotayanagi]

なるほど！！ありがとうございます。
ちなみになんですけど、このシュミレーションを1000000回実行してその合計と平均を求めたいと考えて
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

int kuji(){

return (rand()>>2) % 10;
}

int main(){

int i;
double avg=0;
unsigned short Flags = 0;
unsigned int N = 0, sum=0;

for(i=0; i<1000000; i++){

sum += N;
avg = sum/1000000;

srand((unsigned) time(NULL));

do{
++N;
Flags |= (1 << kuji() );
}while( Flags != 0x3FF);

}

printf("sum = %u\n",sum);
printf("avg = %.2f\n", avg );

return 0;
}
というプログラミングを書いてみたのですが合計は18億前後、平均は1800ほどと本来20~30ぐらいとなるはずの平均値が大きくずれてしまいます。
do文をfor文の中に入れて1000000回ループさせようと考えたのですがなぜこうなってしまうかわかりますか？？
説明へたくそでごめんなさい。。。

[fana]

・別の話になっている
・コードありきの話をコメント欄でやり続けるのはきつい
・コードをぱっと見では，何をしたいのかがよくわからない

…等の理由により，解決が必要な話なのであれば，別途の質問としていただきたく．
（そうすれば，別の人からも回答もらいやすいですし）

[Shotayanagi]

そうですね。何度も質問してしまい申し訳ありません…
ご丁寧に返信くださってありがとうございました!

Answer 2

kuji[i]=0;

初期化は出来てるようなので、発生した乱数を添え字として1を代入して、あとは全部1になるまでの回数を数えればいいのでは？

Comments

[Shotayanagi]

ご回答ありがとうございます！！