■海辺にn人の美女が並んでいる。
■それを片端から順に見て行って、これぞと思う美女が見つかったらデイトに誘う。
■後戻りは許されない。
■美女には1位からn位までの順位があり、n!通りから等確率で並ぶ。

▼以上の条件で誘う美女の順位の期待値を最小にするにはどのような選び方をすれば良いか?

Y(i):i番目まで見て、i番目の人のそれまでの中での順位。
C(n-1):(n+1)/2
S(i):[Ci*(i+1)/(n+1)] (i=n-1,…,1)
C(i-1):C(i) + (S(i)/i)*{(n+1)*(S(i)+1)/(i+1)/2-C(i))} (i=n-1,…,2)
Y(i)がS(i)以下ならデイトに誘う。

n→∞の時の極限値は約3.8695
どんなに大勢美女が居る場合でもこの戦略を取るなら平均4位以内になる。

#include <math.h>
main(){int i, m, S;float j, n, T, C;printf("美女の数は?\n");scanf("%d", &m);printf("i\tCi\t\tSi\n");n=m;C=(n+1)/2;printf("%d\t%f",m,C);for (i=m-1; i>=0; --i){j=i;n=m;S=floor((j+1)/(n+1)*C);T=S;printf("\t%d\n",S);if (i == 0){break;}C=C+T/j*((m+1)/(j+1)*(T+1)/2-C);printf("%d\t%f",i,C);}}