算法每日一题（一）

LNH_Sniper

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


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

chao_prince

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

1. /*
   
2. **        问题：现在有21根火柴，两个人轮流取，
   
3. **        每人每次可以取走1至4根，不可多取，也不能不取，
   
4. **        谁取最后一根火柴谁输。请编写一个程序进行人机对弈，
   
5. **        要求人先取，计算机后取；计算机一方为“常胜将军”。
   
6. **        By 小锅
   
7. **        7/4/11
   
8. */
   
9. 
   
10. #include <stdio.h>
    
11. 
    
12. int main()
    
13. {
    
14.         int StickNum = 21;
    
15.         int i;
    
16.        
    
17.         printf( "Game Start!\n" );
    
18.         while( StickNum > 0 )
    
19.         {
    
20.                 do{
    
21.                         printf( "How many sticks do you want to take (1 ~ %d) : ", StickNum > 4 ? 4 : StickNum );
    
22.                         scanf( "%d", &i );
    
23.                 }while( i < 1 || i > 4 || i > StickNum );
    
24.                 if( StickNum - i > 0 )
    
25.                         printf( "%d stick left in the pile.\n", StickNum - 1 );
    
26.                 if( StickNum - i <= 0 )
    
27.                 {
    
28.                         printf( "You have taken the last stick!\n" );
    
29.                         printf( "You Lose!\nGanme Over!\n" );
    
30.                         break;
    
31.                 }
    
32.                 else
    
33.                 {
    
34.                         printf( "Computer take %d stick(s).\n", 5 - i );
    
35.                         StickNum -= 5;
    
36.                         printf( "%d stick left in the pile.\n", StickNum );
    
37.                 }
    
38.                        
    
39.         }
    
40.         return 0;
    
41. }

复制代码

LNH_Sniper

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

1. 
   

复制代码

1. #include "stdio.h"
   
2. 
   
3. int main()
   
4. {
   
5. int computer, people, spare;
   
6. spare = 21;
   
7. printf("Game Begin:\n\n");
   
8. 
   
9. while(1)
   
10. {
    
11. printf("-----------&Auml;&iquest;&Ccedil;°&raquo;&sup1;&Oacute;&ETH;&raquo;&eth;&sup2;&ntilde; %d &cedil;ù------------\n",spare);
    
12. printf(" People: ");
    
13. scanf("%d",&people);
    
14. if( people < 1 || people > 4 || people > spare )
    
15. {
    
16. printf("You Take A Wrong Number!!\n\n");
    
17. continue;
    
18. }
    
19. spare = spare - people;
    
20. if( spare == 0 )
    
21. {
    
22. printf("\nComputer Win!!\n Game Over!!\n");
    
23. break;
    
24. }
    
25. computer = 5 - people;
    
26. spare = spare - computer;
    
27. printf("Computer :%d \n",computer);
    
28. if( spare == 0 )
    
29. {
    
30. printf("\n People Win!!\n Game Over!!\n");
    
31. break;
    
32. }
    
33. }
    
34. 
    
35. return 0;
    
36. }

复制代码

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()