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

本文概述

• 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 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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。