算法每日一题（一）

LNH_Sniper

问题：现在有21根火柴，两个人轮流取，每人每次可以取走1至4根，不可多取，也不能不取，谁取最后一根火柴谁输。请编写一个程序进行人机对弈，要求人先取，计算机后取；计算机一方为“常胜将军”。


每次问题，会在当天发布解题思路和相应程序。发题时间为上午（本次除外），解答时间为晚上8点。

chao_prince

21 = 4 * 5 + 1,
所以只要每次取的总和为5根，最后一根必定是玩家取到。

/*
**        问题：现在有21根火柴，两个人轮流取，
**        每人每次可以取走1至4根，不可多取，也不能不取，
**        谁取最后一根火柴谁输。请编写一个程序进行人机对弈，
**        要求人先取，计算机后取；计算机一方为“常胜将军”。
**        By 小锅
**        7/4/11
*/

#include <stdio.h>

int main()
{
        int StickNum = 21;
        int i;
        
        printf( "Game Start!\n" );
        while( StickNum > 0 )
        {
                do{
                        printf( "How many sticks do you want to take (1 ~ %d) : ", StickNum > 4 ? 4 : StickNum );
                        scanf( "%d", &i );
                }while( i < 1 || i > 4 || i > StickNum );
                if( StickNum - i > 0 )
                        printf( "%d stick left in the pile.\n", StickNum - 1 );
                if( StickNum - i <= 0 )
                {
                        printf( "You have taken the last stick!\n" );
                        printf( "You Lose!\nGanme Over!\n" );
                        break;
                }
                else
                {
                        printf( "Computer take %d stick(s).\n", 5 - i );
                        StickNum -= 5;
                        printf( "%d stick left in the pile.\n", StickNum );
                }
                        
        }
        return 0;
}

LNH_Sniper

正如chao_price所说，本题的核心就是：每轮抽取，人与计算机抽取之和为5，即可实现计算机的长胜不败

#include "stdio.h"

int main()
{
int computer, people, spare;
spare = 21;
printf("Game Begin:\n\n");

while(1)
{
printf("-----------Ä¿Ç°»¹Óлð²ñ %d ¸ù------------\n",spare);
printf(" People: ");
scanf("%d",&people);
if( people < 1 || people > 4 || people > spare )
{
printf("You Take A Wrong Number!!\n\n");
continue;
}
spare = spare - people;
if( spare == 0 )
{
printf("\nComputer Win!!\n Game Over!!\n");
break;
}
computer = 5 - people;
spare = spare - computer;
printf("Computer :%d \n",computer);
if( spare == 0 )
{
printf("\n People Win!!\n Game Over!!\n");
break;
}
}

return 0;
}

asd82937121

这就是谁先取谁输啊

dstttfgcd

厉害啊！知道答案了觉得也没那么复杂了{:1_1:}，不过自己开始的时候还是不知道怎么下手呢！～

wangyexin

这是博弈问题，n根火柴，一次最多取m根的话，只要n%（m+1）!=0，就是先手必胜

zyp2011_mit

这是博弈问题，n根火柴，一次最多取m根的话，只要n%（m+1）!=0，就是先手必胜~
我赞成这个~

Davishu

:lol好贴 学习了

z1446773686

#用Python写的(*^__^*) 嘻嘻……
def matchstick(number = 21):
                import random
                while( number > 0 ):
                                human = input('请输入1~4根火柴的数量\n您的选择是:')
                                while(not human.isdigit()) or ((human == '0' ) or (human > '4')):
                                                human = input('请重新输入1~4根火柴的数量\n您的选择是:')
                                human = int(human)
                                number -= human
                                if(number <= 0):
                                                print('\n此时火柴的数量为:%d\n' % number)
                                                break
                                if(number > 4):
                                                robot = random.randint(1,4)
                                elif(number < 4):
                                                robot = random.randint(1,3)
                                elif(number < 3):
                                                robot = random.randint(1,2)
                                elif(number == 1):
                                                robot = 1
                                print('\'常胜将军\'选择的数量是：%d' % robot)
                                number -= robot
                                print('\n此时火柴的数量为:%d\n' % number)
                if(number - robot <= 0):
                                human = input('请输入大侠英名：')
                                print('恭喜\'%s\'您获得了胜利!' % human)
                if(number - human <= 0):
                                print('恭喜\'常胜将军\'获得了胜利！' )

matchstick()

z1446773686

z1446773686 发表于 2018-2-5 11:10
#用Python写的(*^__^*) 嘻嘻……
def matchstick(number = 21):
                import random

可是我自己写的哦(*^__^*) 嘻嘻……

z1446773686

z1446773686 发表于 2018-2-5 11:10
#用Python写的(*^__^*) 嘻嘻……
def matchstick(number = 21):
                import random

还是有不足之处，恩慢慢改进不捉急

z1446773686

#改进后的
def matchstick(number = 21):
                import random
                print('\n此时火柴的数量为:%d\n' % number)
                while( number > 0 ):
                                human = input('请输入1~4根火柴的数量\n您的选择是:')
                                while(not human.isdigit()) or ((human == '0' ) or (human > '4')):
                                                human = input('请重新输入1~4根火柴的数量\n您的选择是:')
                                human = int(human)
                                number -= human
                                print('此时火柴的数量为:%d\n' % number)
                                if(number <= 0):
                                                print('\n此时火柴的数量为:%d\n' % number)
                                                print('恭喜\'常胜将军\'获得了胜利！' )
                                else:
                                                if(number == 1):
                                                                robot = 1
                                                elif(number < 3):
                                                                robot = random.randint(1,2)
                                                elif(number < 4):
                                                                robot = random.randint(1,3)
                                                elif(number > 4):
                                                                robot = random.randint(1,4)
                                                print('\'常胜将军\'选择的数量是：%d' % robot)
                                                number -= robot
                                                print('\n此时火柴的数量为:%d\n' % number)
                                                if(number <= 0):
                                                                human = input('请输入大侠英名：')
                                                               
                                                                print('恭喜\'%s\'您获得了胜利!' % human)
                                
matchstick()