【100个python算法超详细讲解】

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

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

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