保证硬币行中获胜(或平局)的算法问题

Question

在一行n枚硬币(>=0，n=偶数(中，每个玩家(阿米尔和塔玛(必须从该行的一个边缘中挑选一枚硬币。金额最大的玩家获胜。需要保证阿米尔至少打成平局。阿米尔先走。我的算法是让阿米尔拿走最大的硬币，除非紧接着的硬币保证了损失(即，如果阿米尔拿走了所有可能剩下的最高硬币，他仍然会损失(。你认为这是对的吗？如果是这样的话，如果你看一下我的代码(Java(，我将不胜感激——获得Amir/Tamar的随机胜利。

//This method takes the largest of the two coins providing the coin adjacent to the larger coin leaves a chance of winning assuming
//worse case scenario - all highest (remaining numbers) are picked by - Tamar.
public static void win(int[] arr){
int beginning = 0, end=arr.length-1, sumAmir = 0, sumTamar = 0;
int[] arrClone = arr.clone();
java.util.Arrays.sort (arrClone, beginning, end+1);
while (beginning<end){
if ((arr[end]>=arr[beginning] && !loses(arr,arrClone, end-1,sumAmir,sumTamar,beginning,end))
|| (arr[end]<arr[beginning] && loses(arr, arrClone,beginning+1,sumAmir,sumTamar,beginning,end))) {
System.out.println ("Amir took " + arr[end]);
sumAmir+=arr[end];
end--;
}
else{
System.out.println ("Amir took "+ arr[beginning]);
sumAmir+=arr[beginning];
beginning++;
}
if (arr[beginning]> arr[end]){
System.out.println ("Tamar took " + arr[beginning]) ;
sumTamar+=arr[beginning];
beginning++;
}
else{
System.out.println ("Tamar took " + arr[end]) ;
sumTamar+=arr[end];
end--;
}
}
System.out.println ("Amir total " + sumAmir + "nTamar total " + sumTamar);
}
private static boolean loses(int[] arr,int[] arrClone, int place, int sumAmir, int sumTamar, int beginning, int end) {
int currPlace =arr[place];
if (end - beginning == 1) {
return false;
}
if (place == beginning + 1) {
sumAmir += arr[beginning];
beginning += 2;
} else {
sumAmir += arr[end];
end -= 2;
}
//Sums lowest & highest halves of (sorted) array. (excluding checked duo)
int lowestValsSum = 0;
int k=0;
int highestValsSum = 0;
for (int i = beginning; i < (beginning+end)/2 + 1; i++) {
k++;
lowestValsSum+=arrClone[i];
highestValsSum+=arrClone[end-k];
}
return sumAmir + highestValsSum < sumTamar + currPlace + lowestValsSum;
}

TX-

Answer 1

您可以尝试为您的游戏实现最小最大算法，以确保玩家的最佳游戏(获胜或平局(。