fork download
copy 
  1. /*
  2. プログラミングのお題スレ Part15 
  3. //mevius.5ch.net/test/read.cgi/tech/1564310397/4
  4.  
  5. 4 名前：デフォルトの名無しさん[sage] 投稿日：2019/07/28(日) 21:32:12.69 ID:MO+jaDzY
  6. お題
  7. とあるゲームでは、10面ダイスによってスコアを次のように定める
  8. 1. x個のダイスを全部振る
  9. 2. 振ったダイスのうち、最大の出目をスコアとする
  10. 3. 出目がc以上のダイスが存在するなら、その全てのダイスを使って同じ試行を行い、スコアに加算する
  11. 例えばc=7の時、2個のダイスの結果が(10,7)→(8,3)→(2)ならスコアは10+8+2=20となる
  12. 最初に振るダイスの個数Nとc(≧2)が分かっている時、スコアの期待値を求めよ
  13. */
  14. class Ideone
  15. {
  16.     public static void main(String[] args)
  17.     {
  18.         for (int n = 1; n <= 10; n++)
  19.             odai(n, 5);
  20.     }
  21.  
  22.     static void odai(int n, int c)
  23.     {
  24.         if (c < 2) throw new IllegalArgumentException();
  25.         System.out.printf("N=%d, c=%d -> %f%n", n, c, calc(10, n, c));
  26.     }
  27.  
  28.  
  29.     /**
  30.      * @param faces ダイスの面数
  31.      * @param dice ダイスの数
  32.      * @param c この出目以上のダイスはもう一回振れる
  33.      * @return 期待値
  34.      */
  35.     static double calc(int faces, int dice, int c)
  36.     {
  37.         double[] scores = new double[dice + 1];
  38.         double probability = Math.max(0, 1 - (c - 1d) / faces);
  39.  
  40.         // n個のダイスを振った時の期待値を求めてscores[n]に入れる
  41.         for (int n = 1; n <= dice; n++)
  42.         {
  43.             double score = expectedMaxValue(faces, n);
  44.  
  45.             for (int reroll = 1; reroll < n; reroll++)
  46.             {
  47.                 score += scores[reroll] * binomialDistribution(n, reroll, probability);
  48.             }
  49.  
  50.             scores[n] = score / (1 - binomialDistribution(n, n, probability));
  51.         }
  52.  
  53.         return scores[dice];
  54.     }
  55.  
  56.     /**
  57.      * 指定回ダイスを振った時の出目の最大値の期待値を求める
  58.      * @param faces ダイスの面数
  59.      * @param num ダイスを振る数
  60.      * @return 出目の最大値の期待値
  61.      */
  62.     static double expectedMaxValue(int faces, int num)
  63.     {
  64.         double value = 0;
  65.         for (int i = 1; i <= faces; i++)
  66.         {
  67.             value += (Math.pow(i, num) - Math.pow(i - 1, num)) * i;
  68.         }
  69.         return value / Math.pow(faces, num);
  70.     }
  71.  
  72.  
  73.     static long binomialCoefficients(int n, int k)
  74.     {
  75.         if (n < 0 || n > 64 || k < 0 || k > n) throw new IllegalArgumentException();
  76.         if (k == 0 || k == n) return 1;
  77.         if (k == 1 || k == n - 1) return n;
  78.  
  79.         long[] array = new long[n + 1];
  80.         array[0] = 1;
  81.         for (int i = 1; i <= n; i++)
  82.         {
  83.             array[i] = 1;
  84.             for (int j = i - 1; j >= 1; j--)
  85.             {
  86.                 array[j] += array[j - 1];
  87.             }
  88.         }
  89.         return array[k];
  90.     }
  91.  
  92.  
  93.     static double binomialDistribution(int n, int k, double p)
  94.     {
  95.         return binomialCoefficients(n, k) * Math.pow(p, k) * Math.pow(1 - p, n - k);
  96.     }
  97. }
  98.  
Success #stdin #stdout 0.08s 34544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N=1, c=5 -> 13.750000
N=2, c=5 -> 21.484375
N=3, c=5 -> 27.061543
N=4, c=5 -> 31.429423
N=5, c=5 -> 35.019871
N=6, c=5 -> 38.067903
N=7, c=5 -> 40.715790
N=8, c=5 -> 43.056198
N=9, c=5 -> 45.152868
N=10, c=5 -> 47.051543
https://ideone.com/JHb8WE
プログラミングのお題スレ15の4
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!