java 中的两个角落投币游戏

Question

2角硬币游戏收到一个数组。游戏的目标是积累最多的点数（数组中元素的值）。你只能从数组的两个角取点。

游戏有2个条件：

1) 第一个玩家 (amir) 永远不会输（他会赢或以平局结束）并且他不一定会选择最大的优势。

2) 第二位玩家 (Tamara) 将始终在最高角得分。

我的输出：

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

问题：

-amir 将 select 16 所以 tamara 必须 select 23 所以在下一回合他将 select 30（因为 tamara 总是 select 最大的角）。

-amir 在最后一回合将 select 13 而不是 14，因为他已经赢了所以他不关心 point/coin 值。

amir选择13而不是14的原因： 1. 因为塔玛拉总是 select 最大的 "end" 2. 因为他不会输掉这场比赛（65 对 59）所以他会选择 13 而不是 14 这是策略 - 只是不输（可以完成平局或赢得比赛）他可以计划他的所有举动，因为他可以从乞讨中看到阵列并且他不想用更少的动作输掉这场比赛

-amir 从第一回合就知道下一步是什么，因为他在这场比赛中不会输（他可以作为赢家结束比赛，或者以与 tamara 相同的分数结束比赛）

-Amir可以提前计算出游戏的完整走法树以及Tamar如何应对每一步，然后他将如何应对每一步。这种解决方案的问题可能是一棵巨大的树（Amir 和 Tamara 可以玩的不同游戏的数量是 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);
}

编辑：（Akshay Batra 的回答）

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]);
    }

Answer 1

此代码适用于您的输入，尝试使用不同的输入，看看它是否会中断，如果是，请优化您的解决方案

从调用方方法调用这种方式int[] a = pickByAmir(array1, 0, 0, 0, array1.length-1);

a[0] 将得到 amir 的总数，a[1] 将得到 tamara 的

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;
    }
    return a;
}
int[] pickByTamara(int[] coins, int start, int end){
    return coins[start] > coins[end] ? coins : swapArray(coins, start, end);
}

int[] swapArray(int[] coins, int start, int end) {
    int temp = coins[start];
    coins[start] = coins[end];
    coins[end] = temp;
    return coins;
}

祝你好运

java 中的两个角落投币游戏

Two corners coin game in java

java

backtracking

recursive-backtracking