Игра с двумя углами получает массив. Цель игры - набрать как можно больше очков (значений элементов в массиве). Вы можете брать очки только из 2 углов массива.
Есть 2 условия для игры:
1) Первый игрок (амир) никогда не проиграет (он выиграет или финиширует с ничьей), и он не обязательно выберет наибольшее преимущество.
2) Второй игрок (Тамара) всегда будет брать очки в верхнем углу.
Мой вывод:
amir took 16
tamara took 23
amira took 30
tamara took 15
amir took 19
tamara took 21
amir took 14
tamara took 13
Final Score:
amir total 79
tamara total 72
Ожидаемый результат:
Amir took 16
Tamara took 23
Amir took 30
Tamara took 15
Amir took 19
Tamara took 21
Amir took 13
Tamara took 14
Final Score:
Amir total 78
Tamara total 73
Проблема:
-амир выберет 16, поэтому Тамара должна выбрать 23, поэтому в следующем ходу он выберет 30 (потому что Тамара всегда будет выбирать самый большой угол).
-амир в последнем ходу выберет 13, а не 14, потому что он уже выиграл, поэтому его не волнует ценность очка / монеты.
Причины, по которым амир выбирает 13, а не 14:
1. потому что тамара всегда выберет самый большой «конец» 2. потому что он не проигрывает эту игру (65 против 59), поэтому он выберет 13, а не 14, это стратегия - просто не проиграть (можно закончить ничьей или выиграть игру ) он может планировать все свои ходы, потому что он может видеть массив с самого начала и хочет не терять эту игру с меньшим ходом
-амир с первого хода знает, что будет следующим ходом, потому что он не может проиграть в этой игре (он может закончить игру победителем или финишировать с тем же счетом тамары)
-Амир может заранее рассчитать полное дерево ходов игры и то, как Тамар может реагировать на каждый ход, а затем, как он будет реагировать на каждый ход. Проблемой такого решения может быть огромное дерево (количество различных игр, в которые Амир и Тамара могут играть, составляет 2 ^ K - а если K больше, то для мощного компьютера потребуется триллионы лет).
Поэтому в этой игре требуется эффективное решение, подобное этому. и требует, чтобы Амир выполнил несколько действий для разработки стратегии для себя
Массив:
int[] array1 = {16,23,30,14,13,21,19,15};
TEST.coingame(array1);
System.out.println();
Мой код:
public static void coingame(int[] arr)
{
int n = arr.length;
int i = 0, j = n-1,p1=0,p2=0,totalP2=0,totalP1=0;
while(j > i){
if(arr[j]+arr[j-1]>arr[i]+arr[i+1]){
p1 = arr[j];--j;
if(arr[j]>arr[i]){
p2=arr[j];--j;
}else{
p2=arr[i];++i;
}
}else{
p1 = arr[i];++i;
if(arr[j]>arr[i]){
p2=arr[j];--j;
}else{
p2=arr[i];++i;
}
}
System.out.println ("amir took "+p1);totalP1+=p1;
System.out.println ("tamara took "+p2);totalP2+=p2;
}
System.out.println ("Final Score:");
System.out.println ("amir total "+totalP1);
System.out.println ("tamara total "+totalP2);
}
Редактировать: (ответ Акшая Батры)
public static int[] pickByAmir(int[] coins, int amirTook, int tamaraTook, int start, int end) {
if(start>end) {
int[] res = new int[2];
res[0] = amirTook;
res[1] = tamaraTook;
return res;
}
int[] a = new int[2];
a[0] = amirTook;
a[1] = tamaraTook;
if(coins.length==0)
return a;
amirTook = coins[start];
coins = pickByTamara(coins, ++start , end);
tamaraTook = coins[start];
a = pickByAmir(coins, amirTook+a[0], tamaraTook+a[1], ++start, end);
int[] b = new int[2];
b[0] = amirTook;
b[1] = tamaraTook;
if(a[0]<a[1]){
amirTook = coins[end];
coins = pickByTamara(coins, start, --end);
b = pickByAmir(coins, amirTook+b[0], tamaraTook+b[1], ++start, end);
if(a[0]<b[0])
return b;
}
System.out.println ("Amir took "+amirTook);
System.out.println ("Tamara took "+tamaraTook);
return a;
}
public static int[] pickByTamara(int[] coins, int start, int end){
return coins[start] > coins[end] ? coins : swapArray(coins, start, end);
}
public static int[] swapArray(int[] coins, int start, int end) {
int temp = coins[start];
coins[start] = coins[end];
coins[end] = temp;
return coins;
}
public static void coingame(int[] arr) {
int[] a = pickByAmir(arr, 0, 0, 0, arr.length-1);
System.out.println ("Final Score: ");
System.out.println ("Amir total: "+a[0]);
System.out.println ("Tamara total: "+a[1]);
}