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

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胜       //解决方案1public 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//解决方案2public 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