如何设计金盒游戏的策略和算法
如何设计金盒游戏的策略和算法
提问于 2014-03-22 14:16:59
金箱问题(方法) 每一个金箱都有不同数量的金币。 玩家玩一个游戏，动机是收集最大数量的金币。每个玩家可以看到每个盒子里有多少个硬币，但只能从两端得到一个盒子，在他的回合中。设计一种让Player1获胜的策略(假设双方都玩得很聪明)
这个问题是在亚马逊的一次采访中问到的。我试过这种方法：
#include<stdio.h>
int max(int a, int b) {
return a>b?a:b;
}
int maxCoins(int arr[], int i, int j, int turn) {
if(i==j) {
if(turn == 1) return arr[i];
else return 0;
}
if(turn) {
return max(arr[i] + maxCoins(arr,i+1,j,0),arr[j] + maxCoins(arr,i,j-1,0));
} else {
if(arr[i]>arr[j])
return maxCoins(arr,i+1,j,1);
else
return maxCoins(arr,i,j-1,1);
}
}
int main() {
int arr[10] = {6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
printf("%d\n",maxCoins(arr,0,9,1));
}但我认为这是不对的，因为player2也玩得很聪明。我遗漏了什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-03-22 14:25:20
我找到解决办法了，就差一点了。以下是我错过的：
“对手打算选择给使用者留下最小价值的硬币。”
以下是更新的解决方案：
#include<stdio.h>
int max(int a, int b) {
return a>b?a:b;
}
int min(int a, int b) {
return a<b?a:b;
}
int maxCoins(int arr[], int i, int j, int turn) {
int a,b;
if(i==j) {
if(turn == 1) return arr[i];
else return 0;
}
if(turn) {
a = arr[i] +maxCoins(arr,i+1,j,0);
b = arr[j] + maxCoins(arr,i,j-1,0);
return max(a,b);
} else {
return min(maxCoins(arr,i+1,j,1), maxCoins(arr,i,j-1,1));
}
}
int main() {
int arr[4] = {8, 15, 3, 7 };//{6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
printf("%d\n",maxCoins(arr,0,3,1));
} 此链接讨论策略：http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22578722
复制相关文章
相似问题
腾讯云开发者
