微信云網(wǎng)站用什么做,視覺網(wǎng)絡網(wǎng)站,免費開源小程序商城源碼,網(wǎng)站開發(fā)文本參考nim游戲 尼姆博弈 是一個兩人博弈。兩名玩家輪流從若干堆物品中拿取一定數(shù)量的物品#xff0c;每次操作需#xff1a; 選擇某一堆。從該堆中至少拿 1 個#xff0c;至多拿完全部物品#xff08;不能不拿#xff09;。 游戲可以設置“拿到最后一個物品獲勝”或“拿到…參考nim游戲尼姆博弈 是一個兩人博弈。兩名玩家輪流從若干堆物品中拿取一定數(shù)量的物品每次操作需選擇某一堆。從該堆中至少拿 1 個至多拿完全部物品不能不拿。游戲可以設置“拿到最后一個物品獲勝”或“拿到最后一個物品失敗”。視頻規(guī)則 中游戲的等價關系不變量是nim 和是否為 0詳細解釋。定義 1nim 和所有堆的異或和定義為nim 和。例子對狀態(tài)(3, 5, 7)nim 和計算為nim(3,5,7) 3 ⊕ 5 ⊕ 7 1注可用瀏覽器的 JS 計算。約定 1狀態(tài)分類為了簡化證明將硬幣狀態(tài)分成 5 類P、Q、R 明顯可判定平衡態(tài) S 與非平衡態(tài) F 是主要討論對象。5 類狀態(tài)的“標準型”指該類形式最簡單的狀態(tài)。狀態(tài)類定義標準型平衡態(tài) Snim 和為 0且不是 P、Q、Rk?(x,x), x1k?(1,2x,2x1)x⊕x01⊕2x⊕(2x1)0非平衡態(tài) Fnim 和不為 0且不是 P、Q、R(1,2)奇堆純 1 態(tài) P僅有奇數(shù)堆 1(1)偶堆純 1 態(tài) Q僅有偶數(shù)堆 1(1,1)僅 1 堆態(tài) R僅有一堆數(shù)量 1(2)約定 2必勝態(tài)與必敗態(tài)P1P、Q、R 的結果顯然無需討論。P2必勝態(tài)若參與者 A 構造狀態(tài) U 后存在必勝走法則 U 為 A 的必勝態(tài)。P3必敗態(tài)若參與者 A 構造狀態(tài) U 后無必勝走法則 U 為 A 的必敗態(tài)。P4狀態(tài) K? (x,x) | x1 是平衡態(tài)也是必勝態(tài)作為 S 類標準型。P5參與者 A 為平衡態(tài)構造者。P6最高位、s 位等均指二進制位。P7狀態(tài) (s) 表示只有一個 s 個硬幣堆其他堆為 0。狀態(tài) (s,t) 表示只有兩堆分別有 s 和 t 個硬幣其他堆為 0。P8并堆狀態(tài)間的一種運算用 ⊕ 表示nim((s) ⊕ (t)) s ⊕ t。結論平衡態(tài) ⊕ 平衡態(tài) 平衡態(tài)非平衡態(tài) ⊕ 平衡態(tài) 非平衡態(tài)定理 1平衡態(tài)是必勝態(tài)非平衡態(tài)是必敗態(tài)不論規(guī)則是“拿到最后一個贏”還是“拿到最后一個輸”都成立。記住拿成平衡態(tài)者獲勝。T1K? 是平衡態(tài)K? (0,0,…,x,x)因為 nim(K?) x ⊕ x 0所以 K? 是平衡態(tài)。T2K? 是必勝態(tài)下一步 B 拿后的狀態(tài)為 (m,X)分類討論m規(guī)則A 拿法結果0拿最后一個贏A 把 X 堆全拿走A 贏0拿最后一個輸A 把 X 堆剩 1 個A 贏1拿最后一個贏A 把 X 堆剩 1 個A 贏1拿最后一個輸A 把 X 堆全拿走A 贏1拿最后一個贏A 把 X 堆剩 m 個回到 P2 步驟1拿最后一個輸A 把 X 堆剩 m 個回到 P2 步驟因硬幣數(shù)嚴格遞減總會結束于上表綠色情況。T3平衡態(tài)的下一個狀態(tài)一定不平衡設平衡態(tài) nim 和為 0從第 j 堆拿后剩 m 個t ⊕x j x_jxj? m, t0則下一狀態(tài) nim 和 t 0不平衡。T4不平衡態(tài)的下一狀態(tài)可平衡也可不平衡設不平衡態(tài) t0其最高位為 s存在某堆 x_j 的第 s 位為 1則可以通過調整 x_j 堆的數(shù)量拿成平衡A 拿剩 t ⊕x j x_jxj?個使 nim 和變 0拿成不平衡A 拿走該堆小于 s 位的部分使 nim 和 s 位保持不平衡T5存在拿法使構造 S 的 A 最終獲勝必勝表規(guī)則必勝態(tài)必敗態(tài)拿最后一個贏K?, S, QP, F, R拿最后一個輸K?, S, PQ, F, RA 可通過拿到 K?、P 或 Q 獲勝B 最終走向必敗態(tài) F1 或 F2。T6只要 A 盡可能保持平衡B 必經(jīng) F1 或 F2F1 (1,1,…,1,m), m1, nim0F2 (0,0,…,x,m), x,m1, nim0, x≠m硬幣有限最終狀態(tài)必終結于 K? 或 F2。推論 1K?、K? 是必勝態(tài)平衡態(tài)的并堆也是必勝態(tài)因異或運算難口算推論可快速判定大多數(shù)狀態(tài)是否必勝。平衡態(tài)構造技巧口訣從x j x_jxj?堆拿剩x j x_jxj?⊕ t 個直到 P、Q、R 狀態(tài)其中 t 為 nim 和x j x_jxj?為與 t 最高位相同的堆。技巧總結技巧說明技巧1K? (x,x)技巧2K? (1,2x,2x1)技巧3奇數(shù)個奇堆不平衡只看個位技巧4從x j x_jxj?堆拿剩x j x_jxj?⊕ t 個直到 P,Q,R 狀態(tài)需要大量異或計算技巧5平衡狀態(tài)下隨便只拿一個技巧6并堆定理技巧7a 是最大堆將 a 堆剩下 b^c技巧8(a^b^c).toString(2).toString(2)可以通過如下腳本確定如何拿硬幣/** * 狀態(tài)s下,如何拿硬幣 * param s {Array[number]} - 輸入的數(shù)字數(shù)組 * return {[number,number,number]} - 返回一個包含三個數(shù)字的數(shù)組 * 狀態(tài)s的nim和 * xj堆的數(shù)量 * xj堆剩下的數(shù)量 */functionnim(s){//計算狀態(tài)s的nim和constts.reduce((acc,cur)acc^cur,0);letxjMath.max(...s);//必敗態(tài),就從最大堆拿一個if(t0){return[t,xj,xj-1];}//找出xj堆for(letitofs){if((it(t.toString(2).length-1))11){xjit;break;}}//xj堆剩下的數(shù)量return[t,xj,xj^t];}/** * 狀態(tài)s的下一個最佳狀態(tài) * param s {Array[number]} 當前狀態(tài) * return {Array[number]} 下一狀態(tài) */functionm(s){sArray.isArray(s)?s:[...arguments];const[t,xj,nextXj]nim(s);letflag0;letnextSs.map((it){if(flag0itxj){flag1;returnnextXj;}else{returnit;}});if(t0){thrownewError(可能會輸:nextS.toString());}returnnextS;}m(3,5,7)