S、P先生数学谜题：
设有两个自然数X、Y，2<=X<=Y<=99,S先生知道这两个数的和S，P先生知道这两个数的积 P ，他们二人进行了如下对话：
S：我确信你不知道这两个数是什么，但我也不知道。
P: 一听你说这句话，我就知道这两个数是什么了。
S: 我也是，现在我也知道了。
现在你能通过他们的会话推断出这两个数是什么吗？（当然，S和P先生都是非常聪明的）
S、P先生数学谜题的思路：
首先已声明2<=x<=y<=99，且x，y都是自然数。
1、S先生说：“我不知道这两个数。”，这就可知S决不是：
4(=2+2)；5(=2+3)；197(=98+99)；198(=99+99)。
把这些S的不可能的值及其对应的X，Y的组合存储到数组US[]中。
2、S先生说：“我确定你也不知道这两个数。”，这就可知P决不是：
（1） 两端的数之积，如4(=2*2)；6(=2*3)；8=(2*4)；10(=2*5)；。。。
9801（=99*99）；9702（=98*99）；9604（=98*98）。
（2） 素数或者素数之积，如5，7，11，。。。25（=5*5），35（=5*7）。
把这些P的不可能的值及其对应的X，Y的组合存储到数组UP[]中。
UP共有2981个元素，它们是：
UP={4 5 6 7。。。4316 4327 4331 。。。9781 9787 9791 9801}
那么可以根据这些X，Y的组合求出对应的S（=X+Y）来，把它们加入到数组US[]中。这样一来，S的数又可以排除一些了。
比如6(=2+4)；7(=2+5)；...10(=5+5);...。
如此一来，就可以初步总结出S可能的数的集合：
S={ 11 ，17 ，23 ，27 ，29 ，35 ，37 ，41 ，47 ，53 }。
同理，根据UP[]也初步总结出P可能的数的集合。但此时P的数目还是很大的，总计有6817个。
P={ 12 16 18。。。4317 4318 4319。。。9798 ，9799 ，9800 }
注意：因为S和P先生都是非常聪明的，所以他们都能够推出上面的S和P。
3、P先生说：“一听你的话，我就知道了。”，这是可以判断P的可能数值的。
我们这样来分析，将P分解后，将得到多个X，Y的组合，分别求出每个组合对应的S（=X+Y）。
例如，P=X*Y得到的X，Y 组合有32（=2*16=4*8），对应的S有18=2+16；12=4+8，因为18和12都不属于S，因此这两个X，Y的组合都是错的；
又如72(=2*36=3*24=4*18=6*12=8*9)也不行，因为3+24=27和8+9=17均属于S，即对于同一个P，有两个不同的X，Y组合属于S。这样P先生根本无法确定唯一的X，Y组合。
那要在什么条件下P先生才能确定唯一的X，Y组合呢？答案就是：当从P中分解出来的多个X，Y组合中有且仅有一个属于S。按照这个方法，
我们可以找出满足条件的P的集合（共86个）：
P={ 18 24 28 50 52 54 76 92 96 100 110 112 114 124 130 138 140 148 152 154 160 162 168 170 172 174 176 182 186 190 198 204 208 216 232 234 238 240 246 250 252 270 276 280 282 288 294 304 306 310 336 340 348 360 364 370 378 390 400 408 414 418 430 442 480 492 496 510 520 522 532 540 550 552 570 592 612 630 646 660 672 682 690 696 700 702 }
P先生就可以把他所知道的P进行分解，然后把分解出来的多个X，Y组合一个个去构成对应的S，这样就可以找到唯一的X，Y组合。
但是我们毕竟不是P先生，我们并不知道真实的P值，我们知道的只是可能的P的集合，我们还必须根据第三句话，即S先生所说的“我也是，现在我也知道了。”来进一步缩小S的可能值的范围。
注意：因为S先生非常聪明，所以他能够根据P先生的话推出上面的P。
4、S先生说：“我也是，现在我也知道了。”，这样一来，就完全可以判断x，y的数值了。其原理和第3步相同。
即将S分解后，将得到多个X，Y的组合，分别求出每个组合对应的P（=X*Y）。当从S中分解出来的多个X，Y组合中有且仅有一个属于P时，就能确定唯一的X，Y组合了。
这样，S先生根据自己猜出的集合P，再把自己的S分解成x，y组合，把不同的X，Y组合放到P中去验证，求出唯一的解。
但是我们毕竟不是S先生，我们并不知道真实的S值，我们知道的只是可能的S的集合。但幸运的是，此时的S集合中只有一个数了，那就是
S={ 17 }。于是我们也就可以和S先生一样猜出正确的答案了。
注：如果，S的值不止一个的话，我们就可以连立方程X+Y=S和X*Y=P。然后把P和S集合中所有的值一个个代进去算，那么就可以解出满足条件的X，Y组合了，当然此时组合的个数就不一定是唯一的了。
编程算法分析：
根据上面的思路，我们可以得出编程的算法：（为提高算法的通用性，我们设M=2，N=99）
1． 遍历S（M+M〈=S〈=N+N〉，分析构成S的X，Y组合的个数，把组合个数唯一的S（即不可能的S）记录到US数组中。
注意：其实此时的US是很容易推出来的，因为它只有4个数：4(=2+2)；5(=2+3)；197(=98+99)；198(=99+99)。
2． 遍历P（M*M〈=P〈=N*N〉，分析构成P的X，Y组合的个数，把组合个数唯一的P（即不可能的P）记录到UP数组中，并同时记录构成P的组合X，Y。
注意1：如果P为素数，则它不能分解为满足条件的X，Y，因此素数也要记录到UP数组中。
注意2：为减少计算量，可累积构成P的X，Y组合的个数，一旦组合的个数超过1，立即退出循环，分析下一个P。
3． 遍历UP，把构成P的组合X，Y之和S记录下来，并加入到由第一步得到的US中。
注意：这次得到的S包含了4(=2+2)；5(=2+3)；197(=98+99)；198(=99+99)。
所以第一步其实是不必要的。
4． 遍历S（M+M〈=S〈=N+N〉，根据得到的US，利用排除法，得到可能的S的值的集合，记录到数组S[ ]中。
5． 同理，遍历P（M*M〈=P〈=N*N〉，根据得到的UP，利用排除法，得到可能的P的值的集合，记录到数组P[ ]中。
6． 根据P先生的话，遍历数组P[ ]，分析构成P的组合X，Y，判断X+Y是否属于S[]，是则返回1，否则返回0。累积返回值，若最后的返回值为1，则表示从该P中分解出来的多个X，Y组合中有且仅有一个属于S。那这个P就是最新的P的可能值，把它记录到数组MUL[]中，并同时记录构成P的组合X，Y。
遍历完数组P[ ]后，把数组MUL[]复制到P[ ]，得到新的数组P[ ]。
7．同理，根据S先生的话，遍历数组S[ ]，分析构成S的组合X，Y，判断X*Y是否属于P[]，是则返回1，否则返回0。累积返回值，若最后的返回值为1，则表示从该S中分解出来的多个X，Y组合中有且仅有一个属于P。那这个S就是最新的S的可能值，把它记录到数组ADD []中，并同时记录构成S的组合X，Y。
遍历完数组S[ ]后，把数组ADD[]复制到S[ ]，得到新的数组S[ ]。
8．利用穷举法，连立方程X+Y=S和X*Y=P。然后把P和S集合中所有的值一个个代进去算，分别记录满足条件的X，Y组合到X[i]和Y[i]中，并返回其长度。
9． 印出所有满足条件的X，Y组合到X[i]和Y[i]；若没有满足条件的X，Y组合，则打印“没有”。
注意：这种算法的特点是能够同时记录P，S以及对应的组合X，Y的值，因此需要建立一个结构
typedef struct{ //存放两个数之和或积的集合
int x;
int y;
int data;
} SP1;
这样一来，占用的空间就大，但它在函数（int put_us(SP1 *us, SP1 up[], int len_us, int len_up); //根据p的不可能的值的集合 进一步确定 s的不可能的值的集合） 和 函数（int possible_xy(SP1 p[], SP1 s[], int len_s, int len_p, int *px, int *py); //根据P和S的可能的值的集合，判断出X，Y的可能的值的集合） 中可以直接把对应的X，Y代入，而不必遍历X和Y，节省了时间。
但是这种算法它是先求出US和UP，再遍历S，根据US得出新的S；遍历P，根据UP得出新的P。这样的计算量也是比较大的。
为了克服这些缺点，我们可以把算法加以改进。
改进之算法：
1． 遍历S（M+M〈=S〈=N+N〉，分析构成S的X，Y组合的个数，并把组合的个数作为数组S[ s]的元素的值，其下标s即当前被分析的s（=x+y）。用s（=x+y）作为下标的好处很大，因为今后遍历S时，其下标就是X，Y之和。
注意1：在这里数组S[ ]的元素的值不是s（=x+y）本身，而是构成S的X，Y组合的个数。如当S=4时，构成S的X，Y组合的个数只有2+2=4，则s[4 ]=1；同理S[5]=1；S[6]=2，因为2+4=6，3+3=6；S[8]=3。
那么，值为1的元素，表示构成其下标S的X，Y组合的个数是唯一的，那么这个S是不可能的。即，若S[s(=x+y)]=1，则s(=x+y)属于US。
例如，因为S[5]=1，所以5是不可能的S值。
2． 同理，遍历P（M*M〈=P〈=N*N〉，分析构成P的X，Y组合的个数，并把组合的个数作为数组P[ p(=x*y)]的元素的值，其下标p即当前被分析的p（=x*y）。
例如，P[4]=1；P[5]=0；P[6]=1；P[12]=2，P[24]=3。
同理，若P[p(=x*y)]]=1或P[p(=x*y)]=0，则该p(=x*y)]属于UP。
注意：为减少计算量，可判断P[ p(=x*y)]的元素的值，
一旦P[p(=x*y)] 〉1，立即退出循环，分析下一个P。
3． 根据P的不可能的值的集合进一步确定 S的不可能的值的集合。即，若P[p(=x*y)]]=1或P [p(=x*y)]=0，则可以推出S[s(=x+y)]=1。
注意：因为此时确定的S的不可能的值的集合包含了第一步中的US，所以第一步其实是不必要的。
4． 根据S的不可能的值的集合进一步确定 S的可能的值的集合。
遍历S[ ]，若S[s(=x+y)] !=1，则该s(=x+y)是可能的，把它归入数组add[ ]。然后把add[ ]复制到S[ ]，得到新的数组S[ ]。
注意：此时新的数组S[ ]的元素值不再表示组合的个数，而是s（=x+y）本身，它的下标是从0开始的，其长度表示S的可能的值的个数。
5．同理，根据P的不可能的值的集合进一步确定 P的可能的值的集合。
遍历P[ ]，若P[p(=x*y)] !=1并且P[p(=x*y)] !=0，则该p(=x*y)是可能的，把它归入数组mul[ ]。然后把mul[ ]复制到P[ ]，得到新的数组P[ ]。
注意：此时新的数组P[ ]的元素值不再表示组合的个数，而是p(=x*y)本身，它的下标是从0开始的，其长度表示P的可能的值的个数。
6．7．8．9步骤同算法（一） 。
注意：在算法（二）中，P[ ]和S[ ]的元素值开始（1-3步骤）表示的是构成P或S的X，Y组合的个数，而到了第4步以后，P[ ]和S[ ]的元素值表示的是s（=x+y）和p(=x*y)本身，其长度表示P或S的可能的值的个数。
算法（二）不用同时记录P，S以及对应的组合X，Y的值，因此不需要建立结构，而只要建立一个整型数组就可以了。
评论