论坛 › 数据结构与算法 › 算法每日一题（一）

LNH_Sniper 发表于 2011-7-4 19:48:57

算法每日一题（一）

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


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

chao_prince 发表于 2011-7-4 21:27:40

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 发表于 2011-7-5 01:31:50

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



#include "stdio.h"

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

while(1)
{
printf("-----------&Auml;&iquest;&Ccedil;°&raquo;&sup1;&Oacute;&ETH;&raquo;&eth;&sup2;&ntilde; %d &cedil;ù------------\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 发表于 2011-7-6 10:58:20

这就是谁先取谁输啊

dstttfgcd 发表于 2011-9-19 10:53:19

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

wangyexin 发表于 2011-9-20 19:59:13

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

zyp2011_mit 发表于 2011-10-21 13:43:41

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

Davishu 发表于 2011-10-24 17:00:30

:lol好贴 学习了

z1446773686 发表于 2018-2-5 11:10:48

#用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 发表于 2018-2-5 11:12:16

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


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

z1446773686 发表于 2018-2-5 11:15:40

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


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

z1446773686 发表于 2018-2-5 12:20:04

#改进后的
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()

查看完整版本: 算法每日一题（一）