资源预览内容
第1页 / 共33页
第2页 / 共33页
第3页 / 共33页
第4页 / 共33页
第5页 / 共33页
第6页 / 共33页
第7页 / 共33页
第8页 / 共33页
第9页 / 共33页
第10页 / 共33页
亲,该文档总共33页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
,博弈,取石子游戏,巴什博弈,一堆n个石子,两个人轮流取,每次至少取一个,至多取m个,最后取光者胜。,巴什博弈,必胜态 必败态,威佐夫博弈,有两堆石子,两个人轮流取,每次可以从其中一堆或者两堆同时取至少一个石子,最后取光者胜。,威佐夫博弈,奇异局势:,威佐夫博弈,奇异局势: (0,0) (1,2) (3,5) (4,7) (6,10) (8,13) ,威佐夫博弈,奇异局势: (0,0) (1,2) (3,5) (4,7) (6,10) (8,13) ak = floor(k(1+sqrt(5)/2) , bk = ak + k,威佐夫博弈,尼姆博奕,有若干堆石子,两个人轮流取,每次可以从一堆中取至少一个石子,最后取光者胜。,尼姆博奕,SG,mex(minimal excludant)SGi = mexsgj ( i - j ),SG,翻硬币游戏,N个硬币排成一排,有的正面朝上,有的反面朝上。两个人轮流翻硬币,每次翻的最右边一个硬币必须由正面翻到反面。不能翻的人输。,翻硬币游戏,1.一次只能翻一个硬币。,翻硬币游戏,1.一次只能翻一个硬币。 2.一次能翻一个或者两个硬币。,翻硬币游戏,hdu3032 Nim or not Nim? 大意:给定n堆石子,alice和bob轮流操作,每次可以从一堆石子中取出若干个,或者将一堆石子分成两堆非空石子。最后取光者胜。,例题:,对SG打表找规律。 SG: 0 1 2 4 3 5 6 8 7 9 10 12 11猜测SGi = i (i%4 = 1 or I % 4 = 2)SGi = i + 1(i%4 = 3)SGi = i 1 (i%4 = 0),例题:,Hdu2516 取石子游戏 大意:1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜。,例题:,打表找规律。 发现2,3,5,8,13都是必败态。 猜测所有Fib都是必败态。 (然后试了一下,发现猜对了。),例题:,hdu2147 kikis game 大意:在一个n*m的棋盘上,一个硬币位于(1,m),两个人博弈,每次可以向左、向下或者向左下移动一格,无法移动者输。,例题:,打表找规律。,例题:,打表找规律。,例题:,打表找规律。 其实还有更优美的做法。,例题:,hdu1847 Good Luck in CET-4 Everybody! 大意:一堆N个石子,两个人博弈,每次可以取2的幂次个数的石子,最后取光者胜。,例题:,打表找规律。,例题:,Anti-Nim,有若干堆石子,两个人轮流取,每次可以从一堆中取至少一个石子,最后取光者负。,Anti-Nim,必胜态: 1.每堆石子都只剩1个,且SG=0 2.至少一堆石子1个,且SG0,Anti-Nim,没啦,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号