Pythonでポイントがn個以下になる確率を調べるプログラム

ユニークなゲームをプレイしていて、n、k、hの3つの値があるとします。 0ポイントから開始し、1からh（両端を含む）の間でランダムに数値を選択すると、その数のポイントを取得できます。最低kポイントを獲得したら停止します。ポイントがn個以下になる確率を見つける必要があります。ここでは、任意の数をランダムに選択でき、結果はすべて同じ確率になります。

したがって、入力がn =2、k =2、h =10の場合、出力は0.11になります。

これを解決するには、次の手順に従います-

• 関数dp（）を定義します。これは道をたどります。

  • パスがk− 1と同じ場合、thens

    • return（n − k + 1およびhの最小値）/ h

  • パス>nの場合、

    • 0を返す

  • パス>=kの場合、

    • 1を返す

  • return dp（path + 1）−（dp（path + h + 1）− dp（path + 1））/ h

• 主な機能から、次のようにします-

• kがゼロの場合、

  • 1を返す

• n

  • 0を返す

• dp（0）を返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, n, k, h):
      if not k: return 1
         if n < k: return 0
         def dp(path):
            if path == k− 1:
               return min((n− k + 1), h) / h
            if path > n:
               return 0
            if path >= k:
               return 1
            return dp(path + 1)− (dp(path + h + 1)− dp(path + 1)) / h
         return dp(0)
ob = Solution()
print(ob.solve(2,2,10))

入力

2,2,10

出力

0.11