100个python算法超详细讲解：常胜将军

【100个python算法超详细讲解】@谷歌学术

1．问题描述
有火柴21根，两人依次取，每次每人只可取走1～4根，不能多取，
也不能不取，谁取到最后一根火柴谁输。请编写一个人机对弈程序，要
求人先取，计算机后取；计算机为“常胜将军”。
2．问题分析
可以这样思考这个问题：要想让计算机是“常胜将军”，也就是要让
人取到最后一根火柴。这样只有一种可能，那就是让计算机只剩下1根
火柴给人，因为此时人至少取1根火柴。别的情况都不能保证计算机常
胜。
于是问题转换为“有20根火柴，两人轮流取，每人每次可以取走1～4
根，不可多取，也不能不取，要求人先取，计算机后取，谁取到最后一
根火柴谁赢”。为了计算机能够取到最后一根火柴，就要保证最后一轮抽
取（人先取一次，计算机再取一次）之前剩下5棵火柴。因为只有这样
才能保证无论人怎样取火柴，计算机都能将其余的火柴全部取走。
于是问题又转换为“15根火柴，两人轮流取，每人每次可以取走1～4
根，不可多取，也不能不取，要求人先取，计算机后取，保证计算机取
到最后一根火柴”。同样道理，为了让计算机取到最后一根火柴，就要保
证最后一轮的抽取（人先取一次，计算机再取一次）之前剩下5根火
柴。
于是问题又转化为10根火柴的问题……，依次递推。
3．算法设计
根据以上分析，可以得出这样的结论：21根火柴，在人先取计算机
后取、每次取1～4根的前提下，只要保证每一轮的抽取（人先取一次，
计算机再取一次）时人抽到的火柴数与计算机抽到的火柴数之和为5，
就可以实现计算机的常胜不败。
4．完整的程序

根据上面的分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 常胜将军
if __name__ == "__main__":
spare = 21 # 21根火柴
print("--------你不能战胜我，不信试试--------")
print("开始游戏: ")
while 1:
print("--------目前还有火柴 %d 根--------" %spare)
people = int(input("人取火柴：")) # 人取火柴
if people < 1 or people > 4 or people > spare:
print("你违规了，你取的火柴数有问题！")
continue
spare = spare – people # 人取后，剩余的火柴数
# 人取后，剩余的火柴数为0，则计算机
获胜，跳出循环
if spare == 0:
print("计算机获胜，游戏结束！")
break
# 计算机取火柴
computer = 5 – people
spare = spare - computer
print("计算机取火柴：%d" %computer)
# 计算机取后，剩余的火柴数为0，则人
获胜，跳出循环
if spare == 0:
print("人获胜，游戏结束！")
break

5．运行结果
在PyCharm下运行程序，结果如图7.5所示。