16 例题.ppt

第1页：第十六讲聪明的学生题目

聪明的学生：A、B、C 三人所戴的帽子上各有一个数字，分别为 a、b、c。每个人只能看到其他二人帽子上的数，而不能看到自己头上的数字。可是每个人都知道某两个数相加等于另一个数。规定猜数的顺序是 A→B→C→A→…。首猜为 A，定义为 n=1；次猜为 B，定义为 n=2；再猜为 C，定义为 n=3；依次类推。如果告诉你第 n 次猜的人猜出自己头上的数是 m，问这三个数是什么数？比如给出 n=3，m=2，表示猜中者为 C，c=m=2，你的程序应推论出 a=b=1。

第2页：分析思路

分析：这是一道比较难的题，想得不对就编不出来。分析问题的思路：考虑每个人在猜数时要“设身处地，顾此思彼”。比如在 C 猜时，一方面要猜自己头上的数字可能是什么？还要往前想：为什么 B 猜不出？A 猜不出？为了分析方便，定义一个猜中与否的函数（函数值为布尔类型）：check(a,b,c,k)，其中 k=1 表示 A 猜，k=2 表示 B 猜，k=3 表示 C 猜，下面我们用一个例子来说明思路。

第3页：例子a=1,b=2,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页：第二步让B猜

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 还会想为什么 A 猜不到呢？B 想：

• 如果 b2=2，A 看到 b=2，c=3，会想到自己头上的数是 5 或 1
• 如果 b2=4，A 看到 b=4，c=3，会想到自己头上的数是 7 或 1

这两种情况 A 都不敢猜。B 认为 A 不敢猜有道理，B 自己也不敢猜。

第6页：第三步让C猜

3. 第三步让 C 猜：C 看到 a=1，b=2，他会想到自己头上的数不是 1 就是 3。C 面对的猜测函数为：

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 会想为什么 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与CB2

在上图中，CB1 表示的是，C 想：如果自己头上是 3，B 能不能猜出 b=2。CB2 表示的是，C 想：如果自己头上是 1，B 能不能猜出 b=2。

第9页：异或判断CB

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=3。

第10页：三人猜数的与或结点图

下面我们给出更为全面的与或结点图：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页：与或结点图整体示意

本页为3 人猜数的与或结点图全貌，图中给出 F、D、E、A、B、C 等结点及其分支关系。

第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页：结点F与结点E的说明

说明：

1. 结点 F 是函数 check(a,b,c,k)，意思是第 k 次猜出来了吗？如果函数值为 true 表示猜出来了，false 表示猜不出来
2. 结点 F 是一个或结点，以 k=0 还是 k>0 分支。当 k=0 时为直接可解结点 E，函数值为 false，可解释为还没让猜，当然为 false

第14页：结点D的三个分支

3. 当 k>0 时，分支至D 结点。D 也是一个或结点，有三个分支：当 k mod 3 = 1 时，分支至 A 结点，意思是轮到 A 猜了；当 k mod 3 = 2 时，分支至 B 结点，意思是轮到 B 猜了；当 k mod 3 = 0 时，分支至 C 结点，意思是轮到 C 猜了。

第15页：结点A与结点B的分支

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页：结点C的分支与布尔表达式

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) XOR check(abs(b-c),b,c,k-1) );

第17页：B与C的布尔表达式

B =( a=c ) or( check(a,a+c,c,k-1) XOR check(a,abs(a-c),c,k-1) ); C =( a=b ) or( check(a,b,a+b,k-1) XOR check(a,b,abs(a-b),k-1) );

以上是对 check 函数的分析，由此不难写出描述该函数的程序。

第18页：check函数的程序

function check(a,b,c,k:integer):boolean; begin if k=0 then begin check:=false; exit; end; case k mod 3 of 1: 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(a-c),c,k-1) ); 3: check:= (a=b) or ( check(a,b,a+b,k-1) xor check(a,b,abs(a-b),k-1) ); end {case}; end;

说明：源文件该函数中第 2、3 分支原写作 check(a,abs(b-c),c,k-1) 与 check(a,b,abs(b-c),k-1)，与前面第 15、16 页给出的布尔表达式不一致，整理时按一致的形式修正为 abs(a-c) 与 abs(a-b)。

第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的与或结点图引入

下面给出 process 的与或结点图来描述寻找 a,b,c 的思路。对该图的说明如下：

第22页：process与或结点图

本页为 process 函数的与或结点图，图中按 n%3 的取值分出 PA、PB、PC 三个分支。

第23页：PA结点分解示意

本页为 PA 结点分解的示意图，图中 PA 按 b=1,2,…,m-1 分解为 PA1、PA2 等与结点。

第24页：LA与LB结点示意

本页为 LA 与 LB 结点的示意图，图中给出 An、An1、An2、An3 与 Bn、Bn1、Bn2、Bn3 各结点的关联关系。

第25页：process结点的三个分支

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结点的An与An1

LA 也是一个与结点，它有 4 项相关联的节点 An，An1，An2 和 An3。

• 2.1An=check(m,b,m-b,n) 其中 b=1,2,…,m-1，n 满足 n%3==1。An 的物理意义是，在上述 a,b,c,n 情况下测试是否能让 A 猜出 m，是真还是假？
• 2.2An1=check(m,b,m-b,n-1) 其中 b=1,2,…,m-1；(n-1)%3==0。相当于同样的 a,b,c 数据让 C 猜，测试是否能让 c 猜出，是真还是假？

第27页：LA结点的An2与An3

• 2.3An2=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页：PB结点与LB结点

2.5 LA 相当于是一个以 b 为循环控制变量的循环的循环体。接在 PA1，b=1；接在 PA2，b=2。

3. 对 PB 结点，也是与结点，相关联的节点有 PB1，PB2，……，PBm-1。PB1 为 a=1 时的 LB，PB2 为 a=2 时的 LB，……，PBm-1 为 a=m-1 时的 LB。LB 是一个与结点，它有 4 项相关联的节点 Bn，Bn1，Bn2 和 Bn3。

第29页：Bn与Bn1的物理意义

• 3.1Bn=check(a,m,m-a,n) 其中 a=1,2,…,m-1；n%3==2。Bn 的物理意义是，在上述 a,b,c,n 情况下测试能否让 B 猜出来
• 3.2Bn1=check(a,m,m-a,n-1) 其中 a=1,2,…,m-1；(n-1)%3==1。Bn1 的物理意义是，在上述 a,b,c,n-1 的情况下，测试能否让 A 猜出来

第30页：Bn2与Bn3的条件B

• 3.3Bn2=check(a,m,m-a,n-2) 其中 a=1,2,…,m-1；(n-2)%3==0。Bn2 的物理意义是，在上述 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页：PC结点与LC结点

4. 对 PC 结点，也是与结点，相关联的节点有 PC1，PC2，……，PCm-1。PC1 为 a=1 时的 LC，PC2 为 a=2 时的 LC，……，PCm-1 为 a=m-1 时的 LC。LC 是一个与结点，它有 4 项相关联的节点 Cn，Cn1，Cn2 和 Cn3。

4.1Cn=check(a,m-a,m,n) 其中 a=1,2,…,m-1；n%3==0。Cn 的物理意义是，在上述 a,b,c,n 情况下测试能否让 C 猜出来。

第32页：Cn1与Cn2的说明

• 4.2Cn1=check(a,m-a,m,n-1) 其中 a=1,2,…,m-1；(n-1)%3=2。Cn1 的物理意义是，在上述 a,b,c,n-1 的情况下，测试能否让 B 猜出来
• 4.3Cn2=check(a,m-a,m,n-2) 其中 a=1,2,…,m-1；(n-2)%3==1。Cn2 的物理意义是，在上述 a,b,c,n-2 的情况下，测试能否让 A 猜出来

第33页：Cn3的条件C

4.4 Cn3 是一个或结点，它是根据条件 C 的满足与否来分支。条件 C 为：Cn && !Cn1 && !Cn2。条件 C 是说在同样 a,b,c 的情况下，只有 C 能猜中，B 和 A 都猜不出。当条件 C 满足时，将这组数据 (a,m-a,m) 调用 add 函数，存入一个方案中；否则什么都不做。

下面是用 C 语言编写的程序：

第34页：猜数程序头部与add函数

#include <stdio.h>#include <math.h>#include <stdlib.h>int check(int,int,int,int) ;void process(int,int);static int alist[100],blist[100],clist[100];static int num =0;void add(int a,int b,int c){ alist[num] = a; blist[num] = b; clist[num] = c; num=num+1;} 
第35页：猜数程序主函数
void main(){ int i; int n,m; printf("请输入n=" ); scanf("%d",&n); printf("请输入m=" ); scanf("%d",&m); process(n,m); printf("We found %d resolutions\n", num); for (i=0; i<num; i=i+1) { printf("a=%d b=%d c=%d\n", alist[i], blist[i], clist[i]); } } 
第36页：check函数的C语言实现前半
//以下函数是被主程序调用的函数 int check(int a,int b, int c,int k){ int ac1,ac2,ac,ba1,ba2,ba,cb1,cb2,cb; int res; if (k<=0) return 0; switch(k % 3) { case 1: { if (b==c) res=(k==1); if (b>c) res=check( b-c,b,c,k-2 ); if (c>b) res=check(c-b,b,c,k-1); break; } case 2: { if (a==c) res=(k==2); if (a>c) res=check(a, a-c,c,k-1); if (c>a) res=check(a,c-a,c,k-2); break; } 
第37页：check与process的变量声明
 case 0: { if (a==b) res=(k==3); if (b>a) res=check(a,b,b-a,k-1); if (a>b) res=check(a,b,a-b,k-2); break; } } return res;} void process(int n, int m){ int a,b,c; int An, An1,An2; int Bn, Bn1,Bn2; int Cn, Cn1,Cn2; 
第38页：process函数的两个分支
 switch (n % 3) { case 1: { for(b=1;b<m;b=b+1) { An=check(m,b,m-b,n); An1=check(m,b,m-b,n-1); An2=check(m,b,m-b,n-2); if(An && !An1 && !An2) { add(m,b,m-b); } } break; } case 2: { for(a=1;a<m;a=a+1) { Bn=check(a,m,m-a,n); Bn1=check(a,m,m-a,n-1); Bn2=check(a,m,m-a,n-2); if(Bn && !Bn1 && !Bn2) { add(a,m,m-a); } } break; } 
第39页：process函数的case0与收尾
 case 0: { for(a=1;a<m;a=a+1) { Cn=check(a,m-a,m,n); Cn1=check(a,m-a,m,n-1); Cn2=check(a,m-a,m,n-2); if(Cn && !Cn1 && !Cn2) { add(a,m-a,m); } } break; } }}