c - カードゲームのアルゴリズム

Question

プレイヤーがカードのリストから左端または右端のカードを選択できる 2 人のプレイヤー間で C 言語でカード ゲームを開発するように依頼されました。例: リストが [2,14,12,6,20 ,10] プレーヤーは 2 または 10 を選択できます。最終的にスコア (プレーヤーが選択したカードの合計) が高いプレーヤーがゲームに勝ちます。常に最良の選択が最大であるとは限らないことを知っているプレイヤーの選択を最適化する方法はありますか (例: 上記のケースで 10 を選択すると、他のプレイヤーが 20 を選択する機会が与えられます)。（再帰関数のように聞こえます...）

Answer 1

私たちはプログラミング コースの 1 つでこの演習を行いました。これが私が思いついた解決策です (c++ ですが、c に簡単に変換できます)。O(n^2) 時間と O(n) 空間の動的計画法を使用します。最初に、長さ 1 の各サブリストの最適なプレイ スコアを計算し、次にそれらを使用して長さ 2 のリストのスコアを計算します。最後に、長さが n-1 の 2 つのリストがあり、全体的なスコアがより良い方を選択します。

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

Answer 2

特定のゲームで最適にプレイすると、プレーヤーはある程度のスコアを獲得します。入力をリスト L とし、長さ l の i 番目の要素から始まるリストの一部の 1 番目と 2 番目のプレイヤー スコアとしてF(i,l)andを定義します。S(i,l)リスト (の一部) の長さが 1 の場合、そのカードは最初のプレイヤーに渡されます。

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

リスト (の一部) が最初のプレイヤーよりも長い場合は、選択したカードの合計と、2 番目のプレイヤーとしてリストに残っているものを最大化したいと考えています。

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

2 番目のプレーヤーはカードを選択していないため、最初のプレーヤーが短いリストで取得したものを取得します。

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).

実装は、 と の 2 つの配列を満たすことによって行われn^2ます。結果はです。FSF(1, length(L) )