问题：
- 两名玩家从一个共同的号码池中选择号码以达到总和。
- 达到/越过目标值的玩家获胜。
- 问题是要找出玩家 1 是否可以执行一个获胜策略——对于给定的总数和一个数字池。
我的方法：
假设两个玩家都从可用池中选择最佳数字。最优，我的意思是-
检查池中可用的最高数字是否 >= 剩余值。[yes]=> 返回可用的最高值。
如果无法获胜，请选择
RequiredToWin - HighestNumberInThePool池中最大的可用数字（ ），这将不能保证在下一回合中获胜。
我刚刚想出了“一个”解决方案并编写了代码。我试图分析它是否是仪式？就时间、空间而言，是最优的。还试图了解如何改进我的编码约定 - 全局变量和我使用条件语句的方式。这个解决方案是仪式吗？
在示例中 - 我使用了从 100 到 105 的预期总和 - 以显示输出中的最佳选择。查看 Player-1 从可用池中选择 5 [7,6,5,4,3,2,1]
编辑这不是问题的解决方案。这种方法在 {pool:[1-5], Total:12} 的情况下失败了。该函数说，玩家 2 总是赢，但玩家 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!