java - 第 100 场比赛 - CanIWin()

Question

问题:

1. 两名玩家从共同的号码池中挑选号码以达到总和。
2. 达到/超过目标值的玩家获胜。
3. 问题是找出玩家 1 是否可以执行获胜策略 - 对于给定的总数和一组数字。

我的方法:

假设两个玩家都从可用池中选择最佳数字。 最佳，我的意思是 -

1. 检查池中可用的最大数是否 >= 剩余值。 [yes]=> 返回可用的最高值。

2. 如果不可能获胜，请选择池中不能保证下一回合获胜的最高可用号码(RequiredToWin - HighestNumberInThePool)。

我刚刚提出“一个”解决方案并编写了代码。我正在尝试分析它是否是仪式？最佳，在时间，空间方​​面。还试图了解如何改进我的编码约定——全局变量和我使用条件语句的方式。这是解决方案吗？

在示例中 - 我使用了从 100 到 105 的预期总和 - 以显示输出中的最佳选择。查看玩家 1 从可用池中选择 5 个 [7,6,5,4,3,2,1]

编辑 这不是问题的解决方案。这种方法在 {pool:[1-5], Total:12} 的情况下失败。该函数表示，Player-2 总是赢，但是如果 Player-1 以 3 开始，他总是可以赢。

/* In "the 100 game," two players take turns adding, to a running 
total, any integer from 1..10. The player who first causes the running 
total to reach or exceed 100 wins. 
What if we change the game so that players cannot re-use integers? 
For example, if two players might take turns drawing from a common pool of numbers 
of 1..15 without replacement until they reach a total >= 100. This problem is 
to write a program that determines which player would win with ideal play. 

Write a procedure, "Boolean canIWin(int maxChoosableInteger, int desiredTotal)", 
which returns true if the first player to move can force a win with optimal play. 

Your priority should be programmer efficiency; don't focus on minimizing 
either space or time complexity. 
*/

    package Puzzles;

    import java.util.List;
    import java.util.ArrayList;

    public class The100Game{
        List<Integer> pool;
        int raceTo;

        The100Game(int poolMax, int finalSum){
            /*  If (finalSum > combined sum of all numbers). 
             *  This is an impossible problem to solve  
             */
            if(finalSum > ((poolMax*poolMax + poolMax)/2)){
                throw new IllegalArgumentException("Expected sum cannot be achieved!");
            }

            raceTo = finalSum;
            pool = new ArrayList<Integer>();
            for(int i=0;i<poolMax;i++)
                pool.add(i+1);
        }

        /*  Autoplay the game with optimal mooves   */
        boolean canIWin(){
            int turns = 0;
            while(raceTo>0){
                turns++;
                System.out.println("Player"+( (turns%2==0)?"2":"1" )+" ==> "+pickANumber()+"   == Remaining ["+raceTo+"]");
            }
            return (turns%2==1);
        }

        /*  Pick an Optimal number, so to win 
         *  or prevent he opponent from winning 
         */
        int pickANumber(){
            int leastMax = -1;
            int len = pool.size();
            for(int i=len-1;i>=0;i--){
                int tmp = pool.get(i);
                if(tmp>=raceTo){
                    /*  Winning Pick */
                    pool.remove(i);
                    raceTo -= tmp;
                    return tmp; 
                }else{
                    if(leastMax > 0){
                        /*  Picking the highest number available in the pool might let the next player win. 
                         *  So picking a number < leastMax, if available - to gaurentee otherwise.  */
                        if(tmp < leastMax){
                            pool.remove(i);
                            raceTo -= tmp;
                            return tmp;
                        }else{
                            continue;
                        }
                    }   

                    if(i-1 >= 0) {
                        /*  We know, the highest number available in the pool is < raceTo (target sum)
                         *  Check in the pool 
                         *  if the sum of the highest number + nextHighest number >=  raceTo (target sum)
                         *      [True]  => Skip both the numbers and look for a number < the LeastMax 
                         *                   so the opposite player does not win.
                         *      [False] => The highest number in the pool is the best pick
                         */
                        if(tmp+pool.get(i-1) < raceTo){
                            pool.remove(i);
                            raceTo -= tmp;
                            return tmp;
                        }else{
                            leastMax = raceTo - tmp;
                            i--;
                            continue;
                        }
                    }else{
                        pool.remove(i);
                        raceTo -= tmp;
                        return tmp;
                    }
                }
            }

            /*  The raceTo sum cannot be achieved in this turn.
             *  There is no number available in the pool 
             *  that can prevent a Win in the next turn. 
             *  So we return the highest number availble in the pool.
             */
            int tmp = pool.get(pool.size()-1);
            pool.remove(pool.size()-1);
            raceTo -= tmp;
            return tmp;
        }

        public static void main(String[] args){
            The100Game game = new The100Game(15, 105);
            System.out.println("\nPlayer-"+(game.canIWin()?"1":"2")+" wins!");
        }
    }

输出:

--------------------------------------
Player1 ==> 15   == Remaining [90]
Player2 ==> 14   == Remaining [76]
Player1 ==> 13   == Remaining [63]
Player2 ==> 12   == Remaining [51]
Player1 ==> 11   == Remaining [40]
Player2 ==> 10   == Remaining [30]
Player1 ==> 9   == Remaining [21]
Player2 ==> 8   == Remaining [13]
Player1 ==> 5   == Remaining [8]
Player2 ==> 7   == Remaining [1]
Player1 ==> 6   == Remaining [-5]

Player-1 wins!

Answer 1

如果数字是正整数并且可以重新使用(并且在 1 到 N 的连续范围内)，那么您的基本想法基本上是正确的，选择最大的可能数字并不能保证对手在倒数第二步获胜将使总数等于 N+1。那么不管对方怎么做，你都能赢。因此，如果总目标总和 M 可被 N+1 整除，则玩家 2 可以获胜，方法是保持总和始终可被 N+1 整除，否则玩家 1 可以通过首先使总和可被 N+1 整除并窃取玩家 2 的数来获胜战略。如果数字不连续和/或不能重复使用，那么问题似乎要难得多。