1、由感性认识到理性认识 透析一类搏弈游戏的解答过程 认识事物的过程事物的现象 认识的感性阶段 ? 事物的本质 认识的理性阶段 人们认识事物，总是 从简单入手 。究竟如何才能 由浅入深 呢？并不是人人都能从简单的事物中得到 一般性的规律 。游戏 甲乙两人面对若干排石子。 每一排石子的数目可以任意确定。 两人轮流按下列规则取走一些石子： 每一步必须从某一排中取走两枚石子； 这两枚石子必须是 紧紧挨着 的； 如果谁无法按规则取子，谁就是输家。a1=7a2=3a3=51 2 3 4 5 6 7规则分析a1=7如果一排有 7枚石子而你取了 3、 4这两枚石子，可以看作是将这一排分成了两排，其中一排有 2枚
2、石子，另一排有 3枚石子。 局面的排数可能会随着游戏的进行而增加。a1=2a2=3从简单入手 用一个无序多元组 (a1, a2, , a n)， 来描述游戏过程中的一个局面。(3, 3, 1) 若初始局面可以分成两个相同的 “子局面 ”，则乙有必胜策略。(3, 3, 3, 3, 1, 1)+ 负(3, 3, 1)(3)+(3)+(1)加法分解加法+ +若先行者有必胜策略，则称为 “胜局面 ”。若后行者有必胜策略，则称为 “负局面 ”。局面的分解胜 负 胜+ =负 负 负+ =胜 胜 ?+ = X C+C X+ =X X 负+ =X 负 X+ =局面与集合我们只关心局面的胜负。X C+C X+
3、=(2, 2, 2, 7, 9, 9) (2, 2, 2, 7) + (9)+(9)= (2, 2, 2, 7)(2, 7)用集合 2, 7来表示 这实质上是简化了局面的表示。Z能不能进一步简化一个局面的表示呢？*一个局面可以用一个集合来描述。类比 局面的加法 胜 +负 =胜； 负 +胜 =胜； 负 +负 =负； 胜 +胜 =不定。 二进制数的不进位加法：对二进制数的每一位，采用 01加法。 二进制的 01加法 VS 局面的加法 1 + 0 = 1；胜 +负 =胜； 0 + 1 = 1；负 +胜 =胜； 0 + 0 = 0；负 +负 =负； 1 + 1 = 0；胜 +胜 =不定。 二进制数的加
4、法 VS 局面的加法胜 负 胜+ =负 负 负+ =胜 胜 ?+ =!0 0 !0+ =0 0 0+ =!0 !0 ?+ =0011+ 101010011010+ 10100000胜 !0，负 0局面的加法，与二进制数的加法，性质完全相同。联想Z能否用一个二进制数，来表示一个局面呢？ #S=#(a1, , a n)=f(a1)+f(a n)。 关键就在于函数 f(x)的构造。S#S(3)#(3)#(3, 3)=#(3)+#(3)(3) (3)(3, 3)+=+=#(3, 3, 1)=#(3)+#(3)+#(1)(3, 3, 1) (3) (3) (1)+ +=+ +=#(3, 3, 1)=f(3)+f(3)+f(1)用符号 #S， 表示局面 S所对应的二进制数，简称局面 S的值。#S=0S负， #S0S胜。构造 集合 g(x)： 表示局面 (x)， 下一步可能局面的值的集合。(5)(1, 4)(2, 3)(7)g(7)=#(5), #(1, 4), #(2, 3)可以证明，令函数 f(x)为 g(x)中没有出现的最小非负整数，满足要求。G如果 g(x)=0, 1, 2, 5, 7, 8, 9， 则 f(x)=3。令 G(x)为 g(x)在非负整数集下的补集。令 f(x)=minG(x)， 满足要求。取两枚相邻石子
