Python程序：计算赢得莲花与毛毛虫游戏中所需预期步数

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

Amal在顶行某个位置放置白色莲花棋子，Bimal在底行某个位置放置毛毛虫棋子。Amal先开始游戏，他们轮流进行。Amal可以将他的棋子移动到当前单元格网格内任何8个相邻单元格，但Bimal的毛毛虫棋子只能在网格内向左或向右移动，或者保持在同一位置。Amal的目标是用尽可能少的步数抓住Bimal，而Bimal（用毛毛虫棋子）则必须尽可能长时间地生存。如果他们随机选择两列放置他们的莲花和毛毛虫，那么我们必须找到Amal赢得这场游戏所需的预期步数。

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

为了解决这个问题，我们将遵循以下步骤：

• r := 0
• 对于l从0到m - 1循环：
  • 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))

输入

5, 7

输出

4.571428571428571

Arnab Chakraborty

更新于：2021年10月25日

浏览量：111

开启你的职业生涯

完成课程获得认证

开始学习