C语言解决常胜将军问题

78 阅读 0 评论 52 点赞

我是靠谱客的博主想人陪蚂蚁，最近开发中收集的这篇文章主要介绍C语言解决常胜将军问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述：

有21张纸牌，两个人依次取，每次每人只可以取走1~4张，不能多取，也不能不取，谁取到最后一张谁输。编写一个人机对弈程序，要求人先取，计算机后取；结果计算机为“常胜将军”。

问题分析：

这样思考这个问题，要想让计算机是“常胜将军”，也就是要然取到最后1张纸牌。这样只有一种可能，就是让计算机只剩1张纸牌给人，因为此时人至少取1张纸牌。其他的情况都不能保证计算机常胜。

于是，问题转化为“有20张纸牌，两人轮流取，每人每次可以取走1~4张，不可多取，也不能不取，要求人先取，计算机后取，谁取到最后一张纸牌谁赢”。为了计算机能够取到最后一张纸牌，就要保证最后一轮抽取（人先取一次，计算机再取一次）之前剩下5根火柴。因为只有这样才能保证无论人怎样取火柴，计算机能将其余的火柴全部取走。

于是，问题又转化为“15张纸牌，两人轮流取，每人每次可以取走1~4张，不可多取，也不能不取，要求人先取，计算机后取，保证计算机取到最后一张纸牌”。同样的道理，为了让计算机取到最后一张纸牌，就要保证最后一轮的抽取（人先取一次，计算机再取一次）之前剩下五根火柴。

于是，问题又转化为10张纸牌的问题...，依次类推。

算法设计：

根据以上分析，可以得出这样的结论：21根纸牌，在人先取计算机后取。每次取1~4张的前提下，只要保证每一轮的抽取（人先抽取一次，计算机再取一次）时，人抽到的纸牌数与计算机抽到的纸牌数之和为5，就可以实现计算机的常胜不败。

完整代码如下：

#include <stdio.h>

int main()
{
        int computer,people,spare = 21;
        printf("---------------------------------n");
        printf("--------快乐码呀 www.happymaya.cn---------n");
        printf("--------你不能战胜我，不信试试---------n");
        printf("---------------------------------nn");
        printf("Game begin:nn");
        int flag = 1;
        while(flag)
        {
                printf("--------目前还有纸牌%d张---------n",spare);
                printf("People:");
                scanf("%d",&people);
                if(people<1 || people>4 || people>spare)
                {
                        printf("你违规了，你取得纸牌数量有问题!nn");
                        continue;
                }
                spare = spare - people;
                if(spare == 0)
{
                        printf("nComputer win! Game Over!n");
                        break;
                }
                computer = 5- people;
                spare = spare - computer;
                printf("Computer:%d n",computer);
                if(spare == 0)
                {
                        printf("nPeople win! Game Over!n");
                        break;
                }
        }
        return 0;
}

运行结果，如下图：