《取石子游戏漫谈》PPT课件

1、取石子游戏”漫谈,初探 描述递归通项 几点思考,初探,典型的博弈问题 “平衡态”是关键,博弈问题的精髓,让对手永远面临,非平衡态,对“取石子”的初步分析,先试探几个小数组,1，2,1，1,0，1,0，1,0，2,0，0,输,2，3,1，3,0，3,2，2,1，2,0，2,0，1,赢,3，4,1，2,3，5,赢,0，2/3/5,1，3/5,2，4,0，1,1，2,输,小结一下,必赢数组比必输数组多 选必输数组为平衡态 显然而重要的结论,平衡态,非平衡态,任意操作,寻找平衡态（必输态,归纳：（n,An,Bn） （1，1，2）； （2，3，5）； （3，4，7）； （4，6，10）；,猜测： An：

2、前n-1组未出现过的最小数 Bn：n+An,寻找平衡态（必输态,正确性,证之,用第二类数学归纳法： n=1时，（1,2）成立 （是平衡态） 假设nk时，（An,Bn）成立； 考虑（Ak，Bk）： 有：Bk=Ak+k,若对手对（Ak，Bk）的操作改变了Ak，或改变了Bk且使BkAk 则Bk-Akk（设为j）。 通过不反复的推导可以推出，经一步变化变化必可以得到（Aj，Bj）。 即：（Ak，Bk）为平衡态,证毕,由数学归纳法可以立得该结论正确。证毕。 结论： 对于任意（Ak，Bk）， Ak：前k-1组未出现过的最小数， Bk：k+Ak 为该组是平衡态（必输态）的充要条件,思路1,我们已经可以描述全

3、部平衡态！ “自下而上”得到全部平衡态 与所输入初值比较 得到结论,具体操作,对于任给的一组数（A，B）（AB），令B-A=n，则列出前n组平衡态，并比较An？=A即可,前50组平衡态,问题,严重超时！ （要先知道上限？） 算法复杂度：O（n2,反思,对一个数列的描述方法： （1）列举法、描述法 （2）递归法 （3）通项公式法 描述法：“自下而上” 得到数列的每一项 其实这是不必要的,对数列进一步分析,观察到： 相邻两项Ak与A(k+1)相差1或2； 相邻两项Bk与B(k+1)相差2或3； 是一般规律吗？ 可以证明,证之,显然：A(k+1)-A(k)=1 则： B(k+1)-B(k)=2 假设

4、：A(k+1)-A(k)=3 则由A(k+1)的性质可知： A(k)+1,A(k)+2都在前k-1组中。 A(k)+1,A(k)+2任一项不可能在A中！（这是已经假设过的） A(k)+1,A(k)+2不可能都在B中！（前面已证,证毕,这说明假设不成立。 所以 相邻两项Ak与A(k+1)相差1或2； 相邻两项Bk与B(k+1)相差2或3； 是一般规律,思路2,检查A中相邻两项之差,2 1 2 2 1 2 1 2 2 1 2 2 1 2 1 2,2 1 2 1 2 2 1 2 2 1 2 1 2 2 1 2 2 1 2 1 2 2 1 2,思路2,采取“自上而下”的办法 对每一个初值，判断其处在哪

5、一大部分，之后再依次判断其处在该大部分的哪一小部分 递归到最小部分 验证是否满足条件,具体操作,参见宫畅同学的代码,反思,算法精深而复杂 非天才不能成也 算法复杂度： log3n log2n 递归法：“自上而下” 得到数列的部分项,对数列的更进一步分析,希望得到通项！ 观察到A，B均是线性递增的 考虑极限情况： 当An，Bn均非常大时，+1/2/3对数列的_影响较小？ 比值,因此考虑是否存在线性关系？ 网上答案,证之,定义K： K的意义： 1n组中，首个超过An的数所在的组数,由线性递增关系立得,1n组中大于An的：(n-K+1)个 （kn组中的B项） 1n组中小于An的：(An-1)个 1n

6、组中等于An的：1个 共计：n-K+1+An-1+1=2n,K=An+1-n 即：K（n）=An+1-n 将K带回原不等式,解左不等式,解右不等式,以相同方法解右不等式可得： 夹逼得到： 证毕,思路3,计算初值对应的项数n 由通项公式计算n对应的An 验证初值是否满足条件 无疑是最简洁的,三种思路的对比与思考,描述法 算法复杂度 n2 对数列的描述：自下而上 递归法 算法复杂度： log3n log2n 对数列的描述：自上而下 通项法 算法复杂度：1 对数列的描述：特征值K,通项公式证明中的启示,夹逼的范围恰到好处 特征值K对数列的描述是完善的。 由此不难引发对于编程的几点思考,几点思考,编程把解决方案用尽量严密的逻辑关系表达、划分、归类,严密,详述,抓住关键,better,本题通过不断的寻找数列的特征得到有用的信息。用尽量少的量完善的描述该数列。 对该数列描述的越准确，编程中的计算量和运算时间就越短。 相反，对该数列描述的