ポスター44種類コンプリート問題

CD1枚購入のたびに、ポスターが44種類のうち1種類ランダムに得られるとする。

Q1. 44種類コンプリートするには、平均何枚のCDを購入する必要があるか。

Q2. 44種類コンプリートした人はその時点で何種類のポスターを持っているか。

• http://d.hatena.ne.jp/textfile/20080229/probability

数学的なことは分からないのでRuby先生に聞いてみた。

KIND_NUM = 44
N = 100000
flags = Array.new( KIND_NUM )
sum = 0
N.times do
	flags.fill( false )
	n = 0
	until flags.all?
		flags[rand(KIND_NUM)] = true
		n += 1
	end
	sum += n
end
puts "平均: #{sum.to_f/N}"

だいたい192枚ぐらいらしい。

• • • -

Cでも書いた。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define KIND_NUM 44
#define NTRY 100000

int main() {
	char flags[KIND_NUM];
	int i, sum = 0;
	for( i = 0; i < NTRY; i++ ) {
		memset( flags, 0, sizeof flags );
		while( memchr( flags, 0, sizeof flags ) != NULL ) {
			flags[rand()%KIND_NUM] = 1;
			sum ++;
		}
	}
	printf( "%f\n", ((double)sum)/NTRY );
}

やっぱりCは速いなー。