プロジェクトオイラー問84

Problem 84 「モノポリーの確率」 †
モノポリーのマス目に泊まる確率を求める問題。


試行錯誤の跡がかなり残ってるがマルコフ連鎖として計算できた。
シミュレートでない解法に成功。
行列演算の収束で解。

ルール。
一度だけサイコロを振りぞろ目だろうがでなかろうがマス目の指示に従う。
これを繰り返す途中で三連続でぞろ目が出たら刑務所行き。
でよいようだ。


#include<stdio.h>
#include<set>
#include<string.h>
#include<algorithm>
#include<vector>
const int LIMIT=40;

const int XAI=4;
const int GO=0;
const int JAIL=10;
const int C1=11;
const int E3=24;
const int H2=39;
const int R1=5;

struct E{
	int no;
	double p;
	bool operator<(const E& e)const{
		return p>e.p;
 	}
}; 

int main(){
	std::set<int> cc,ch,rs,us;
	cc.insert(2);
	cc.insert(17);
	cc.insert(33);
	
	ch.insert(7);
	ch.insert(22);
	ch.insert(36);
	
	rs.insert(5);
 	rs.insert(15);
	rs.insert(25);
	rs.insert(35);
	rs.insert(45);
	
	us.insert(12);
	us.insert(28);
	us.insert(52);

	double all[4][LIMIT];
	memset(all,0,sizeof(all));
	all[0][0]=1.0;

	for(int i=0;i<100;i++){
		
		double commit[4][LIMIT];
		memset(commit,0,sizeof(commit));
		double D=XAI*XAI;
		for(int k=0;k<=2;k++){
			for(int j=0;j<LIMIT;j++){	
				for(int d1=1;d1<=XAI;d1++){
					for(int d2=1;d2<=XAI;d2++){
						int p=(d1+d2+j)%LIMIT;
						double ep=all[k][j]/D;
						double *p1;
						if(d1==d2){
							if(k==2){
								commit[0][JAIL]+=ep;
 								continue;
							}
							p1=commit[k+1];
						}else{
							p1=commit[0];
						}
						if(p==30){
							p1[JAIL]+=ep;
						}else if(ch.find(p)!=ch.end()){
							ep/=16.0;
							p1[GO]+=ep;
							p1[JAIL]+=ep;
							p1[C1]+=ep;
							p1[E3]+=ep;
							p1[H2]+=ep;
							p1[R1]+=ep;
							int j1=(*(rs.upper_bound(p)))%40;
						p1[j1]+=ep*2;
							j1=(*(us.upper_bound(p)))%40;
							p1[j1]+=ep;
 							p1[(p+LIMIT-3)%LIMIT]+=ep;
						p1[p]+=ep*6;
						}else if(cc.find(p)!=cc.end()){
							ep/=16.0;
							p1[GO]+=ep;
							p1[JAIL]+=ep;
							p1[p]+=ep*14.0;
						}else{
							p1[p]+=ep;
						}
					}
				}
			}
		}
		memcpy(all,commit,sizeof(all));
	}
	double check=0;
	E e1;
	std::vector<E> es;
	double all1[LIMIT]={0};
	for(int i=0;i<4;i++){
		for(int j=0;j<LIMIT;j++){
			all1[j]+=all[i][j];
		}
	}
	for(int i=0;i<LIMIT;i++){
		check+=all1[i];
		e1.no=i;
		e1.p=all1[i];
		es.push_back(e1);
	}
	printf("\ncheck=%lf\n",check);
std::sort(es.begin(),es.end());
	for(int i=0;i<3;i++){
 		printf("(%d %lf)",es[i].no,es[i].p);
	}
	printf("\n\n");
}  
最終更新:2015年01月26日 13:35