计算机语言与程序设计.ppt

聪明的学生聪明的学生 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=1。1分析分析 这是一道比较难的题，想得不对就编不出来。分析问题的思路：考虑每个人在猜数时要“设身处地，顾此思彼”。比如在C猜时，一方面要猜自己头上的数字可能是什么？还要往前想：为什么B猜不出？A猜不出？为了分析方便，定义一个猜中与否的函数（函数值为布尔类型）check(a,b,c,k)k=1表示A猜，k=2表示B猜，k=3表示C猜，下面我们用一个例子来说明思路。2例子例子 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);32.第二步让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);4 B还会想为什么A猜不到呢？B想：如果b2=2，A看到b=2，c=3，会想到自己头上的数是 如果b2=4，A看到b=4，c=3，会想到自己头上的数是 这两种情况A都不敢猜。B认为A不敢猜有道理，B自己也不敢猜。53.第三步让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);6 C会想为什么B猜不到呢？C想：如果c3=1，对B而言，B看到a=1，c3=1,B会很快判断出b=a+c3=1+1=2。可是B并未猜出，说明c3=1应被排除。两种可能性，一个被排除了，另一个就是所求了，即c3=3。我们用“与或”结点图来描述C的猜测过程。7 在上图中，CB1表示的是，C想：如果自己头上是3，B能不能猜出b=2。CB2表示的是，C想：如果自己头上是1，B能不能猜出b=2。8 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。9 下面我们给出更为全面的与或结点图。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猜。1011AC1=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;12说明：1.结点F是函数check(a,b,c,k)，意思是第k次猜出来了吗？如果函数值为true表示猜出来了，false表示猜不出来。2.结点F是一个或结点，以k=0还是k0分支。当k=0时为直接可解结点E，函数值为false，可解释为还没让猜，当然为false。133.当k0时，分支至D结点。D也是一个或结点，有三个分支：当 k mod 3=1 时，分支至A结点，意思是轮到A猜了；当 k mod 3=2 时，分支至B结点，意思是轮到B猜了；当 k mod 3=0 时，分支至C结点，意思是轮到C猜了。144.A结点有两个分支当 b=c 时，A=true，即A能猜出来 a=b+c;当 bc 时，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;当 ac 时，B=BA，BA=check(a,a+c,c,k-1)XOR check(a,abs(a-c),c,k-1)156.C结点有两个分支当 a=b 时，C=true，即C能猜出来 c=a+b;当 ab 时，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)；16 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函数的分析，由此不难写出描述该函数的程序17function 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(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;18当我们已经构造出一个猜中与否的函数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 时19同时猜中者头上的数即为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次之前一定猜不出来。20下面给出process的与或结点图来描述寻找a,b,c的思路。对该图的说明如下:212223241.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 时的LA25LA也是一个与结点，它有4项相关联的节点An，An1，An2 和 An3。2.1 An=check(m,b,m-b,n)其中b=1,2,m-1，n满足n%3=1。An的物理意义是，在上述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猜出，是真还是假？262.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函数；否则什么都不做。272.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。283.1 Bn=check(a,m,m-a,n)其中a=1,2,m-1；n%3=2。Bn的物理意义是，在上述a,b,c,n情况下测 试能否让B猜出来3.2 Bn1=check(a,m,m-a,n-1)其中a=1,2,m-1；(n-1)%3=1。Bn1的物理意义是，在上述a,b,c,n-1的情况 下，测试能否让A猜出来 29 3.3 Bn2=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函数,存入一个方案中；否则什么都不做。304.对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.1 Cn=check(a,m-a,m,n)其中a=1,2,m-1；n%3=0。Cn的物理意义是，在上述a,b,c,n情况下测 试能否让A猜出来314.2 Cn1=check(a,m-a,m,n-1)其中a=1,2,m-1；(n-1)%3=2。Cn1的物理意义是，在上述a,b,c,n-1的情况 下，测试能否让B猜出来 4.3 Cn2=check(a,m-a,m,n-2)其中a=1,2,m-1；(n-2)%3=1 Cn2的物理意义是，在上述a,b,c,n-2的情况 下，测试能否让A猜出来32 4.4 Cn3是一个或结点，它是根据条件C的满足 与否来分支。条件C为：Cn&!Cn1&!Cn2 条件C是说在同样a,b,c的情况下，只有C能 猜中，B和A都猜不出.当条件C满足时，将这组数据(a,m-a,m)调用add函数,存入一个方案中；否则什么都不做。下面是用C语言编写的程序:33#include /预编译命令预编译命令#include /预编译命令预编译命令#include /预编译命令预编译命令int check(int,int,int,int);/声明有被调用函数声明有被调用函数void process(int,int);/声明有被调用函数声明有被调用函数static int alist100,blist100,clist100;/定义三个数组定义三个数组static int num=0;/方案数预置方案数预置0void add(int a,int b,int c)/自定义函数自定义函数,将解将解a,b,c存入数组存入数组/add开始开始alistnum=a;/a存入数组存入数组alistblistnum=b;/b存入数组存入数组blistclistnum=c;/c存入数组存入数组clistnum=num+1;/方案数加一方案数加一/add结束结束34void main()/主函数主函数/主程序开始主程序开始 int i;int n,m;/整型变量整型变量 printf(请输入请输入 n=);/提示信息提示信息 scanf(%d,&n);/输入正整数输入正整数n printf(请输入请输入 m=);/提示信息提示信息 scanf(%d,&m);/输入正整数输入正整数m process(n,m);/process为被调用函数为被调用函数 printf(We found%d resolutionsn,num);for(i=0;inum;i=i+1)/输出解的结果输出解的结果 printf(a=%d b=%d c=%dn,alisti,blisti,clisti);/主程序结束主程序结束35/以下函数是被主程序调用的函数以下函数是被主程序调用的函数int check(int a,int b,int c,int k)/整型自定义函数整型自定义函数,a,b,c,k为形参为形参 /自定义函数体开始自定义函数体开始 int ac1,ac2,ac,ba1,ba2,ba,cb1,cb2,cb;int res;if(kc)res=check(b-c,b,c,k-2);/C对对A的数据作出反应的数据作出反应 if(cb)res=check(c-b,b,c,k-1);/B对对A的数据作出反应的数据作出反应 break;/跳出跳出switchcase 2:if(a=c)res=(k=2);/B猜猜 if(ac)res=check(a,a-c,c,k-1);/A对对B的数据作出反应的数据作出反应 if(ca)res=check(a,c-a,c,k-2);/C对对B的数据作出反应的数据作出反应 break;/跳出跳出switch36case 0:if(a=b)res=(k=3);if(ba)res=check(a,b,b-a,k-1);/B对对C的数据作出反应的数据作出反应 if(ab)res=check(a,b,a-b,k-2);/A对对C的数据作出反应的数据作出反应 break;/跳出跳出switch /switchreturn res;/反回猜测结果反回猜测结果 /checkvoid process(int n,int m)/自定义函数自定义函数 /process开始开始int a,b,c;/定义整型数定义整型数int An,An1,An2;/定义整型数定义整型数int Bn,Bn1,Bn2;/定义整型数定义整型数 int Cn,Cn1,Cn2;/定义整型数定义整型数37switch(n%3)/switch开始开始 case 1:/CASE 1 开始开始for(b=1;bm;b=b+1)/枚举枚举b An=check(m,b,m-b,n);/同样的数据让同样的数据让A猜猜 An1=check(m,b,m-b,n-1);/同样的数据让同样的数据让C猜猜 An2=check(m,b,m-b,n-2);/同样的数据让同样的数据让B猜猜 if(An&!An1&!An2)/如果如果A猜中且猜中且C,B猜不中猜不中 add(m,b,m-b);/则增加一个解则增加一个解 break;/跳出跳出switch /CASE 1 结束结束 case 2:/CASE 2 开始开始 for(a=1;am;a=a+1)/枚举枚举a Bn=check(a,m,m-a,n);/同样的数据让同样的数据让B猜猜 Bn1=check(a,m,m-a,n-1);/同样的数据让同样的数据让A猜猜 Bn2=check(a,m,m-a,n-2);/同样的数据让同样的数据让C猜猜 if(Bn&!Bn1&!Bn2)/如果如果B猜中且猜中且A,C猜不中猜不中 add(a,m,m-a);/则增加一个解则增加一个解break;/跳出跳出switch /CASE 2 结束结束 38 case 0:/CASE 0 开始开始for(a=1;am;a=a+1)/枚举枚举a Cn=check(a,m-a,m,n);/同样的数据让同样的数据让C猜猜 Cn1=check(a,m-a,m,n-1);/同样的数据让同样的数据让B猜猜 Cn2=check(a,m-a,m,n-2);/同样的数据让同样的数据让A猜猜 if(Cn&!Cn1&!Cn2)/如果如果C猜中且猜中且B,A猜不中猜不中 add(a,m-a,m);/则增加一个解则增加一个解 break;/跳出跳出switch /CASE 0 结束结束/switch结束结束/process结束结束39