计算机语言与程序设计

《计算机语言与程序设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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。1分析这是一道比较难的题，想得不对就编不出来。分析问题的思路：考虑每个人在猜数时要“设身处地，顾此思彼”。比如在C猜时，一方面要猜自己

2、头上的数字可能是什么？还要往前想：为什么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(

3、b-c

4、,b,c,1)=check(1,2,3,1);32.第二步让B猜：B看到a=1，c

5、=3，他会想到自己头上的数不是2就是4。B面对的猜测函数为：check(a,a+c,c,2)=check(1,4,3,2);check(a,

6、a-c

7、,c,2)=check(1,2,3,2);4B还会想为什么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);ch

8、eck(a,b,

9、a-b

10、,3)=check(1,2,1,3);6C会想为什么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。8C推测B对C头上的两种可能数字的反映，来判定该排除哪一个，保留哪一个。如果能够保留一个排除一个则CB=true；如

11、果两个都保留或两上都排除,则CB=false。因此CB应为CB1与CB2的异或运算结果。上述这张图的物理意义是：要想判断check(1,2,3,3)是true还是false？要把它转化为check(1,2,3,2)XORcheck(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,

12、b,c,k)为猜数函数，为布尔型函数。其中a,b,c分别为A、B、C三人帽子上的数，k为第k次猜。规定k=1为A猜，k=2为B猜，k=3为C猜。如猜测次数超过3，则有kmod3=1为A猜，kmod3=2为B猜，kmod3=0为C猜。1011AC1=check(b+c,b,c,k-1);AC2=check(abs(b-c),b,c,k-1);AC=AC1XORAC2;BA1=check(a,a+c,c,k-1);BA2=check(a,abs(a-c),c,k-1);BA=BA1XORBA2;CB1=check(a,b,a+b,k-1);CB2=check(a,

13、b,abs(a-b),k-1);CB=CB1XORCB2;12说明：1.结点F是函数check(a,b,c,k)，意思是第k次猜出来了吗？如果函数值为true表示猜出来了，false表示猜不出来。2.结点F是一个或结点，以k=0还是k>0分支。当k=0时为直接可解结点E，函数值为false，可解释为还没让猜，当然为false。133.当k>0时，分支至D结点。D也是一个或结点，有三个分支：当kmod3=1时，分支至A结点，意思是轮到A猜了；当kmod3=2时，分支至B结点，意思是轮到B猜了；当kmod3=0时，分支至C结点，意思是轮到C猜了。144.A结点有两

14、个分支当b=c时，A=true，即A能