求婚者の花嫁

「求婚者の花嫁」では、若者は国王の１００人の娘の中から花嫁を選びたいという設定だ。娘たちはランダムに紹介され、若者は外見の美貌や気品から花嫁を選ぶわけだが、もし紹介された娘を一度断ったら、もうその娘とは会えなくなる。そして、一度相手を決めたら、その娘と必ず結婚しなくてはならず、他の相手とすることはもう許されない。

「プログラマのための論理パズル」p17より。

さて、このとき最も美しい娘と結婚するにはどうしたらいいか。

次のようなプログラムを考える。

/*
 *  main.cpp
 *  q4Iser1
 *
 *  Created by Pinggu on 09/08/10.
 *  Copyright 2009 Pinggu. All rights reserved.
 *
 */
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>

using namespace std;

int const n = 100;//花嫁の数
int const sim_num = 10000;//シミュレーションの試行回数
int const swap_num = 1000;//シャッフルの回数

//シャッフル
void swap(int a[],int i, int j){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

//初期化
void init_f(int fiances[]){
	for(int i = 0 ; i < n; ++i){
		fiances[i] = i+1;
	}
}
//花嫁の順番を決める
void genf(int fiances[]){
	for(int k = 0 ; k < swap_num; ++k){
		int i = rand() % n;
		int j = rand() % n;
		swap(fiances ,i ,j );
	}
}
			
void show(double a[n]){ //要素数n個の配列の表示
	for(int i = 0 ; i < n ; ++i){
		cout << a[i] << " " ;
	}
	cout << endl;
}

int main () {
	int fiances[n];
	srand( (unsigned int)time(NULL) );
	double score[n];
	ofstream ofs( "test1.txt" );
	
	for(int m = 0; m < n ; ++m){ // m:何人目まで見るか
		double s = 0.0;
		for(int i = 0; i < sim_num; i++){
			init_f(fiances);
			genf(fiances);
			//show(fiances);
			int val = 0;
			for(int j = 0; j < m; ++j){//m人目までの最高の美人を記録する
				if(fiances[j] > val){
					val = fiances[j];
				}
			}
			for(int j = m; j < n; ++j){//valよりも美人が現れたら終了
				if(fiances[j] > val){
					if(fiances[j] == n){
						s++;
					}
					break;
				}
			}
		}
		score[m] = s /10000.0;
		ofs << m << " " << score[m] <<endl;
	}
	show(score);
	
    return 0;
}

結果は以下の通り

0.0102 0.0503 0.0867 0.1079 0.1289 0.1487 0.1711 0.1801 0.2056 0.2222 0.2361 0.2421 0.2583 0.2699 0.2785 0.2828 0.2975 0.3079 0.3108 0.3288 0.323 0.3346 0.3362 0.3374 0.3423 0.3528 0.3553 0.3591 0.3653 0.3618 0.3648 0.3658 0.3622 0.3648 0.3707 0.371 0.3757 0.3712 0.3626 0.3765 0.3674 0.367 0.3673 0.3651 0.361 0.3566 0.3593 0.3549 0.3551 0.3548 0.3479 0.3329 0.3461 0.3419 0.3411 0.3221 0.3279 0.3207 0.3171 0.3174 0.2995 0.3008 0.2964 0.2982 0.297 0.2785 0.2761 0.2679 0.2653 0.2604 0.2458 0.2475 0.2345 0.2286 0.22 0.2166 0.2153 0.2089 0.1917 0.1892 0.1766 0.1743 0.1631 0.1536 0.1496 0.1479 0.1332 0.1228 0.1127 0.1035 0.0991 0.0837 0.0795 0.0717 0.0604 0.0466 0.0413 0.0263 0.02 0.0107

これをグラフにすると、

したがって、35人目ぐらいまではただ見るだけで、それ以降はそれまでで一番の美人に決めれば良いということが分かる。