Euler Projesi 227. Soru

Takip

"Takip", iki zar ve çift sayıda oyuncuyla oynanan bir oyun.

Oyuncular bir masaya otururlar; karlı karşıya oturan iki oyuncuya birer zar verilerek oyuna başlanır. Her turda iki oyuncu ellerinde birer zarla.

Eğer bir oyuncu 1 atarsa, zarı soldaki oyuncuya verir; eğer 6 atarsa sağdaki oyuncuya verir; diğer durumlarda sonraki tur için zar kendinde kalır.

Herkes atıp geçişler yapıldıktan sonra elinde iki zar bulunan oyuncu varsa, oyunu kaybeder.

100 kişilik bir oyunda oyunun son bulması için beklenen tur sayısı nedir?

Cevabı 10 anlamlı basamağa kadar veriniz.

Cevap: 3780.618622

 C++:

 int N = 51;
    vector < vector < double > > v(N, vector < double >(N+1, 0));
    v[0][0] = 1;
    for (int i = 1; i < N; ++i) {
        v[i][i] = 0.5;
        for (int j = -2; j <= 2; ++j) {
            if (j == 0)
                continue;
            double d = (abs(j) == 2) ? 1.0/36.0 : 2.0 / 9.0;
            int k = i+j;
            if (k < 0)
                k = -k;
            if (k > 50)
                k = 100 - k;
            v[i][k] -= d;
        }
        v[i][N] = 1;
    }
    for (int i = 0; i < N; ++i) {
        double d = v[i][i];
        for (int j = i; j <= N; ++j)
            v[i][j] /= d;
        for (int j = i+1; j < N; ++j) {
            double d = v[j][i];
            for (int k = i; k <= N; ++k)
                v[j][k] -= d*v[i][k];
        }
    }
    printf("%12.12lf\n", v[N-1][N]);

 Mathematica:

k = 50;
f[x_, y_] :=
  Switch[x,
   0,      Switch[y - x,  0, 1, _, 0],
   1,      Switch[y - x, -1, 2/9, 0, -17/36, 1, 2/9, 2, 1/36, _, 0],
   k - 1, Switch[y - x, -2, 1/36, -1, 2/9, 0, -17/36, 1, 2/9, _, 0],
   k,      Switch[y - x, -2, 1/18, -1, 4/9, 0, -1/2, _, 0],
   _,      
   Switch[y - x, -2, 1/36, -1, 2/9, 0, -1/2, 1, 2/9, 2, 1/36, _, 0]];
m = Table[f[x, y], {x, 0, k}, {y, 0, k}];
b = Table[Switch[x, 0, 0, _, -1], {x, 0, k}]; 
NumberForm[LinearSolve[m, b] // N, 10]

 Python:

double cache227[100][100][2];

double recurse227(int a, int b, int p, int t)
{
    static double weight[] = {1.0/6.0, 2.0/3.0, 1.0/6.0};
    double tot = 0;

    if (cache227[a][b][t & 1] >= -1)
        return cache227[a][b][t & 1];

    if (t == 0) {
        if (a == b)
            return 1;
        return 0;
    } else {
        if (a == b)
            return 0;
    }

    for (int ma = -1; ma < 2; ma++) {
        for (int mb = -1; mb < 2; mb++) {
            int newa = (a+ma)%p;
            if (newa < 0) newa += p;
            int newb = (b+mb)%p;
            if (newb < 0) newb += p;
            tot += weight[ma+1] * weight[mb+1] * recurse227(newa, newb, p, t-1);
        }
    }

    cache227[a][b][t & 1] = tot;

    return tot;
}

double recurse227f(int a, int b, int p, int t)
{
    for (int aa = 0; aa < 100;  aa++)
        for (int bb = 0; bb < 100;  bb++)
        {
            cache227[aa][bb][t & 1] = -2.0;
            recurse227(aa, bb, p, t);
        }

    return recurse227(a, b, p, t);
}
    

void euler_227_entry()
{
    printf("euler 227\n");

    for (int a = 0; a < 100; a++)
        for (int b = 0; b < 100; b++)
            for (int t = 0; t < 10; t++)
                cache227[a][b][t] = -2.0;

    double tot = 0;
    for (int x = 0; x < 100000; x++)
    {
        double r = (double)x * recurse227f(0, 50, 100, x);
        if (x % 1000 == 0)
            printf("%d %.20f %.20f\n", x, r, tot);
        tot += r;
    }
    printf("tot = %.20f\n", tot);
}

 Haskell:

fsub (v:vs) (c:x:xs) = (c+x*v):(zipWith (+) xs $ map (x*) vs ++ repeat 0)
reduce (c:x:xs) = map (/(1-x)) (c:xs)

nxt (x,a,b) = let c = reduce $ fsub b $ fsub a coeffs in (x+1,b,c)
  where coeffs
          | x == 1     = [1,0,2/9,19/36,2/9,1/36]
          | x == (n-1) = [1,1/36,2/9,19/36,2/9,0]
          | x == n     = [1,1/18,4/9,1/2,0,0]
          | otherwise  = [1,1/36,2/9,1/2,2/9,1/36]
          where n = 50

p227 = head t
  where (_,_,t) = iterate nxt (1,[0],[0]) !! 50

 Java:

import java.util.*;
import java.io.*;

public class Pr227
{
  static public void main(String[] args)
  {
    int size = 100;
    long maxTurns = 100000;

    double[] prob = new double[size]; // probability mass for die2 position
    prob[size/2] = 1.0;               // initial position has all the probability mass

    double E_last = 0.0; // the value of interest

    for (long turn = 1; turn <= maxTurns; ++turn) {
      prob = next_prob(prob,size); // first move of this turn
      prob = next_prob(prob,size); // second move of this turn
      E_last += turn*prob[0]; // prob[0] is the prob this was the last turn
      prob[0] = 0.0;
    }

    System.out.println("E_last: " + E_last);

  } // main(String[] args)

  static private double[] next_prob(double[] prob, int size)
  {
    double[] next = new double[size];
    for (int pos = 0; pos < size; ++pos) {
      double v = prob[pos];
      next[mod(pos+1,size)] += v/6; // some prob mass moves to left neighbor
      next[mod(pos-1,size)] += v/6; // some prob mass moves to right neighbor
      next[pos] += 2*v/3;           // some prob mass stays put
    }
    return next;
  }

  static private int mod(int a, int b) { if (a >= 0) return a%b; else return (a+b)%b;}
    // lol java!
}