游戲策略(完整版)
【正文】 rom the text file for each board determines, whether the first player has a winning strategy, writes the results to the text file . InputThe first line of the input file consists of three integers c, z and n, 1 = c, z, n = 1000, equal to the lengths of stripes, adequately: red, green and blue ones. Numbers in the line are separated by single spaces. The second line of the file consists of one number m, 1 = m = 1000, which is equal to the number of different boards to consider. Lines from the 3rd to the (m+2)th consists of one number p, 1 = p 1000. Number in the (i+2)th line is the length of the ith board. OutputThe output file should contain m lines. Only one number should be written in the ith line of the file: 1 if the first player has a winning strategy on the ith board 2 otherwise. ExampleFor the input file : 1 5 13 1 5 6the correct result is the output file 11 2異或乘 l 問題引入l 在一個 n*n的方格陣中，每個格子里放一枚硬幣。122241724~35的 SG值為： 473l 這個問題看似已經(jīng)解決，但我們可以進(jìn)行優(yōu)化。SG(1)=0，所以SG(3)=3l SG(4)可分解為 {SG(2),保齡球問題l 在一行中有 n個木瓶，你和你的朋友輪流用保齡球去打這些木瓶，由于你們都是高手，每一次都可以準(zhǔn)確的擊倒一個或相鄰的兩個木瓶，誰擊倒最后一個剩余的木瓶誰將獲得勝利。⊕ ⊕ak’ak證明：請回憶 SG函數(shù)的性質(zhì)：如果當(dāng)前某圖的狀態(tài)值 0，那么游戲者可以通過一步走棋把 圖的當(dāng)前狀態(tài)值 任意的減小。⊕兩個游戲者輪流行動。那么 游戲者無論如何移動，下一個點的 SG值都不等于 0。l 這樣定義有什么好處呢？我們把一個 圖的當(dāng)前狀態(tài)值 定義為游戲者處在的這個點的 SG值。誰無法走了誰就輸。因此情況 2我們可以把這堆石子取完或者取得只剩下 1，使得只剩下奇數(shù)堆數(shù)目為 1的石子留給對方，由 1)，必勝。3. Pi已標(biāo)記的石子堆， D0[i]和 ’部分 NIM方法取子必勝，由于 R1R2R3l 若初始局面為勝局面， P1’’和 P n分解成為兩部分 P1然后符合定理一的結(jié)果，記 S=P1’’XORSP1，令 P1’=P1XORPi’0。2. 若 S=0，即 P1 如果一個局面先手必勝，就稱之為 N局面，反之稱之為 P局面。m堆為奇數(shù)時，先手必勝。l 若只有一堆石子，先收走必勝l 若有 m堆石子，每堆只有一顆石子， l 因此，對于某一個局面，若為非 0局面，它的任務(wù)就是要尋找某一種取法，使得局面變?yōu)?0局面。若 S=0則為 P局面，否則為 N局面。S’， PiPi’，則 PiXOR可知 P1P2……P3若 S=0則為 P局面，否則為 N局面?！痩 若對 P1’部分取子，則按 NIM方法走步，若對R1R2R3’(K+1)即可。112…找出一個二進(jìn)制第 W位為 而且未標(biāo)記的石子堆 Pi，將 Pi標(biāo)記，并把它的第 W位由 1改為 0reNim問題l 取石子問題有 N堆石子，每次從某一堆里選出若干石子去掉（但不能不去石子），兩人輪流取石，誰不能繼續(xù)取誰就贏了。因此不可能給對手留下情況 2l 圖游戲模型 forg(x)1 這些數(shù)必然都出現(xiàn)在 x的后繼節(jié)點的 SG值中，而游戲者可以走到這些點中的任意一個。l 如果當(dāng)前點 SG≠0，先手可以走到一個 SG=0的點，這樣后手面對一個必敗狀態(tài)，所以先手必勝。a2,ak⊕⊕a2Game的走法行動，使得 a1’0。l 剩余兩個時，可以取到 0或 1，其中 SG(0)=0， SG(1)=1，所以 SG(2)=2l 剩余三個時，我們可以把局面變成 1或 2或兩堆均為 1。優(yōu)化l 對于每一個 N值，我們?yōu)榱饲蟪鏊?SG值 ,3612~23的 SG值為： 414222118l 判斷某一種狀態(tài)是先手必勝還是后手必勝。x?(y?z)=(x?y)?zy,兩個人輪流操作，不能操作者輸。每次可以選一個格子，把這個格子及其右下方的所有格子全部拿走。l 否則如果 A是一個先手必勝狀態(tài)，那么必然可以通過拿掉某個格子變成先手必敗狀態(tài)。gameTheirthegreen,areThebelongtoa set of successors,fromweretheinonly,nonemptymakewestart fieldturnsthisopponent).offinishedtimeQ.theforatwinsthatiswinsmatterl readsofforthel Inputl Inb,thenumberb3000.descriptionsdescriptionsofforintegersthegreen)field.a+b)Theythearegreenthanallgratertext
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1