数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：寻找划船游戏获胜者
假设我们有一个高度数组height。有n座不同高度的塔。Amal和Bimal正在玩一个游戏。游戏规则如下：
Amal总是先走
在每次移动中，当前玩家选择一座高度为X的塔，将其拆分成Y座高度均为Z的塔。[Y*Z = X; X和Y > 1]
无法移动者输掉游戏
我们需要找到获胜者的名字。
所以，如果输入类似height = [3,1,2]，则输出将是Bimal，因为初始高度为{3,1,2}。如果Amal将高度为2的塔拆分成两座高度为1的塔，则新的高度数组将为{3,1,1,1}，Bimal可以将高度为3的塔拆分成三座高度为1的塔，因此Amal无法移动，所以Bimal获胜。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数util()。这将采用limit参数，初始limit值为10^3+5
- result := 一个大小为limit的数组，并用0填充
- 对于范围在2到limit-1的i：
- s := 一个新的集合
- 对于范围在1到i的平方根向下取整的j：
- d := i/j的商，r := i/j的余数
- 如果r等于0，则：
- 如果j是奇数，则：
- 将result[d]插入s
- 如果d是奇数，则：
- 将result[j]插入s
- 如果j是奇数，则：
- j := 0
- 当j存在于s中时：
- j := j + 1
- result[i] := j
- 返回result
- g := util()
- 从主方法中执行以下操作：
- r := 0
- 对于height中的每个i：
- r := r XOR g[i]
- 如果r不为零，则：
- 返回"Amal"
- 否则：
- 返回"Bimal"
示例
让我们看看下面的实现以更好地理解：
def util(limit=10**3+5):
result = [0] * limit
for i in range(2, limit):
s = set()
for j in range(1, int(i**0.5)+1):
d, r = divmod(i, j)
if r == 0:
if j & 1:
s.add(result[d])
if d & 1:
s.add(result[j])
j = 0
while j in s: j += 1
result[i] = j
return result
g = util()
def solve(height):
r = 0
for i in height:
r ^= g[i]
if r:
return "Amal"
else:
return "Bimal"
height = [3,1,2]
print(solve(height))输入
[3,1,2]
输出
Bimal
更新于：2021年10月23日
295次浏览
广告