http://www.zhihu.com/question/23999095#answer-12373156问题来自知乎
2015-08-17
问题描述：
一个教授逻辑学的教授，有三个学生，而且三个学生均非常聪明！
一天教授给他们出了一个题，教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个！（每个人可以看见另两个数，但看不见自己的）
教授问第一个学生：你能猜出自己的数吗？回答：不能
问第二个，不能
第三个，不能
再问第一个，不能
第二个，不能
第三个：我猜出来了，是144！
教授很满意的笑了。
请问您能猜出另外两个人的数吗？
PS：其实这个问题可以拓展到任意数字m，任意轮k，任意同学s猜出
分析：
1.首先这是一道动态规划想都不用想，不过在动态规划之前，我们先想几个问题：
a.怎么才能一定能猜出来？
b.在猜出来之前，其他人怎么想的？
2.好了带着这两个问题，我们先想第一个问题：a.怎么才能一定能猜出来？
首先我们先明确，0首先不是一个正整除，那么，一定存在（m,m/2,m/2）或者（m/2,m,m/2）或者（m,m/2,m/2）的情况一定能猜得出来，你想呀其他两个人都是同一个数，你自己的数不可能是0吧，嘻嘻嘻，所以马上得出答案。
然后其他情况呢？不用多说，这是根据上一个同学所猜的情况得出来的，那么上一个，上上一个，上上上一个......肯定猜不出来，于是我们知道只要保证本轮是
由于上一轮的一定猜不出来的状态，而来的一定能猜出来的状态，就完事了
那怎么表述这个东西呢？
我们先来看开始的时候：
首先A同学先猜，A同学看到另外俩贴着纸片的逗比，如果他们俩都是相同数字，那么恭喜A同学，他成功猜出他的数字就是另外俩同学的数之和。可是万一不是呢？那就不知道了，比如如果他看到B是2，C是3，那他究竟是1还是5呢？心疼A同学，我们让下一个同学来猜
所以此时A同学的必猜到态是（2,1,1）（比例式，下面同理）（0,0）（第1轮第一个状态）
轮到B同学，B同学的必猜到态也有一个（1,2,1）（0,0），那么因为可怜的A同学已经猜了一次了，那么B自己的数字一定不和C同学的重复（不然A同学早就手舞足蹈了），所以B的必猜到态还可以是（2,3,1），因为B自己的数字不可能和C重复嘛，如果看到A是C的两倍，那么恭喜B同学，他的数字一定是两个数字之和，而不是差，不然就是A同学猜出来
好了如果B同学也猜不出来，那就轮到C同学了，和A,B同学一定，C同学自己的必猜到态也是（1,1,2），然后建立在前俩同学都猜不到的基础上，他会有哪些状态是一定能猜到数字的呢？
如果A的数字是B的俩倍（或反着来），和上面的情况一样，C会有（1,2,3）这个必猜到态，同时也有（2,1,3）这个必猜到态，对称的拉
然后我们注意到B之前已经不能判断（2,3,1）这个状态（也就是这个时候不可能出现这种比例），那么C一定是5（相对于A,B，2+3=5），而不可能是3-2=1（不然就被B猜到了）
好了回头一看，我们已经处理完我们这道题的基准情况了，我们数一下，一开始A有1种必猜到态，B有2种必猜到态，C有4种必猜到态。
接下来就是推进这些基准情况了，我们知道必猜到态一定是建立在必猜不到的状态的基础上的，根据我们上面的推导，你是不是发现了一个规律，如果一个处于K的状态，比如（2,3,？）如果（2,3,1）b不是必猜到态，那么（2,3,5）一定是必猜到态，只要把比例中的另外两个数加起来代替当前比例中的位置，就是必猜到态了，多省事！
另外，当前这个人的猜测是根据另外两个人猜不到的基础上的，所以当前必猜到态的个数一定是之前两个人都猜不出来的状态的和！
设a（x）是必猜到态的个数，则当前必猜到态的个数是
a(x)=a(x-1)+a(x-2) x>=4
= 1 (x=1)
= 2 (x=2)
= 4 (x=3)
这个东西是不是似曾相识，对的没错他就是斐波那契数.....的兄弟OWO
1,2,4,6,10,16,26.....
至于代码，知道原理以后代码就很好写了，主要是要处理不同种情况要小心就好了
#include <stdio.h> #include <stdlib.h> #define MAX 255 static int Win_State[3][MAX][3]; static int Who_Konw; void Initialize_(void); void Search(const int, int[], const int); void Print_Item(const int, int[]); void ReMark(int[], int); int main(void) { int Win_Sum[3]; int m, k, i; printf("输入格式：(数字大小,轮数，第几个同学)\n"); while (1) { Win_Sum[0] = 1; Win_Sum[1] = 2; Win_Sum[2] = 4; Initialize_(); fflush(stdin); if (~scanf("(%d,%d,%d)", &m, &k, &Who_Konw) && k > 0 && Who_Konw > 0 && Who_Konw <= 3) { i = (k - 1) * 3 + Who_Konw; Search(m, Win_Sum, i); } } } void Initialize_(void) { //先定义a(1),a(2),a(3)的三个基准情况 Win_State[0][0][0] = 2; Win_State[0][0][1] = 1; Win_State[0][0][2] = 1; Win_State[1][0][0] = 2; Win_State[1][0][1] = 3; Win_State[1][0][2] = 1; Win_State[1][1][0] = 1; Win_State[1][1][1] = 2; Win_State[1][1][2] = 1; Win_State[2][0][0] = 1; Win_State[2][0][1] = 1; Win_State[2][0][2] = 2; Win_State[2][1][0] = 2; Win_State[2][1][1] = 1; Win_State[2][1][2] = 3; Win_State[2][2][0] = 1; Win_State[2][2][1] = 2; Win_State[2][2][2] = 3; Win_State[2][3][0] = 2; Win_State[2][3][1] = 3; Win_State[2][3][2] = 5; } void Search(const int m, int Win_Sum[], const int Goal_Position) { if (Goal_Position == 1 || Goal_Position == 2 || Goal_Position == 3) Print_Item(m, Win_Sum); else { int i, self; for (i = 4; i <= Goal_Position; i++) { self = (i - 1) % 3; ReMark(Win_Sum, self); } Print_Item(m, Win_Sum); } } void ReMark(int Win_Sum[], int self) { int j, k, p = self; Win_Sum[self] = Win_Sum[(p + 1) % 3] + Win_Sum[(p + 2) % 3]; for (j = 0; j < Win_Sum[self];) { for (k = 0; k < Win_Sum[(p + 1) % 3]; k++, j++) { Win_State[self][j][self] = Win_State[(p + 1) % 3][k][(p + 1) % 3] + Win_State[(p + 1) % 3][k][(p + 2) % 3]; Win_State[self][j][(p + 1) % 3] = Win_State[(p + 1) % 3][k][(p + 1) % 3]; Win_State[self][j][(p + 2) % 3] = Win_State[(p + 1) % 3][k][(p + 2) % 3]; } for (k = 0; k < Win_Sum[(p + 2) % 3]; k++, j++) { Win_State[self][j][self] = Win_State[(p + 2) % 3][k][(p + 1) % 3] + Win_State[(p + 2) % 3][k][(p + 2) % 3]; Win_State[self][j][(p + 1) % 3] = Win_State[(p + 2) % 3][k][(p + 1) % 3]; Win_State[self][j][(p + 2) % 3] = Win_State[(p + 2) % 3][k][(p + 2) % 3]; } } } void Print_Item(const int m, int Win_Sum[]) { int i, sum = 0, p = Who_Konw - 1; for (i = 0; i < Win_Sum[Who_Konw - 1]; i++) { if (m % Win_State[Who_Konw - 1][i][Who_Konw - 1] == 0) { printf("%d:(144,",++sum); printf("%d,", m*Win_State[Who_Konw - 1][i][(p + 1) % 3] / Win_State[Who_Konw - 1][i][Who_Konw - 1]); printf("%d)\n", m*Win_State[Who_Konw - 1][i][(p + 2) % 3] / Win_State[Who_Konw - 1][i][Who_Konw - 1]); } } }
好了代码就是上面，写的其实是有点怪怪的感觉，主要是我用的是数组代表了不同人，这样我只用写一次代码就可以了！而不用多次A，B，C之类的，太烦，所以就产生了三维数组噜
另外第一次在博客园发博客，吐槽一下博客园的代码显示器，单色的太难看了，每次我看代码都要复制到编译器看。。。不然我都不想看下去。。。
另外附上一张VS的图，你们看这样的感觉就很好，一点都没有压抑感（另外说一下Productivity Power Tools 这个插件真的好用，微软自家的就是不一样）
原文：http://www.cnblogs.com/Philip-Tell-Truth/p/4736987.html