使用Python来找到莲花和毛毛虫游戏中获胜所需的期望移动次数

假设我们有一个n行m列的网格。Amal和Bimal正在这个网格上玩游戏。游戏规则如下 –

Amal在顶行某个位置放置白色莲花方块，Bimal在底部行某个位置放置毛毛虫方块。Amal开始游戏，然后他们轮流玩。Amal可以将他的方块移动到当前单元格内的8个相邻单元格中的任何一个，但Bimal的毛毛虫方块只能左右移动，或者停留在原地。Amal的目标是用尽可能少的步骤抓住Bimal，而Bimal（随着毛毛虫方块）要尽可能长地存活下去。如果他们随机选择两列来放置他们的莲花和毛毛虫，则我们必须找出Amal赢得此游戏所需的平均移动次数。

因此，如果输入如n = 5，m = 7，则输出将为4.571428571428571。

要解决此问题，我们将按照以下步骤进行 –

r := 0
对于区间从0到m – 1的任何l，执行以下操作 –
- temp := n – 1.0
- 如果l >= n，则
  - temp := temp + (l – n + 1) * ((l – 1) / m)
- 如果l < m – n，则
  - temp := temp + (m – n – l) * ((m – l – 2) / m)
- r := r + temp / m
返回r

举例

让我们查看以下实现以更好地了解 –

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))