打印硬币游戏中获胜可能性的代码中的问题

Question

我正在使用回溯递归来解决以下问题。第一个代码“ CoinGame1”提供正确的解决方案，但是第二个代码“ CoinGame2”提供错误的解决方案。我想，发生了一些不好的事情，因为我在递归调用之前先将字符串反转了。

*硬币游戏：爱丽丝和鲍勃正在使用一堆硬币玩游戏。玩家依次从堆中挑出几个硬币。每个玩家每回合可以选择1，2或4个硬币。每次允许玩家挑选硬币时，获得最后一个硬币的玩家就是获胜者。众所周知，最后剩下1，2或4个硬币时，首轮玩家肯定会根据需要选择1，2或4个硬币并获胜。例如，如果最后有2个硬币并且爱丽丝是第一个选择的玩家，那么她肯定会选择2个硬币并获胜。给定硬币数量和玩家顺序（这意味着第一和第二位玩家选择硬币），编写一个程序来打印游戏获胜者的所有可能性，

F（1，{alice，bob}）

爱丽丝

F（6，{alice，bob}）

爱丽丝，鲍勃，鲍勃，爱丽丝，鲍勃，鲍勃

F（4，{alice，bob}）

爱丽丝

F（3，{alice，bob}）

鲍勃，鲍勃*

                         f（6，{A，B}）                                     

                     / \ \

            f（5，{B，A}）f（4，{B，A}）f（2，{B，A}）

          / | \ B胜B胜

f（4，{A，B}）f（3，{A，B}）f（1，{A，B}） 

胜利/ | \一胜        

          / | \

f（2，{B，A}）f（1，{B，A}）f（-1，{B，A}）

B胜B胜       

//解决方案1

public class CoinGame1

{

   public static void Count(int n, String[] s)   // n: no. of coins 

                                               //s:{"Alice","Bob"} (order) 

  {

       if(n>0)

       {

           if(n==1 || n==2 || n==4) System.out.println( s[0] );  // if 1/2/4 

                                 //coins left, the one with first chance wins

           else

           { 

               Count(n-1,new String[]{s[1],s[0]});

               Count(n-2,new String[]{s[1],s[0]});

               Count(n-4,new String[]{s[1],s[0]});  

           }

       }

  }

  

java CoinGame1 A B B A B B

//解决方案2

public class CoinGame2

{

   public static void Count(int n, String[] s)          // n: no. of coins    

                                                 //s:{"Alice","Bob"} (order) 

  {

       if(n>0)

       {

           if(n==1 || n==2 || n==4) System.out.println( s[0] );  // if 1/2/4 

                                //coins left, the one with first chance wins

           else

           {

               String temp = s[0]; s[0] = s[1]; s[1] = temp;     // reverse s

               Count(n-1,s);

               Count(n-2,s);

               Count(n-4,s);  

           }

       }

  }

  

java CoinGame2 A B B B B B

Answer 1

SOLUTION2中的更改（现在可以提供正确的结果）导入java.util。*;    公共类CoinGame2    {       public static void Count（int n，String [] s）// n：否。硬币，s：{“ Alice”，“ Bob”}（顺序）      {           如果（n> 0）           {               if（n == 1 || n == 2 || n == 4）System.out.println（s [0]）; //如果剩下1/2/4个硬币，则有机会赢得的硬币               别的               {                  //字符串temp = s [0]; s [0] = s [1]; s [1] =温度；//反转s                   String [] t = Arrays.copyOfRange（s，0，s.length）;                   字符串温度= t [0]; t [0] = t [1]; t [1] =温度；                   计数（n-1，t）;                   计数（n-2，t）;                   计数（n-4，t）;                 }           }      }      公共静态void main（String [] args）          {              String [] order = new String [] {“ A”，“ B”};              Count（6，order）;          }    }

Answer 2

有时它有助于简化递归问题。我重新编写了您的问题，但我以5个硬币开始，选择了1或2。这样，第一个选择器将始终获胜。您唯一会输的方法是连续两次选择，结果不言而喻。运行此代码，结论很明显，如上所述，整个过程都在运行s的相同实例。    public static void Count(int n, String[] s)          // n: no. of coins    //s:{"Alice","Bob"} (order)    {        if(n>0)        {            if(n==1 || n==2 ) System.out.println( s[0] );  // if 1/2/4                //coins left, the one with first chance wins            else            {                String temp = s[0]; s[0] = s[1]; s[1] = temp;     // reverse s                Count(n-1,s);                Count(n-2,s);            }        }    }    public static void main(String[] args)    {        String[] order = new String[]{"A","B"};        Count(5,order);    }    // the result is B,B,B,A,A