この問題は今のところ考え中です。
この問題ｎ枚のゲームでaターン目にｍ枚と告げられた時、この３つの引数だけからとるべき行動は一意に決まり。
(a-1)ターン目までにえられたデータは意味がないというところまで到達しているのですがそこから先に進めない状態です。
a-1ターン目までのデータに意味がない理由
議論Ａ
例えば5枚目までに 1,3,5,7,9と出た場合,5枚目が9の場合と7の場合。
(1,3,5,7)=(a1<a2<a3<a4)
(1,3,5,9)=(b1<b2<b3<b4)の変数と対応付けると。
4枚目までの出方が
(1,3,5,7)=(a1,a2,a3,a4)
(1,3,5,9)=(b1,b2,b3,b4)
(1,5,3,7)=(a1,a3,a2,a4)
(1,5,3,9)=(b1,b3,b2,b4)
(7,1,5,3)=(a4,a1,a3,a2)
(9,1,5,3)=(b4,b1,b3,b2)
,,,
というように4枚目までのすべての出方で一対一対応が取れます。
この場合4枚目までにどんなデータが得られても5枚目に7が出る確率も9が出る確率も同じです。
5枚目が(1,3),(1,5),(1,7),(1,9),(3,5),(3,7),(3,9),(5,7),(5,9),(7,9)
の組ととしても同じです。
議論Ｂ
また2,4,7,11,13みたいな（どんな数字の組み合わせでもいいですが）別の組み合わせの数が5枚目までにでるとしてで5枚目が11だとして
(2,4,7,13)=(b1＜b2＜b3＜b4)
とすれば議論Ａと同じ理由で何らかの順番で1,3,5,7が出た後で9が出るのと何らかの順番で2,4,7,13が出た後で11が出る確率も同じです。
他のどんな数字の組み合わせにしても同様の議論ができます。
よって、aターン目の決定には (a-1)ターン目までに得られたデータは使えないとわかります。
議論Ｂ
具体的な計算
まずaターン以降最適な戦略をとった場合のスコアの期待値をP(a)と表します。
Ｐ(ｎ)は簡単に求まります。
次に、f(n,a,m)をn枚のゲームでaターン目にｍ枚と告げられた時、そこでゲーム終了としたときのスコアの期待値とします。
ただしP(a+1)<f(n,a,m)の場合f(n,a,m)=P(a+1)と定義します。
P(a)＝Σｆ(n,a,m)/a
と定義してP(n)から計算をはじめP(1)まで計算すれば答えが出ると考えました。
しかしこの手法では計算量のオーダーがn^3になります。
私にはこの問題は難しすぎるのかもしれません。
今のところこの分析から先に進めない状態です。
オーダーn^3のコード例C++ BCC5.5
f(10)を計算します。
f(10)で正しい答えが出てるのでたぶん発想は正しいのでしょう。
n=100万の場合はよくわかりません。
#include<stdio.h>
double com(double n,double r){
double re=1;
for(double i=1;i<=r;i+=1){
re*=(n/i);
n-=1;
}
return re;
}
const int LIMIT=10;
int main(){
double ave=0;
for(int i=1;i<=LIMIT;i++){
ave+=i;
}
ave/=LIMIT;
for(int i=LIMIT-1;i>=1;i--){
double ave2[LIMIT]={0};
for(int j=0;j<i;j++){
double sum=0,count=0;
for(int k=i-j;k<=LIMIT-j;k++){
sum+=k*com(k-1,i-j-1)*com(LIMIT-k,j);
count+=com(k-1,i-j-1)*com(LIMIT-k,j);
}
ave2[j]=sum/count;
if(ave<ave2[j])ave2[j]=ave;
}
double sum=0;
for(int j=0;j<i;j++){
sum+=ave2[j];
}
ave=sum/i;
printf("%d %lf\n",i,ave);
}
}
最終更新：2015年04月02日 01:47
