PythonでLotusandCaterpillarゲームに勝つために必要な予想される動きの数を見つけるためのプログラム

n行m列のグリッドがあるとします。アマルとビマルはそのグリッドでゲームをプレイしています。ゲームルールは以下のようになります-

アマルは一番上の列のどこかに白い蓮のタイルを置き、ビマルは一番下の列のどこかに毛虫のタイルを置きます。アマルはゲームを開始し、彼らは交互に遊んでいます。アマルは自分のタイルを現在のセルのグリッド内の8つの隣接するセルのいずれかに移動できますが、ビマルのキャタピラータイルはグリッド内で左または右に移動するか、同じ位置にとどまることができます。アマルの目標は、できるだけ少ない動きでビマルを捕まえることですが、ビマル（毛虫のタイルを使用）はできるだけ長く生き残る必要があります。彼らが蓮と毛虫を置くためにランダムに2つの列を選択した場合、アマルがこのゲームに勝つために必要な予想される動きの数を見つける必要があります。

したがって、入力がn =5 m =7の場合、出力は4.571428571428571になります。

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

• r：=0
• 0〜m-1の範囲のlの場合、do
  • temp：=n-1.0
  • l> =nの場合、
    • temp：=temp +（l --n + 1）*（（l --1）/ m）
  • l
  • temp：=temp +（m --n --l）*（（m --l --2）/ m）
• r：=r + temp / m

例

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

def solve(n, m):
   r = 0

   for l in range(m):
      temp = n - 1.0
      if l >= n:
         temp += (l - n + 1) * ((l - 1) / m)
      if l < m - n:
         temp += (m - n - l) * ((m - l - 2) / m)
      r += temp / m

   return r

n = 5
m = 7
print(solve(n, m))

入力

5, 7

出力

4.571428571428571