Игра 100 - CanIWin()
Проблема:
- Два игрока выбирают номера из общего пула номеров, чтобы получить общую сумму.
- Игрок, который достигает / пересекает целевое значение, выигрывает.
- Задача состоит в том, чтобы выяснить, может ли игрок-1 применить стратегию победы - для заданной суммы и пула чисел.
Мой подход:
Предполагая, что оба игрока выбирают оптимальное число из доступного пула. Под оптимальным я имею в виду -
Убедитесь, что наибольшее число, доступное в пуле>= оставшееся значение. [yes]=> вернуть наибольшее доступное значение.
Если выигрыш невозможен, выберите максимально возможное число (
RequiredToWin - HighestNumberInThePool) в пуле, который НЕ гарантирует победу в следующем ходу.
Я просто придумал решение "а" и написал код. Я пытаюсь проанализировать, если это обряд? оптимальный, с точки зрения времени, пространства. Также пытаюсь понять, как я могу улучшить свои соглашения по кодированию - глобальные переменные и то, как я использую условные операторы. Это решение обряд?
В примере - я использовал ожидаемую сумму от 100 до 105 - чтобы показать оптимальный выбор в выводе. Смотрите Player-1 выбирает 5 из доступного пула [7,6,5,4,3,2,1]
Редактировать Это не решение проблемы. Этот подход не подходит для случая {пул:[1-5], всего: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!
1 ответ
Если числа являются положительными целыми числами и могут быть использованы повторно (и находятся в последовательном диапазоне от 1 до N), то ваша основная идея по существу верна, если выбрать наибольшее возможное число, которое не гарантирует победу противника на втором и последнем ходу, то получится сумма равна N+1. Тогда независимо от того, что делает противник, вы можете выиграть. Таким образом, если общая целевая сумма M делится на N+1, то игрок два может выиграть, оставляя сумму всегда делимой на N+1, в противном случае игрок 1 может выиграть, сначала сделав сумму, делимую на N+1, и украдя игрока 2. стратегия. Если числа не являются последовательными и / или не могут быть повторно использованы, то проблема кажется намного сложнее.