# 算法题：硬币游戏赢家，每个玩家都有三个选择

2021年4月30日19:31:57 发表评论 1,052 次浏览

## 本文概述

A和B在玩游戏。一开始有n个硬币。再给两个数字x和y，玩家每走一步都可以选择x、y或l枚硬币。A总是开始游戏。捡到最后一枚硬币的玩家赢得游戏。对于给定的n值，如果a和a都是最优策略，判断a是否会赢。

``````Input :  n = 5, x = 3, y = 4
Output : A
There are 5 coins, every player can pick 1 or
3 or 4 coins on his/her turn.
A can win by picking 3 coins in first chance.
Now 2 coins will be left so B will pick one
coin and now A can win by picking the last coin.

Input : 2 3 4
Output : B``````

n = 0 A不能拾取任何硬币, 因此他损失

n = 1 A可以选择1个硬币并赢得比赛

n = 2 A只能选择1个硬币。现在B将选择1个硬币并赢得比赛

n = 3 4 A将赢得3或4个硬币, 从而赢得比赛

n = 5、6 A将选择3或4个硬币。现在, B将必须从2个硬币中进行选择, 这样A才能获胜。

## C ++

``````//CPP program to find winner of game
//if player can pick 1, x, y coins
#include <bits/stdc++.h>
using namespace std;

//To find winner of game
bool findWinner( int x, int y, int n)
{
//To store results
int dp[n + 1];

//Initial values
dp[0] = false ;
dp[1] = true ;

//Computing other values.
for ( int i = 2; i <= n; i++) {

//If A losses any of i-1 or i-x
//or i-y game then he will
//definitely win game i
if (i - 1>= 0 and !dp[i - 1])
dp[i] = true ;
else if (i - x>= 0 and !dp[i - x])
dp[i] = true ;
else if (i - y>= 0 and !dp[i - y])
dp[i] = true ;

//Else A loses game.
else
dp[i] = false ;
}

//If dp[n] is true then A will
//game otherwise  he losses
return dp[n];
}

//Driver program to test findWinner();
int main()
{
int x = 3, y = 4, n = 5;
if (findWinner(x, y, n))
cout <<'A' ;
else
cout <<'B' ;

return 0;
}``````

## Java

``````//Java program to find winner of game
//if player can pick 1, x, y coins
import java.util.Arrays;

public class GFG {

//To find winner of game
static boolean findWinner( int x, int y, int n)
{
//To store results
boolean [] dp = new boolean [n + 1 ];

Arrays.fill(dp, false );

//Initial values
dp[ 0 ] = false ;
dp[ 1 ] = true ;

//Computing other values.
for ( int i = 2 ; i <= n; i++) {

//If A losses any of i-1 or i-x
//or i-y game then he will
//definitely win game i
if (i - 1>= 0 && dp[i - 1 ] == false )
dp[i] = true ;
else if (i - x>= 0 && dp[i - x] == false )
dp[i] = true ;
else if (i - y>= 0 && dp[i - y] == false )
dp[i] = true ;

//Else A loses game.
else
dp[i] = false ;
}

//If dp[n] is true then A will
//game otherwise  he losses
return dp[n];
}

//Driver program to test findWinner();
public static void main(String args[])
{
int x = 3 , y = 4 , n = 5 ;
if (findWinner(x, y, n) == true )
System.out.println( 'A' );
else
System.out.println( 'B' );
}
}
//This code is contributed by Sumit Ghosh``````

## Python3

``````# Python3 program to find winner of game
# if player can pick 1, x, y coins

# To find winner of game
def findWinner(x, y, n):

# To store results
dp = [ 0 for i in range (n + 1 )]

# Initial values
dp[ 0 ] = False
dp[ 1 ] = True

# Computing other values.
for i in range ( 2 , n + 1 ):

# If A losses any of i-1 or i-x
# or i-y game then he will
# definitely win game i
if (i - 1> = 0 and not dp[i - 1 ]):
dp[i] = True
elif (i - x> = 0 and not dp[i - x]):
dp[i] = True
elif (i - y> = 0 and not dp[i - y]):
dp[i] = True

# Else A loses game.
else :
dp[i] = False

# If dp[n] is true then A will
# game otherwise he losses
return dp[n]

# Driver Code
x = 3 ; y = 4 ; n = 5
if (findWinner(x, y, n)):
print ( 'A' )
else :
print ( 'B' )

# This code is contributed by Azkia Anam``````

## C#

``````//C# program to find winner of game
//if player can pick 1, x, y coins
using System;

public class GFG {

//To find winner of game
static bool findWinner( int x, int y, int n)
{

//To store results
bool [] dp = new bool [n + 1];

for ( int i = 0; i <n+1; i++)
dp[i] = false ;

//Initial values
dp[0] = false ;
dp[1] = true ;

//Computing other values.
for ( int i = 2; i <= n; i++)
{

//If A losses any of i-1 or i-x
//or i-y game then he will
//definitely win game i
if (i - 1>= 0 && dp[i - 1] == false )
dp[i] = true ;
else if (i - x>= 0 && dp[i - x] == false )
dp[i] = true ;
else if (i - y>= 0 && dp[i - y] == false )
dp[i] = true ;

//Else A loses game.
else
dp[i] = false ;
}

//If dp[n] is true then A will
//game otherwise he losses
return dp[n];
}

//Driver program to test findWinner();
public static void Main()
{
int x = 3, y = 4, n = 5;

if (findWinner(x, y, n) == true )
Console.WriteLine( 'A' );
else
Console.WriteLine( 'B' );
}
}

//This code is contributed by vt_m.``````

## 的PHP

``````<?php
//PHP program to find winner of game
//if player can pick 1, x, y coins

//To find winner of game
function findWinner( \$x , \$y , \$n )
{

//To store results
\$dp = array ();

//Initial values
\$dp [0] = false;
\$dp [1] = true;

//Computing other values.
for ( \$i = 2; \$i <= \$n ; \$i ++)
{

//If A losses any of i-1 or i-x
//or i-y game then he will
//definitely win game i
if ( \$i - 1>= 0 and ! \$dp [ \$i - 1])
\$dp [ \$i ] = true;
else if ( \$i - \$x>= 0 and ! \$dp [ \$i - \$x ])
\$dp [ \$i ] = true;
else if ( \$i - \$y>= 0 and ! \$dp [ \$i - \$y ])
\$dp [ \$i ] = true;

//Else A loses game.
else
\$dp [ \$i ] = false;
}

//If dp[n] is true then A will
//game otherwise he losses
return \$dp [ \$n ];
}

//Driver program to test findWinner();
\$x = 3; \$y = 4; \$n = 5;
if (findWinner( \$x , \$y , \$n ))
echo 'A' ;
else
echo 'B' ;

//This code is contributed by anuj_67.
?>``````

``A``