所以我试着做一个递归函数，但它导致了无限循环
So I tried to make a recursive function but it results in infinite loop
我正在尝试编码挑战 Link
对于没有帐户的人，这里是复制的：
彼得和亨利正在玩一个由字符“0”和“1”组成的长度为 n 的字符串 s 的游戏。两位玩家交替轮流，但彼得先轮到。
在每个回合中，玩家都可以对字符串执行以下操作之一：
Select 任意 i，其中 s[i]= '0' 并将 s[i] 更改为 '1' 并支付 1 卢比。另一个操作是反转整个字符串并支付 0 卢比。仅当字符串当前不是回文且上次执行的操作不是反向时才允许执行此操作。如果彼得把弦反了，那么下一回合亨利就不能反弦了，反之亦然。
反转字符串意味着将其字母从最后到第重新排序。例如“01001”反转后会变成“10010”
当字符串的每个字符都变成'1'时，游戏结束。到此为止花费最少卢比的玩家赢得游戏，如果双方花费相等的卢比则平局。如果两个玩家都发挥最佳，确定谁是赢家还是平局。
输入格式
第一行包含一个整数 t 。然后是t个测试用例。
每个测试用例的第一行包含一个整数 n 。
每个测试用例的第二行包含长度为n的字符串s，由字符'0'和'1'组成。保证字符串s中至少包含一个'0'
输出格式
对于每个测试用例，在新行中打印一个单词：
“PETER”，如果彼得赢得比赛，“HENRY”，如果亨利赢得比赛，“DRAW”，如果比赛以平局结束。
示例输入 0
2
3个
110
2个
00
示例输出 0
彼得
亨利
解释 0
在例子的第一个测试用例中，在第一步中，彼得将使用第二次操作来反转字符串，因为执行第一次操作无论如何都会导致他的损失。这也迫使亨利使用第一个操作。在第 2 步中，Henry 必须执行第 1 个操作，因为第 2 个操作不能连续执行两次。字符串的所有字符都是'1'，游戏结束。彼得花费 0 卢比，而亨利花费 1 卢比。因此，彼得获胜。
这是代码，我是递归函数的新手，这段代码导致最大递归limit.Any帮助将不胜感激。
def Winner(c,counter):
if sum(c) == b:
if len(set(counter.values)) == 1:
print("DRAW")
return
else:
d=index(min(counter.values()))
print(counter.keys(d))
return
if c == c[::-1]:
for i in c:
if i==0:
c[i] =1
break
counter["PETER"] +=1
c=c[::-1]
print(c)
Winner(c,counter)
else:
c= c[::-1]
for i in c:
if i==0:
c[i]=1
break
counter["HENRY"] +=1
Winner(c,counter)
a=int(input())
p,h=0,0
counter={"PETER":0,"HENRY":0}
global b
for i in range(a):
b=int(input())
c=list(map(int,input().strip().split()))
Winner(c,counter)
我花了几天时间试图理解您的代码和它的逻辑，但它不会 运行 并且它的逻辑布局似乎有缺陷这一事实阻碍了我。因此，我开始自己分析游戏问题并构建自己的解决方案。为此，为了清楚地说明我认为的游戏规则，我尽可能简洁明了地重申了这些规则：
游戏
Peter 和 Henry 正在玩一个由字符“0”和“1”组成的长度为 n 的字符串 s 的游戏。两位玩家交替轮流，但彼得总是先轮到。
该剧
在每个回合中，玩家可以对字符串执行以下操作之一：
- Select 任意 i，其中 s[i]= '0' 并将 s[i] 更改为 '1' 并支付 1 卢比。
- 反转整个字符串并支付 0 卢比。如果出现以下情况，则不允许使用此选项：
- 之前的玩家推翻了字符串
- 字符串是回文
结束游戏
当字符串的每个字符都变成'1'时，游戏结束。
花费最少的玩家获胜。如果双方花费相等，则为平局。
问题
如果两个玩家都发挥最佳，确定谁会赢或者游戏结果是否平局。
分析
假设以上内容准确描述了游戏玩法：
任何解决方案需要解决的第一个问题是确定 'Optimal Play.' 的含义 通过初步观察，我们可以推断出任何玩家最佳玩法必须符合：
- select 如果可能，字符串反转 - 这会迫使对手做出一个数字 selection 罚球
- 如果反转不是一个选项，select 一个反转的数字会产生回文。这要求对手也切换一个数字，因此惩罚相等
- 如果不能创建回文，select一个索引，惩罚1
改值
然而，经过进一步评估，这不一定是正确的优先级，例如以下：
开始：10100,
玩家 0 玩 00101 score(0,0)
玩家 1 打出 10101 分 (0,1)
玩家 0 玩 11101 分数 (1,1)
玩家 1 打出 10111 分 (1,1)
玩家 0 玩 11111 score(2,1)
玩家 1 获胜
或者
玩家 0 玩 10101 分数 (1,0)
玩家 1 打出 11101 分 (1,1)
玩家 0 玩 10111 分数 (1,1)
玩家 1 打出 11111 分 (1,1)
玩家 0 获胜
如上图所示，玩家 0 可以通过在第一步中创建回文而不是反转字符串来改善结果。因此，最优的定义取决于游戏的最终结果，而不是简单地select选择最好的游戏在任何给定的游戏阶段可用的选项。
实现此逻辑的方法要求首先确定所有游戏状态，然后在每个回合中为玩家采用最佳 end-game 解决方案路径。
然后第一步需要我们创建所有游戏状态的连接图 (GameTree)。为了跟踪游戏每一步的游戏状态，我创建了一个 GameState Class。 class 的一个实例将用于定义 GameTree 的每个节点。 GameState 的每个实例将定义：
- 输入得分 [玩家 1，玩家 2]
- 玩家在此状态下移动
- 输入字符串
- 前一步是反向标志True/False
- 之前的游戏状态
- child 游戏状态
- 每个 child
的 end_point 分数
因此，使用上面的示例，生成的简化树将符合以下内容，其中每个节点由 (Player, String_state, score, children) 描述：
GS0=[0: '10100', (0,0), [GS1, ..]]
GS1 = [1: '00101', (0,0), [GS3, ..]]
GS3 = [0, '10101', (0,1), [GS4, ..]]
GS4 = [1: '11101', (1,1). [GS5]]
GS5 = [0: '10111', (1,1), [GS6, ..]]
GS6 = [1: '11111', (2,1), []]
GS2 = [1: '10101', (1,0), [GS7, ..]]
GS7 = [0: '11101', (1,1), [GS8, ..]]
GS8 = [1: '10111', (1,1), [GS9]]
GS9 = [0: '11111', (1,2), []]
一旦定义了 GameTree 图，就可以使用深度优先搜索 (DFS) 算法沿着树的每个分支向下移动，直到找到叶节点（即没有 [=125= 的节点） ]ren), 并将叶节点得分回传给前一个节点。在多个选项可用的每个节点，tghe 函数将为玩家 select 最佳解决方案并将该解决方案传递给前一个节点，这将继续返回直到搜索所有路径并且最佳 end-game 移动对于第一个玩家可以确定。以下代码实现了这种方法。
# Utility functions to assist in implementing optimal play
def is_palindrome(z):
# Returns True if s is a palindrome
return z == z[::-1]
def find_palindrome(s):
""" Returns a list of indexes that if switched
will result in a palindrome position"""
rslt = []
k = ''
for i, d in enumerate(s):
k += d
if d == '0':
j = k[:i] + '1' + s[i+1:]
if is_palindrome(j):
rslt.append(i)
return rslt
def get_bestScore(l, plr):
""" Return best score for existing move options"""
best = None
scr = None
for sc in l:
rslt = sc[(plr+1)%2] - sc[plr]
if best == None:
best = rslt
scr = sc
else:
if rslt > best:
best = rslt
scr = sc
return scr
def find_BestMove(node):
# Recursive function to search for leaf nodes and bactrack to define best play option
ptr = 0
if node.children:
while len(node._end_options) < len(node.children):
node._end_options.append(find_BestMove(node.children[ptr]))
ptr += 1
return get_bestScore(node._end_options, node.player)
else:
return node.score
#Class to maintain game tree node states
class GameState:
def __init__(self, parent, str_in, rvflg, score):
self._prior = parent
self._str = str_in
self._player = 0
self._score = score
self._rvflg = rvflg
self._children = []
self._end_options = []
if self._prior:
self._player = (self._prior.player + 1)%2
self._children.extend(self.get_move_options())
def __gt__(self, other):
return self.score[self.player] < other.score[other.player]
def __repr__(self):
return f"GS{self._id:02} - [{self.player}: {self.state_string} => {self.score}"
def get_move_options(self):
''' return a list of next game states for each possible move
from current postion. The list is sorted so that the best moves are
at the begining of the list'''
mv_opts = []
if not self.rvflg and not is_palindrome(self._str):
mv_opts.append(GameState(self, self._str[::-1], True, self.score))
sc = self._score.copy()
sc[self._player] += 1
popts = find_palindrome(self._str)
for i, d in enumerate(self._str):
if d == '0' and i not in popts:
popts.append(i)
for m in popts:
nw_str = self._str[:m]+'1'+self._str[m+1:]
mv_opts.append(GameState(self, nw_str, False, sc))
return mv_opts
@property
def state_string(self):
return self._str
@property
def rvflg(self):
return self._rvflg
@property
def score(self):
return self._score
@property
def player(self):
return self._player
@property
def children(self):
return self._children
def playGame(instr):
# Function to play the Game by building the Gamestate tree and playing optimum moves
players = ["Peter", 'Henry']
cgs = GameState(None,instr, False, [0,0])
rslt = find_BestMove(cgs)
out_str = ''
if rslt[0] == rslt[1]:
out_str = 'Draw'
elif rslt[0] < rslt[1]:
out_str = players[0]
else:
out_str = players[1]
return out_str
以上代码为例：
test_cases = [('00', 'Henry'), ('100', "Draw"), ('10100', 'Peter'), ('0010', 'Peter')]
for tc in test_cases:
print(f"For Input String '{tc[0]}', Expected {tc[1]} and got: {playGame(tc[0])}")
产生以下输出：
For Input String '00', Expected Henry and got: Henry
For Input String '100', Expected Draw and got: Draw
For Input String '10100', Expected Peter and got: Peter
For Input String '0010', Expected Peter and got: Peter
我正在尝试编码挑战 Link
对于没有帐户的人，这里是复制的： 彼得和亨利正在玩一个由字符“0”和“1”组成的长度为 n 的字符串 s 的游戏。两位玩家交替轮流，但彼得先轮到。
在每个回合中，玩家都可以对字符串执行以下操作之一：
Select 任意 i，其中 s[i]= '0' 并将 s[i] 更改为 '1' 并支付 1 卢比。另一个操作是反转整个字符串并支付 0 卢比。仅当字符串当前不是回文且上次执行的操作不是反向时才允许执行此操作。如果彼得把弦反了，那么下一回合亨利就不能反弦了，反之亦然。
反转字符串意味着将其字母从最后到第重新排序。例如“01001”反转后会变成“10010”
当字符串的每个字符都变成'1'时，游戏结束。到此为止花费最少卢比的玩家赢得游戏，如果双方花费相等的卢比则平局。如果两个玩家都发挥最佳，确定谁是赢家还是平局。
输入格式
第一行包含一个整数 t 。然后是t个测试用例。
每个测试用例的第一行包含一个整数 n 。
每个测试用例的第二行包含长度为n的字符串s，由字符'0'和'1'组成。保证字符串s中至少包含一个'0'
输出格式
对于每个测试用例，在新行中打印一个单词：
“PETER”，如果彼得赢得比赛，“HENRY”，如果亨利赢得比赛，“DRAW”，如果比赛以平局结束。
示例输入 0
2 3个 110 2个 00
示例输出 0
彼得 亨利
解释 0
在例子的第一个测试用例中，在第一步中，彼得将使用第二次操作来反转字符串，因为执行第一次操作无论如何都会导致他的损失。这也迫使亨利使用第一个操作。在第 2 步中，Henry 必须执行第 1 个操作，因为第 2 个操作不能连续执行两次。字符串的所有字符都是'1'，游戏结束。彼得花费 0 卢比，而亨利花费 1 卢比。因此，彼得获胜。
这是代码，我是递归函数的新手，这段代码导致最大递归limit.Any帮助将不胜感激。
def Winner(c,counter):
if sum(c) == b:
if len(set(counter.values)) == 1:
print("DRAW")
return
else:
d=index(min(counter.values()))
print(counter.keys(d))
return
if c == c[::-1]:
for i in c:
if i==0:
c[i] =1
break
counter["PETER"] +=1
c=c[::-1]
print(c)
Winner(c,counter)
else:
c= c[::-1]
for i in c:
if i==0:
c[i]=1
break
counter["HENRY"] +=1
Winner(c,counter)
a=int(input())
p,h=0,0
counter={"PETER":0,"HENRY":0}
global b
for i in range(a):
b=int(input())
c=list(map(int,input().strip().split()))
Winner(c,counter)
我花了几天时间试图理解您的代码和它的逻辑，但它不会 运行 并且它的逻辑布局似乎有缺陷这一事实阻碍了我。因此，我开始自己分析游戏问题并构建自己的解决方案。为此，为了清楚地说明我认为的游戏规则，我尽可能简洁明了地重申了这些规则：
游戏
Peter 和 Henry 正在玩一个由字符“0”和“1”组成的长度为 n 的字符串 s 的游戏。两位玩家交替轮流，但彼得总是先轮到。
该剧
在每个回合中，玩家可以对字符串执行以下操作之一：
- Select 任意 i，其中 s[i]= '0' 并将 s[i] 更改为 '1' 并支付 1 卢比。
- 反转整个字符串并支付 0 卢比。如果出现以下情况，则不允许使用此选项：
- 之前的玩家推翻了字符串
- 字符串是回文
结束游戏
当字符串的每个字符都变成'1'时，游戏结束。
花费最少的玩家获胜。如果双方花费相等，则为平局。
问题
如果两个玩家都发挥最佳，确定谁会赢或者游戏结果是否平局。
分析
假设以上内容准确描述了游戏玩法：
任何解决方案需要解决的第一个问题是确定 'Optimal Play.' 的含义 通过初步观察，我们可以推断出任何玩家最佳玩法必须符合：
- select 如果可能，字符串反转 - 这会迫使对手做出一个数字 selection 罚球
- 如果反转不是一个选项，select 一个反转的数字会产生回文。这要求对手也切换一个数字，因此惩罚相等
- 如果不能创建回文，select一个索引，惩罚1 改值
然而，经过进一步评估，这不一定是正确的优先级，例如以下：
开始：10100,
玩家 0 玩 00101 score(0,0)
玩家 1 打出 10101 分 (0,1)
玩家 0 玩 11101 分数 (1,1)
玩家 1 打出 10111 分 (1,1)
玩家 0 玩 11111 score(2,1)
玩家 1 获胜
或者
玩家 0 玩 10101 分数 (1,0)
玩家 1 打出 11101 分 (1,1)
玩家 0 玩 10111 分数 (1,1)
玩家 1 打出 11111 分 (1,1)
玩家 0 获胜
如上图所示，玩家 0 可以通过在第一步中创建回文而不是反转字符串来改善结果。因此，最优的定义取决于游戏的最终结果，而不是简单地select选择最好的游戏在任何给定的游戏阶段可用的选项。
实现此逻辑的方法要求首先确定所有游戏状态，然后在每个回合中为玩家采用最佳 end-game 解决方案路径。
然后第一步需要我们创建所有游戏状态的连接图 (GameTree)。为了跟踪游戏每一步的游戏状态，我创建了一个 GameState Class。 class 的一个实例将用于定义 GameTree 的每个节点。 GameState 的每个实例将定义：
- 输入得分 [玩家 1，玩家 2]
- 玩家在此状态下移动
- 输入字符串
- 前一步是反向标志True/False
- 之前的游戏状态
- child 游戏状态
- 每个 child 的 end_point 分数
因此，使用上面的示例，生成的简化树将符合以下内容，其中每个节点由 (Player, String_state, score, children) 描述：
GS0=[0: '10100', (0,0), [GS1, ..]]
GS1 = [1: '00101', (0,0), [GS3, ..]]
GS3 = [0, '10101', (0,1), [GS4, ..]]
GS4 = [1: '11101', (1,1). [GS5]]
GS5 = [0: '10111', (1,1), [GS6, ..]]
GS6 = [1: '11111', (2,1), []]
GS2 = [1: '10101', (1,0), [GS7, ..]]
GS7 = [0: '11101', (1,1), [GS8, ..]]
GS8 = [1: '10111', (1,1), [GS9]]
GS9 = [0: '11111', (1,2), []]
一旦定义了 GameTree 图，就可以使用深度优先搜索 (DFS) 算法沿着树的每个分支向下移动，直到找到叶节点（即没有 [=125= 的节点） ]ren), 并将叶节点得分回传给前一个节点。在多个选项可用的每个节点，tghe 函数将为玩家 select 最佳解决方案并将该解决方案传递给前一个节点，这将继续返回直到搜索所有路径并且最佳 end-game 移动对于第一个玩家可以确定。以下代码实现了这种方法。
# Utility functions to assist in implementing optimal play
def is_palindrome(z):
# Returns True if s is a palindrome
return z == z[::-1]
def find_palindrome(s):
""" Returns a list of indexes that if switched
will result in a palindrome position"""
rslt = []
k = ''
for i, d in enumerate(s):
k += d
if d == '0':
j = k[:i] + '1' + s[i+1:]
if is_palindrome(j):
rslt.append(i)
return rslt
def get_bestScore(l, plr):
""" Return best score for existing move options"""
best = None
scr = None
for sc in l:
rslt = sc[(plr+1)%2] - sc[plr]
if best == None:
best = rslt
scr = sc
else:
if rslt > best:
best = rslt
scr = sc
return scr
def find_BestMove(node):
# Recursive function to search for leaf nodes and bactrack to define best play option
ptr = 0
if node.children:
while len(node._end_options) < len(node.children):
node._end_options.append(find_BestMove(node.children[ptr]))
ptr += 1
return get_bestScore(node._end_options, node.player)
else:
return node.score
#Class to maintain game tree node states
class GameState:
def __init__(self, parent, str_in, rvflg, score):
self._prior = parent
self._str = str_in
self._player = 0
self._score = score
self._rvflg = rvflg
self._children = []
self._end_options = []
if self._prior:
self._player = (self._prior.player + 1)%2
self._children.extend(self.get_move_options())
def __gt__(self, other):
return self.score[self.player] < other.score[other.player]
def __repr__(self):
return f"GS{self._id:02} - [{self.player}: {self.state_string} => {self.score}"
def get_move_options(self):
''' return a list of next game states for each possible move
from current postion. The list is sorted so that the best moves are
at the begining of the list'''
mv_opts = []
if not self.rvflg and not is_palindrome(self._str):
mv_opts.append(GameState(self, self._str[::-1], True, self.score))
sc = self._score.copy()
sc[self._player] += 1
popts = find_palindrome(self._str)
for i, d in enumerate(self._str):
if d == '0' and i not in popts:
popts.append(i)
for m in popts:
nw_str = self._str[:m]+'1'+self._str[m+1:]
mv_opts.append(GameState(self, nw_str, False, sc))
return mv_opts
@property
def state_string(self):
return self._str
@property
def rvflg(self):
return self._rvflg
@property
def score(self):
return self._score
@property
def player(self):
return self._player
@property
def children(self):
return self._children
def playGame(instr):
# Function to play the Game by building the Gamestate tree and playing optimum moves
players = ["Peter", 'Henry']
cgs = GameState(None,instr, False, [0,0])
rslt = find_BestMove(cgs)
out_str = ''
if rslt[0] == rslt[1]:
out_str = 'Draw'
elif rslt[0] < rslt[1]:
out_str = players[0]
else:
out_str = players[1]
return out_str
以上代码为例：
test_cases = [('00', 'Henry'), ('100', "Draw"), ('10100', 'Peter'), ('0010', 'Peter')]
for tc in test_cases:
print(f"For Input String '{tc[0]}', Expected {tc[1]} and got: {playGame(tc[0])}")
产生以下输出：
For Input String '00', Expected Henry and got: Henry
For Input String '100', Expected Draw and got: Draw
For Input String '10100', Expected Peter and got: Peter
For Input String '0010', Expected Peter and got: Peter