算法题（硬币游戏赢家，每个玩家都有三个选择） _游戏

本文概述

C ++
Java
Python3
C#
的PHP

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

让我们以x = 3, y = 4的n为例。
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才能获胜。
我们可以观察到, 只有当A输掉硬币n-1, n-x和n-y时, A才能赢取n个硬币。
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 otherwisehe 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 otherwisehe 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# 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. ?>

输出如下：