zerone 01串博弈问题

近日领到了老师的期末作业 其中有这道 01 串博弈问题：

刚开始读题我也是云里雾里 但是精读数遍 “细品” 之后，我发现这是一个 “动态规划” 问题。好嘞，硬着头皮上吧。

      分析问题：可知对每个人有两手选择 0 或 1。那么很自然的我们就可以用二叉树来储存每一个选择后的结果。对于本题 ，选择后的结果是还有多少01串未被抹除。所以我再每一个二叉树的节点上再生成一维向量组来保存我们还有那些串未被抹除。这样经过一系列暴力的循环运算后我们将得到一个储存着我们的结果的二叉树。之后的问题是：如何得到必胜方。这一点困扰了我不少时间。不过只要你逻辑清晰还是很容易可以知道：对于每一个节点来说，下一手的选择是对当前的博弈者最有利的选择。比如对亚当来说，选择0，必输，选择1，有可能会嬴，那么亚当绝对会选择1。理清了这个逻辑，加上之前我们已经运算出了博弈的所有结果，这样我们便可以从下往上，从子树反推根代表的必胜者。（这部分可能很绕。。。请多思考），这样我们再建立一个二维向量表，并将刚才所有博弈结果中的胜利者信息（第 i 手，是哪个根的子树）输入进去，然后暴力计算反推：）。虽然我们的方法看起来粗糙 、原始、血腥，任何一个算法老鸟看了都不屑一顾，但能抓住老鼠就是好猫啊！

ps：（之前再网上看过某前辈用的栈+类轻松解决问题，我这个自学c++的小白实在学不来。。。）

下面贴上代码：

  1 // 01串.cpp: 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include<iostream>
  6 #include <vector>
  7 #include <math.h>
  8 
  9 using namespace std;
 10 void Findwiner(vector<vector<int>>&n, vector<int>&a);
 11 int Findwiner_i(vector<vector<int>>&n, int i);
 12 int p = 0;//全局变量 01 串的数量
 13 constexpr auto len = 10;//定义01串最大的长度 若31以上要将向量里的 int 换为long int！！！！！！
 14 
 15 int main()
 16 {
 17     cout << "输入串的数目：";
 18     cin >> p;
 19 
 20     char a[len];
 21     vector<int> w(p, 0);
 22     vector<vector<int>>  b(p);
 23     for (int i = 0; i < p; i++)
 24     {
 25         b[i].resize(len);
 26     }
 27     //将向量全部初始化为3，用来区分01串；
 28     for (int i = 0; i < p; i++)
 29     {
 30         for (int j = 0; j < len; j++)
 31         {
 32             b[i][j] = 3;
 33         }
 34 
 35     }
 36     //输入字符串 并将其值添加到向量中去。
 37     cout << "初始化:" << endl;
 38     for (int i = 0; i < p; i++)
 39     {
 40         cout << "输入第" << i + 1 << "串：";
 41         cin >> a;
 42         for (int j = 0; j < len; j++)
 43         {
 44             if (((a[j] - '0') == 0) || ((a[j] - '0') == 1))
 45             {
 46                 b[i][j] = a[j]-'0';
 47             }
 48             else
 49             {
 50                 break;
 51             }
 52            
 53         }
 54 
 55     }
 56     cout << endl;
 57     cout << "输入为："<<endl;
 58     for (int i = 0; i < p; i++)
 59     {
 60         for (int j = 0; j < len; j++)
 61         {
 62             if ((b[i][j] == 0) || (b[i][j] == 1))
 63             {
 64                 cout << b[i][j];
 65             }
 66             else
 67             {
 68                 break;
 69             }
 70         }
 71         cout << endl;
 72     }
 73 
 74     Findwiner(b,w);
 75 
 76     cout << endl;
 77 
 78     for (int i = 0; i < p; i++)
 79     {
 80         cout << w[i] << " ";
 81     }
 82     cout << endl;
 83     cout << "winer:   " << "  start  " << "  end  " << endl;
 84 
 85     cout << endl;
 86     cout << endl;
 87     for (int i = 0; i < p; i++)
 88     {
 89         if (w[i] == 2)
 90         {
 91             if ((i == 0) || (w[i - 1] == 1))
 92             {
 93                 cout << "Eva:      ";
 94             }
 95             if ((i == 0) || (w[i - 1] == 1))
 96             {
 97                 cout << "  " << i+1 << "     ";
 98             }
 99             if (i != p - 1)
100             {
101                 if (w[i + 1] == 1)
102                 {
103                     cout << "  " << i+1 << "  " << endl;
104                 }
105             }
106             else
107             {
108                 cout << "  " << i+1 << "  " << endl;
109             }
110         }
111         if (w[i] == 1)
112         {
113             if ((i == 0) || (w[i - 1] == 2))
114             {
115                 cout << "Adam :    ";
116             }
117             if ((i == 0) || (w[i - 1] == 2))
118             {
119                 cout << "  " << i+1 << "     ";
120             }
121             if (i != p - 1)
122             {
123                 if (w[i + 1] == 2)
124                 {
125                     cout << "  " << i+1 << "  " << endl;
126                 }
127             }
128             else
129             {
130                 cout << "  " << i+1 << "  " << endl;
131             }
132         }
133         
134     }
135 
136     system("pause");
137     return 0;
138 }
139 
140 void Findwiner(vector<vector<int>>&n,vector<int>&a)
141 {
142     int i = 0;
143     
144     for (i=0;i<p;i++)
145     {
146         a[i] = Findwiner_i(n,i+1);
147     }
148     /*a[2] = Findwiner_i(n, 2 + 1);
149     system("pause");*/
150 
151 
152 }
153 
154 int Findwiner_i(vector<vector<int>>&n,int i)
155 {
156     vector<int> temp(i,1);
157     vector<vector<vector<int>>> dpt(len + 1);
158     vector<vector<int>> dp(len + 1);
159     int sign1 = 0, sign2 = 0, sign3 = 0, winer = 0;
160     for (int j = 0; j < len+1; j++)
161     {
162         dpt[j].resize(pow(2, len + 1));
163         dp[j].resize(pow(2, len + 1));
164     }
165     for (int j = 0; j < len+1; j++)
166     {
167         for (int k = 0; k < pow(2, len+1); k++)
168         {
169             dpt[j][k].resize(i);
170         }
171     }
172     for (int j = 0; j < i; j++)
173     {
174         dpt[0][0][j] = temp[j];
175     }
176     //运行动态规划 计算dpt表 将博弈的结果存在里面
177     for (int j = 0; j < len; j++)
178     {
179         for (int k = 0; k < pow(2,j); k++)
180         {
181             for (int l = 0; l < i; l++)
182             {
183                 if (dpt[j][k][l] != 0)
184                 {
185                     if (n[l][j] == 1)
186                     {
187                         dpt[j + 1][(k + 1) * 2 - 2][l] = 0;
188                         dpt[j + 1][(k + 1) * 2 - 1][l] = dpt[j][k][l];
189                     }
190                     if (n[l][j] == 0)
191                     {
192                         dpt[j + 1][(k + 1) * 2 - 2][l] = dpt[j][k][l];
193                         dpt[j + 1][(k + 1) * 2 - 1][l] = 0;
194                     }
195                     if (n[l][j] == 3)
196                     {
197                         dpt[j + 1][(k + 1) * 2 - 2][l] = 0;
198                         dpt[j + 1][(k + 1) * 2 - 1][l] = 0;
199                     }
200                 }
201                 else //dpt[j][k][l]==0;
202                 {
203                     dpt[j + 1][(k + 1) * 2-1][l] = dpt[j][k][l];
204                     dpt[j + 1][(k + 1) * 2 - 2][l] = dpt[j][k][l];
205                 }
206             }
207         }
208     }
209 
210     //===================================================================
211     //输出dpt 调试用
212     /*for (int j = 0; j < len + 1; j++)
213     {
214         for (int k = 0; k < pow(2, j ); k++)
215         {
216             for (int l = 0; l < i; l++)
217             {
218                 cout << dpt[j][k][l];
219             }
220             cout << "           " ;
221         }
222         cout << endl;
223     }*/
224     //===================================================================
225     //计算dp dp表表示在二叉树中胜利者的位置 经两次计算将胜利者的代号放入dp[0][0]中
226     for (int j = 0; j <len; j++)
227     {
228         for (int k = 0; k < pow(2, j); k++)
229         {
230             sign1 = 0;
231             sign2 = 0;
232             sign3 = 0;
233             for (int l = 0; l < i; l++)
234             {
235                 if (dpt[j][k][l] != 0)
236                 {
237                     sign1++;
238                 }
239                 if (dpt[j + 1][(k + 1) * 2 - 2][l] != 0)
240                 {
241                     sign2++;
242                 }
243                 if (dpt[j + 1][(k + 1) * 2 - 1][l] != 0)
244                 {
245                     sign3++;
246                 }
247             }
248             if ((sign1 != 0)&&(sign2==0)&&(sign3==0))
249             {
250                 if (j % 2 == 0)
251                 {
252                     dp[j][k] = 2;
253                 }
254                 if (j % 2 == 1)
255                 {
256                     dp[j][k] = 1;
257                 }
258             }
259         }
260     }
261 
262     //========================================================================
263     //1 :adam        2:eva
264     for (int j = len - 1; j > 0; j--)
265     {
266         for (int k = 0; k < pow(2, j); k++)
267         {
268             sign1 = ceil((double)(k + 1) / 2) - 1;
269             if (sign1 < 0)
270             {
271                 sign1 = 0;
272             }
273             if (dp[j][k] == 1)
274             {
275                 if (dp[j - 1][sign1] == 0)
276                 {
277                     dp[j - 1][sign1] = dp[j][k];
278                 }
279                 if (dp[j - 1][sign1] == 1)
280                 {
281                     dp[j - 1][sign1] = dp[j][k];
282                 }
283                 if (dp[j - 1][sign1] == 2)
284                 {
285                     if (j % 2 == 1)
286                     {
287                         dp[j - 1][sign1] = dp[j][k];
288                     }
289                     if (j % 2 == 0) 
290                     {
291                         dp[j - 1][sign1] = dp[j - 1][sign1];
292                     }
293                     
294                 }
295             }
296 
297             if (dp[j][k] == 2)
298             {
299                 if (dp[j - 1][sign1] == 0)
300                 {
301                     dp[j - 1][sign1] = dp[j][k];
302                 }
303                 if (dp[j - 1][sign1] == 2)
304                 {
305                     dp[j - 1][sign1] = dp[j][k];
306                 }
307                 if (dp[j - 1][sign1] == 1)
308                 {
309                     if (j % 2 == 0)
310                     {
311                         dp[j - 1][sign1] = dp[j][k];
312                     }
313                     if (j % 2 == 1)
314                     {
315                         dp[j - 1][sign1] = dp[j - 1][sign1];
316                     }
317 
318                 }
319             }
320 
321             if (dp[j][k] == 0)
322             {
323                 dp[j - 1][sign1] = dp[j - 1][sign1];
324             }
325         }
326     }
327     //=============================================================
328     //输出dp 调式用
329 /*    cout << endl << "dp:" << endl;
330     for (int j = 0; j < len + 1; j++)
331     {
332         for(int k=0;k<pow(2,j);k++)
333         {
334             cout << dp[j][k] << "  ";
335         }
336         cout << endl;
337     }*/
338     winer = dp[0][0];
339 
340     return winer;
341 }

　　好了，到此本题结束，代码有点难看，不过凑合能用，希望能帮到以后的学弟学妹吧。：）

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄

×

选择打赏方式：

微信 QQ钱包 支付宝

打赏

打赏

打赏

多少都是心意！谢谢大家！！！