카드 게임 알고리즘

Question

플레이어가 카드 목록에서 가장 왼쪽 또는 가장 오른쪽 카드를 선택할 수있는 2 명의 플레이어 간 C 언어로 카드 게임을 개발해야합니다. 예 : 목록이 [2, 14,12,6,20,10] 플레이어는 2 또는 10을 선택할 수 있습니다. 마지막으로 점수가 높은 플레이어 (플레이어가 선택한 카드의 합)가 게임에서 승리합니다. 플레이어의 선택을 최적화하는 방법이 있습니까? 예를 들어, 위의 경우 10을 선택하면 다른 플레이어가 20을 선택할 기회가 주어집니다. (재귀 함수로 들리 겠지만 ...)

Answer 1

최적의 게임을하면 주어진 점수로 점수가 부여됩니다. 입력을 L로 나열하고 길이가 l 인 i 번째 요소부터 시작하여리스트의 일부에 대해 첫 번째 및 두 번째 플레이어 점수로 F(i,l) 및 S(i,l)을 정의합니다. 목록의 (일부) 길이가 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). 

구현은 F 및 S 두 n^2 배열을 작성하여 수행됩니다. 결과는 F(1, length(L))입니다.

Answer 2

나는 최대화에 관해 모른다. 첫 번째 플레이어의 경우 간단한 알고리즘이 있습니다.

먼저 빨간색과 검정색으로 카드를 표시하면 (가장자리에있는 카드가 빨간색과 검은 색으로 번갈아 표시됩니다) 다른 색상. 블랙 카드와 레드 카드를 (별도로) 합친 다음 원하는 색상을 선택하십시오. 블랙 카드의 합이 더 높다고 가정하면 (예를 들어) 블랙 카드를 계속 선택하면 상대방은 레드 카드를 선택해야합니다. 그러면 승리 할 것입니다!

Answer 3

우리는이 과정을 우리의 프로그래밍 과정 중 하나에서했고, 이것이 내가 생각해 냈던 해결책이다 (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]; 
} 

Answer 4

@asaelr 대답은 간단하고 이해하기 쉽습니다.이 문제는 정말 좋은 속임수입니다. 그러나이 솔루션은 첫 번째 플레이어가 패배하지 않도록하고, 상대보다 많은 포인트를 얻지 못하도록 할 수 있습니다. 최적의 솔루션을 얻으려면 DP를 사용해야합니다. 예 : {3, 2, 2, 3, 1, 2}, 우리가 이길 수있는 트릭을 사용하여 2, DP를 사용하여 3 점을 획득 할 수 있습니다. 자세한 설명은 여기에서 찾을 수 있습니다. 정말 좋은 기사. http://articles.leetcode.com/coins-in-line/