python - python 递归函数不停地转

Question

我正在尝试编写一些代码来解决这个数学问题:有 8 支球队，他们都会互相踢足球比赛(所以总共 7+6+...+1 = 28 场比赛)并且他们有结果只有两种机会:赢或输。每支球队至少有 1 胜 1 负的组合有多少种。如果您无法回答问题，请说出来，让我再次尝试解释。问题是我的代码打印无限增加的数字(这是一个无限循环，我在函数中编写了 print 语句来了解问题是什么)这是我的代码，您认为问题是什么？谢谢。

num = 8
team = [0,0,0,0,0,0,0,0]
order = []
how_many_stats = 0
temp = 0

for i in range(num):
    for t in range(i+1 , num):
        order.append([i,t])
total_matches = len(order) - 1
curr_matches = - 1

def do_match():
    global num
    global team
    global order
    global how_many_stats
    global temp
    global total_matches
    global curr_matches
    print(how_many_stats)
    curr_matches += 1
    team[order[curr_matches][0]] += 1                               # first wins

    if not curr_matches == total_matches:
        do_match()
    else:
        for i in range(num):
            if team[i] > 0 and team[i] < 7:                                            #7/8?
                temp += 1

        if temp == num:
            how_many_stats += 1
        temp = 0


    team[order[curr_matches][0]] -= 1                              # take back the action

    team[order[curr_matches][1]] += 1                              # second wins

    if not curr_matches == total_matches:
        do_match()
    else:
        for i in range(num):
            if team[i] > 0 and team[i] < 7:                                         #7/8?
                temp += 1

        if temp == num:
            how_many_stats += 1
        temp = 0


    team[order[curr_matches][1]] -= 1

    curr_matches -= 1
    return

do_match()
print(how_many_stats)

解释:我为比赛声明了一条道路，并将它们放入一个数组中(第一队对第二队，第一队对第三队等)，然后我按照该数组的顺序将它们付诸行动。如果这条路满足或不满足我们的条件，可能会为每场比赛建立一棵关于输赢的树，并在每个分支的末端建立一个控制结构。如果满足，则将how_many_stats的值增加1，并后退一步尝试另一条路，以此类推，如果不满足，则再次后退1步查找其他路。如果已经查看了下面的两个节点，请再次后退，依此类推。

Answer 1

在第 21 行添加一些调试逻辑后:

print("called do_match with num: %d, team: %s, order: %s, how_many_stats: %d, temp: %d, total_matchs: %d, curr_matches: %d" % (
    num, str(team), str(order), how_many_stats, temp, total_matches, curr_matches
))

并让它运行一会儿:

called do_match with num: 8, team: [7, 4, 4, 1, 4, 1, 2, 4], order: [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]], how_many_stats: 0, temp: 0, total_matchs: 27, curr_matches: 26
called do_match with num: 8, team: [7, 4, 4, 1, 4, 0, 3, 3], order: [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]], how_many_stats: 0, temp: 0, total_matchs: 27, curr_matches: 25
...
called do_match with num: 8, team: [7, 4, 4, 1, 3, 1, 3, 4], order: [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]], how_many_stats: 0, temp: 0, total_matchs: 27, curr_matches: 26
called do_match with num: 8, team: [7, 4, 4, 1, 3, 0, 4, 3], order: [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]], how_many_stats: 0, temp: 0, total_matchs: 27, curr_matches: 25

我得出的结论是，你的代码确实终止了，你的问题是你的匹配树中有太多的可能性。

例如，通过将团队数量减少到 4 并再次运行，它确实会终止:

called do_match with num: 4, team: [0, 0, 0, 0], order: [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]], how_many_stats: 0, temp: 0, total_matchs: 5, curr_matches: -1
....
called do_match with num: 4, team: [0, 1, 2, 2], order: [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]], how_many_stats: 32, temp: 0, total_matchs: 5, curr_matches: 4
32

因此，您需要找出一种更好的算法，能够计算匹配数，而无需暴力破解匹配树并计算符合您要求的结果

at least 1 win and 1 lose

例如，您可以计算每支球队恰好赢一场或输一场的可能性数量，然后从可能结果的总数中减去该结果(只需确保不要将它们计入两次，或者可以独立发生)

target=total_number-exactly_one_win-exactly_one_loss+exactly_one_win_and_one_loss