4

我被要求在 2 个玩家之间用 c 语言开发一个纸牌游戏，玩家可以从卡片列表中选择最左边或最右边的卡片，例如：如果列表是：[2,14,12,6,20 ,10]玩家可以选择2或10。最终得分较高的玩家（玩家选择的牌的总和）赢得比赛。有没有办法优化玩家的选择，因为知道并不总是最好的选择是最大值（例如：在上述情况下选择 10 会给其他玩家选择 20 的机会）。（听起来是一个递归函数......）

4

4 回答 4

2

我不知道最大化。但是如果（一开始）有偶数张牌，那么第一个玩家有一个简单的算法：

首先，用红色和黑色（交替）标记卡片，这样边缘的卡片就会有不同的颜色。将黑卡和红卡（分别）相加，然后选择您喜欢的颜色。假设（例如）黑牌的总和更高，继续选择黑牌，你的对手将不得不选择红牌 - 你会赢！

于 2013-06-09T20:49:38.523 回答
0

发挥最佳，对于给定的游戏，玩家将获得一些分数。让输入为列表 L 并将和定义F(i,l)为S(i,l)从长度为 l 的第 i 个元素开始的列表部分的第一和第二玩家得分。如果（部分）列表的长度为 1，则该卡将发给第一个玩家。

F(i,1) = L[i]
S(i,1) = 0

如果（部分）列表比第一个玩家想要最大化他选择的卡的总和以及他作为第二个玩家将得到什么列表还剩下什么。

F(i,l) = max( L[i] + S(i+1,l-1), L[i+l-1] + S(i,l-1) )

由于第二个玩家没有选择卡片，他将获得第一个玩家在较短列表中获得的内容。

S(i,l) = F(i+1,l-1) if L[i] + S(i+1,l-1) >= L[i+l-1] + S(i,l-1), or
         F(i,l-1)   if L[i] + S(i+1,l-1) < L[i+l-1] + S(i,l-1).

实现是通过为 和 填充两个数组n^2来完成的。结果是。FSF(1, length(L) )

于 2013-06-09T20:30:52.500 回答
0

我们在我们的一门编程课程中进行了这个练习，这就是我想出的解决方案（在 c++ 中，但它很容易翻译成 c）。它使用 O(n^2) 时间和 O(n) 空间的动态规划。首先它计算每个长度为 1 的子列表的最佳播放分数，然后使用它们计算长度为 2 的列表的分数，依此类推。最后有两个长度为 n-1 的列表，我们选择总分更好的列表。

int f(const vector<int>& numbers) // return 0 if left is optimal pick, 1 if right 
{
    vector<int> s(numbers);

    for(size_t len = 1; len < numbers.size() - 1; ++len)
        for(size_t i = 0; i < numbers.size() - len; ++i)
            s[i] = max(numbers[i] - s[i + 1], numbers[i + len] - s[i]);

    return numbers.front() - s[1] < numbers.back() - s[0];
}
于 2013-06-09T20:56:20.227 回答
-1

@asaelr 的答案简单易懂，这是解决这个问题的一个非常好的技巧。但是，这种方案只能保证第一个玩家不输，不能保证他比对手获得的积分最多。如果我们想得到最优解，我们必须使用 DP。例如：{ 3, 2, 2, 3, 1, 2 }，使用技巧可以赢2，使用DP可以赢3分。可以从这里找到详细的解释。真是不错的文章。 http://articles.leetcode.com/coins-in-line/

于 2017-10-07T22:21:56.907 回答