今天封寝室了,无聊看了看电视剧,正好看了天才基本法,看到了如图所示的问题
这个问题可以抽象成 有n个石子,每次可以拿1-3个,问先手是否可以必胜
解题思路
当n=1,2,3 时先手必胜 ,n=4 时 先手必败。
那么 ,n=5,6,7 先手还是必胜。
进而我们可以得到一个递推式 , f[i] 表示剩余i颗石子时,先手是否必胜
f[1]=f[2]=f[3]=1
f[i]=(!f[i−1]) | (!f[i−2]) | (!f[i−3])
其实就是当时 n%4==0,先手必败,否者先手必胜,因为可以拿1−3颗,那么我必然能够走到先手必败态,显然电视剧是在欺负人啊!
还好,看了后续,主角没那么傻,反而拓展到n个物品,每次可以拿1−m个物品的情况,
那么 n%(m+1)==0时 ,先手必败,否则先手必胜。