近日領到了老師的期末作業 其中有這道 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 }View Code
好了，到此本題結束，代碼有點難看，不過湊合能用，希望能幫到以后的學弟學妹吧，：）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117908.html
標籤：其他
上一篇：FPGA