计算机语言与程序设计.ppt
39页
1,聪明的学生,A、B、C三人所戴的帽子上各有一个数字，分别为a、b、c每个人只能看到其他二人帽子上的数，而不能看到自己头上的数字可是每个人都知道某两个数相加等于另一个数规定猜数的顺序是ABCA…首猜为A，定义为n=1；次猜为B，定义为n=2；再猜为C，定义为n=3；依次类推如果告诉你第n次猜的人猜出自己头上的数是m，问这三个数是什么数？比如给出n=3，m=2，表示猜中者为C，c=m=2，你的程序应推论出a=b=12,分析,这是一道比较难的题，想得不对就编不出来分析问题的思路：考虑每个人在猜数时要“设身处地，顾此思彼”比如在C猜时，一方面要猜自己头上的数字可能是什么？还要往前想：为什么B猜不出？A猜不出？ 为了分析方便，定义一个猜中与否的函数（函数值为布尔类型）check(a,b,c,k)k=1表示A猜，k=2表示B猜，k=3表示C猜，下面我们用一个例子来说明思路3,例子,a=1, b=2, c=3. 1.第一步让A先猜：A只能看到b=2，c=3，他会想到自己头上的数不是1就是5在有两种可能的情况下，A不敢猜，只能放弃A面对的猜测函数有两个：check(b+c,b,c,1)=check(5,2,3,1);check(|b-c|,b,c,1)=check(1,2,3,1);,4,2.第二步让B猜：B看到a=1，c=3，他会想到自己头上的数不是2就是4。
B面对的猜测函数为：check(a,a+c,c,2)=check(1,4,3,2);check(a,|a-c|,c,2)=check(1,2,3,2);,5,B还会想为什么A猜不到呢？B想：①如果b2=2，A看到b=2，c=3，会想到自己头上的数是②如果b2=4，A看到b=4，c=3，会想到自己头上的数是这两种情况A都不敢猜B认为A不敢猜有道理，B自己也不敢猜6,3.第三步让C猜：C看到a=1，b=2，他会想到自己头上的数不是1就是3C面对的猜测函数为：check(a,b,a+b,3)=check(1,2,3,3);check(a,b,|a-b|,3)=check(1,2,1,3);,7,C会想为什么B猜不到呢？C想：如果c3=1，对B而言，B看到a=1，c3=1,B会很快判断出b=a+c3=1+1=2可是B并未猜出，说明c3=1应被排除两种可能性，一个被排除了，另一个就是所求了，即c3=3我们用“与或”结点图来描述C的猜测过程8,在上图中，CB1表示的是，C想：如果自己头上是3，B能不能猜出b=2CB2表示的是，C想：如果自己头上是1，B能不能猜出b=29,C推测B对C头上的两种可能数字的反映，来判定该排除哪一个，保留哪一个。
如果能够保留一个排除一个则CB=true；如果两个都保留或两上都排除,则CB=false 因此CB应为CB1与CB2的异或运算结果上述这张图的物理意义是：要想判断check(1,2,3,3)是true还是false？要把它转化为 check(1,2,3,2) XOR check(1,2,1,2)check(1,2,1,2)是说让B猜，B如果看到c=1，a=1，他会抢先猜到自己头上的数是2但这不是事实，因为B没敢猜可见B看到的不是c=1，而是另一种可能c=3故B帮助C排除了一种可能，成全了C，让C猜到c=310,下面我们给出更为全面的与或结点图3人猜自己帽子上的数的“与或”结点图定义：check(a,b,c,k)为猜数函数，为布尔型函数其中a,b,c分别为A、B、C三人帽子上的数，k为第k次猜规定k=1为A猜，k=2为B猜，k=3为C猜如猜测次数超过3，则有 k mod 3 = 1 为A猜， k mod 3 = 2 为B猜， k mod 3 = 0 为C猜11,12,AC1=check(b+c,b,c,k-1); AC2=check(abs(b-c),b,c,k-1); AC =AC1 XOR AC2;BA1=check(a,a+c,c,k-1); BA2=check(a,abs(a-c),c,k-1); BA =BA1 XOR BA2;CB1=check(a,b,a+b,k-1); CB2=check(a,b,abs(a-b),k-1); CB =CB1 XOR CB2;,13,说明： 1.结点F是函数check(a,b,c,k)，意思是第k次猜出来了吗？如果函数值为true表示猜出来了，false表示猜不出来。
2.结点F是一个或结点，以k=0还是k>0分支当k=0时为直接可解结点E，函数值为false，可解释为还没让猜，当然为false14,3.当k>0时，分支至D结点D也是一个或结点，有三个分支：当 k mod 3 = 1 时，分支至A结点，意思是轮到A猜了；当 k mod 3 = 2 时，分支至B结点，意思是轮到B猜了；当 k mod 3 = 0 时，分支至C结点，意思是轮到C猜了15,4.A结点有两个分支当 b=c 时，A=true，即A能猜出来 a=b+c;当 b≠c 时，A=AC，AC= check(b+c,b,c,k-1) XOR check(abs(b-c),b,c,k-1) 5.B结点有两个分支当 a=c 时，B=true，即B能猜出来 b=a+c;当 a≠c 时，B=BA，BA= check(a,a+c,c,k-1) XOR check(a,abs(a-c),c,k-1),16,6.C结点有两个分支当 a=b 时，C=true，即C能猜出来 c=a+b;当 a≠b 时，C=CB，CB= check(a,b,a+b,k-1) XOR check(a,b,abs(a-b),k-1) 7.判断A、B、C、三个结点的取值可用如下的三个布尔表达式：A = ( b=c ) or( check(b+c,b,c,k-1) XORcheck(abs(b-c),b,c,k-1) )；,17,B = ( a=c ) or( check(a,a+c,c,k-1) XORcheck(a,abs(a-c),c,k-1) )；C = ( a=b ) or( check(a,b,a+b,k-1) XORcheck(a,b,abs(a-b),k-1) )；以上是对check函数的分析，由此不难写出描述该函数的程序,18,function check(a,b,c,k:integer):boolean; beginif k=0 thenbegincheck:=false; exit;end;case k mod 3 of1: check:= (b=c) or ( check(b+c,b,c,k-1)xor check(abs(b-c),b,c,k-1) );2: check:= (a=c) or ( check(a,a+c,c,k-1)xor check(a,abs(b-c),c,k-1) );3: check:= (a=b) or ( check(a,b,a+b,k-1)xor check(a,b,abs(b-c),k-1) );end {case}; end;,19,当我们已经构造出一个猜中与否的函数check时，我们再回到题目的要求上来。
题目是说在第n次猜中者说自己头上的数字是m，希望找出a,b,c来，可能不是一组答案在这里我们用process(int n, int m)这一函数来寻找a、b、c思路是第n次猜时的猜中者很容易判断，即A ， n mod 3 = 1 时该人是 B ， n mod 3 = 2 时C ， n mod 3 = 0 时,,20,同时猜中者头上的数即为m，也就是说a = m, 如果 n mod 3 = 1 时b = m, 如果 n mod 3 = 2 时c = m, 如果 n mod 3 = 0 时无论是谁猜中，也只知道一个人帽子上的数m，而其他两个人头上的数就要根据如下的约束条件用枚举方法来凑了条件1： a=m=b+c，如果 n mod 3 = 1；b=m=a+c，如果 n mod 3 = 2；c=m=a+b，如果 n mod 3 = 0；条件2： 在满足条件1的情况下，还要使a,b,c三个数保证在第n次才能猜出来，在第n次之前一定猜不出来21,下面给出process的与或结点图来描述寻找a,b,c的思路对该图的说明如下:,22,23,24,25,1.process结点可分解为三个分支：当n%3=1时，分支为PA结点，对应猜中者为A；当n%3=2时，分支为PB结点，对应猜中者为B；当n%3=0时，分支为PC结点，对应猜中者为C。
2.对PA结点，将其视为与结点，相关联的节点有PA1 为 b=1 时的LA，PA2 为 b=2 时的LA，.PAm-1为 b=m-1 时的LA,26,LA也是一个与结点，它有4项相关联的节点An，An1，An2 和 An32.1 An=check(m,b,m-b,n)其中b=1,2,…,m-1，n满足n%3==1An的物理意义是，在上述a,b,c,n情况下测试是否能让A猜出m，是真还是假？2.2 An1=check(m,b,m-b,n-1)其中b=1,2,…,m-1; (n-1)%3==0相当于同样的a,b,c数据让C猜，测试是否能让c猜出，是真还是假？,27,2.3 An2=check(m,b,m-b,n-2)其中b=1,2,…,m-1；(n-2)%3==2相当于同样的a,b,c数据让B猜，测试是否 能让B猜出2.4 结点An3是一个或结点，它是根据条件A的满足与否来分支条件A为：An && !An1 && !An2条件A是说在同样a,b,c的情况下，只有A能猜中，B和C都猜不出.当条件A满足时，将这组数据(m,b,m-b)存入一个方案中，调用add函数；否则什么都不做28,2.5 LA相当于是一个以b为循环控制变量的循环的循环体。
接在PA1,b=1;接在PA2,b=2.3.对PB结点，也是与结点，相关联的节点有PB1,PB2,.PBm-1PB1 为 a=1 时的LB，PB2 为 a=2 时的LB，.PBm-1为 a=m-1 时的LBLB是一个与结点，它有4项相关联的节点Bn，Bn1，Bn2和Bn329,3.1 Bn=check(a,m,m-a,n)其中a=1,2,…,m-1；n%3==2Bn的物理意义是，在上述a,b,c,n情况下测试能否让B猜出来3.2 Bn1=check(a,m,m-a,n-1)其中a=1,2,…,m-1；(n-1)%3==1Bn1的物理意义是，在上述a,b,c,n-1的情况下，测试能否让A猜出来,30,3.3 Bn2=check(a,m,m-a,n-2)其中a=1,2,…,m-1；(n-2)%3==0Bn2的物理意义是，在上述a,b,c,n-2的情况下，测试能否让C猜出来3.4 Bn3是一个或结点，它是根据条件B的满足与否来分支条件B为：Bn && !Bn1 && !Bn2条件B是说在同样a,b,c的情况下，只有B能猜中，A和C都猜不出.当条件B满足时，将这组数据(a,m,m-a)调用add函数,存入一个方案中；否则什么都不做。
31,4.对PC结点，也是与结点，相关联的节点有PC1,PC2,.PCm-1PC1 为 a=1 时的LC，PC2 为 a=2 时的LC，.PCm-1为 a=m-1 时的LCLC是一个与结点，它有4项相关联的节点Cn，Cn1，Cn2和Cn34.1 Cn=check(a,m-a,m,n)其中a=1,2,…,m-1；n%3==0Cn的物理意义是，在上述a,b,c,n情况下测试能否让A猜出来,32,4.2 Cn1=check(a,m-a,m,n-1)其中a=1,2,…,m-1；(n-1)%3=2Cn1的物理意义是，在上述a,b,c,n-1的情况下，测试能否让B猜出来4.3 Cn2=check(a,m-a,m,n-2)其中a=1,2,…,m-1；(n-2)%3==1Cn2的物理意义是，在上述a,b,c,n-2的情况下，测试能否让A猜出来,。
