《数据结构与算法分析:C语言描述》复习——第十章“算法设计技巧”——拿石头游戏

2014.07.08 00:08

简介:

  本章里没有讲到这个内容,是我在看书的时候回忆起了自己被问过的一道面试题。当时觉得特别难,现在回想起来才知道是自己无知。

  如果有50颗石子,两人轮流拿。每次可以从其中拿走1,2,4或者8颗。谁拿走了最后一颗,谁就输了(输或者赢根本无所谓)。

  请问,先手或者后手有什么必胜策略吗?

描述:

  如果你是参加过ACM训练的人,肯定觉得小儿科,于是你可以不用看了。

  但对于我这样的外行,在听到这道题目的时候,脑子里一片混乱,甚至打算在草稿纸上硬推出一个结果。

  作为一个软件工程师,如果你在面试的时候以求出正确答案为傲,那么你就错了。因为人家期望的是你要么用理论解释答案,要么用代码解决问题。

  至于具体答案是几?Don’t care。

  

  巴什博弈几乎是博弈问题里最简单的一种了:给定n颗石头,俩人轮流拿走石头,如果每次拿走1~m颗石头的话,谁必胜或者必败呢?

  这些问题有共同点,有不同点。而当你遇到陌生问题的时候,要做的肯定不是用无数脑细胞和人肉计算来得到一个答案,而是用你已有的理论和工具来分析问题。

  我们学过些什么呢?博弈论我肯定不懂了,我就懂一点动态规划的基本知识。

  于是有了下面几条思路:

    1. 不论是{1,2,4,8}还是1~m,我至少有选择的余地。我可以决定下一步怎么走。

    2. 我为什么会输?因为我不论选择哪一步,都是输。我为自己的利益着想,自然是不得已才会输。

    3. 我为什么会赢?因为我至少能找到一步,让我赢。我为自己的利益着想,能赢我一定会赢。

    4. 那么n=50的时候,我到底能不能赢?

  于是动态规划就来了,dp[n]表示n个石头的情况下的游戏结果。

  dp[n]和谁有关?必然是dp[n-1]、dp[n-2]、dp[n-4]、dp[n-8],因为可选的操作只有{1,2,4,8}。

  我们用-1表示对手赢,+1表示我赢,0表示未知(也就是公平竞争,没有人必胜或者必败)。

  如果dp[n-1]、dp[n-2]、dp[n-4]、dp[n-8]全都是+1,表示前一步都是我赢。那么不论我拿走几颗石头到达n,我都是输。(我不想输,所以我是迫不得已的)

  如果dp[n-1]、dp[n-2]、dp[n-4]、dp[n-8]至少有一个是-1,表示前一步有可能是对手赢。那么我会选择对手赢的那条路,因为那样我能赢。(只要能赢,我就会赢)

  而对于结果为0的情况,不作讨论。

  这种由“与”和“或”构成的递推关系式,就是动态规划的关键了。

  尽管这种动态规划的思路写成代码后效率并不高,但思想却很重要。后来我查阅了资料才发现这种动态规划的思想就是“博弈树”。

  

  此外,这个问题虽然是我临时想起来的,但作为一种博弈问题,自然也会和本章的Min-Max策略发生关联。接下来的一篇博文会进行介绍。

  下面的代码给出了这种拿石头问题的程序解法,与其在草稿纸上硬算,不如把代码写给面试官看。既然是码农,自然应该用代码说话了。

实现:

 1 // This is said to be an interview question about game.
 2 // This solution is by dynamic programming.
 3 // Description:
 4 //    If there‘re 50 stones at the beginning, you and your component take turns to take away 1, 2, 4 or 8 stones.
 5 //    Whoever takes away the last stone loses the game.
 6 //    Does this game has a winning strategy for any side?
 7 #include <algorithm>
 8 #include <iostream>
 9 #include <vector>
10 using namespace std;
11 
12 void game(const int n, const vector<int> &move, vector<int> &dp)
13 {
14     int i;
15     // dp[i] means the game result when the total number of stones is i.
16     // 1 for offensive win, -1 for defensive win, 0 for uncertain(fair play).
17     dp.resize(n + 1, 0);
18     
19     int n_move = (int)move.size();
20     int n_win;
21     dp[move[0]] = -1;
22     
23     int j;
24     for (i = move[0] + 1; i <= n; ++i) {
25         n_win = 0;
26         for (j = 0; j < n_move; ++j) {
27             if (i - move[j] <= 0) {
28                 ++n_win;
29                 continue;
30             }
31             if (dp[i - move[j]] == -1) {
32                 // one of the parent node in the game tree is lose, 
33                 // then you win.
34                 dp[i] = 1;
35                 break;
36             } else if (dp[i - move[j]] == 1) {
37                 ++n_win;
38             }
39         }
40         if (j == n_move && n_win == n_move) {
41             // all parent nodes in the game tree are wins, then you lose
42             dp[i] = -1;
43         }
44     }
45 }
46 
47 int main()
48 {
49     vector<int> dp;
50     vector<int> move;
51     int n;
52     int i;
53     int tmp;
54     
55     while (cin >> n && n > 0) {
56         while (cin >> tmp && tmp > 0) {
57             move.push_back(tmp);
58         }
59         game(n, move, dp);
60         sort(move.begin(), move.end());
61         for (i = 1; i <= n; ++i) {
62             cout << i << :;
63             switch(dp[i]) {
64             case -1:
65                 cout << "Defensive win." << endl;
66                 break;
67             case 0:
68                 cout << "Fair play." << endl;
69                 break;
70             case 1:
71                 cout << "Offensive win." << endl;
72                 break;
73             }
74         }
75         
76         dp.clear();
77         move.clear();
78     }
79     
80     return 0;
81 }

 

《数据结构与算法分析:C语言描述》复习——第十章“算法设计技巧”——拿石头游戏,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。