S先生和P先生，一道很有意思的问题

Question

《人工智能》课的一个题，虽然已经知道答案，但仍觉得很有意思，不敢独享，答对有分：1）两个数i和j，1＜i,j＜100
2）两个很聪明的人，分别称为S先生和P先生
3）S先生和P先生均不知道i和j究竟是什么。S先生只知道二者的和，P先生只知道i二者的积。
4）S先生和P先生相遇。有下面一段对话：
　　S先生：“我不知道这两个数是多少，我只知道二者的和，但我确信你也不知道。”
　　P先生：“我原来只知道二者的积，但听你这么一说，我现在知道i和j分别是多少了。”
　　S先生：“我现在也知道了”
　　
　　请提供一个思路或写一个程序解出这个问题（i,j的值）。

Answer 1

在条件1中加一条i<=j（原题如此，忘写了，不好意思），不过有没有这条不会影响求解方法和最终答案。

Answer 2

提示一下，是让你写程序解决这个问题，多想想利用下计算机的强大的计算能力。
另外，注意条件1中给出的是1<i,j<100，也就是说i,j不可能为1和100。

Answer 3

下面的程序可以把两个数可能的和列举出来。
还没有全想好，关注中，思考中。// sum != 以下任意两个数之和
// 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
// 5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 24, 25, 26, 28, 
#include <stdio.h>void main()
{
int a[27] = { 2, 3, 5, 7, 11, 13, 17, 29, 23, 29,31, 37, 41, 43,47, 53, 59,61,67,71,73,79,83, 89,91, 97};
  /*  a[0] = 2;
a[1] = 3;
a[2] = 5;
a[3] = 7;
a[4] = 11;
a[5] = 13;
a[6] = 17;
a[7] = 23;
a[8] = 29;
a[9] = 31;
a[10] = 37;
a[11] = 41;
a[12] = 43;
a[13] = 47;
a[14] = 53;
a[15] = 59;
a[16] = 61;
a[17]= 67;
a[18] = 71;
a[19] = 73;
a[20] = 79;*/ int b[1000];
int len;
int c[200];
for (int test = 0; test < 200; test++)
{
c[test] = test + 1;
} int k = 0;
for(int i = 0; i < 26; i++)
{
for(int j = 0; j < 26; j++)
{
b[k++] = a[i] + a[j];
}
} for(int h = 0; h < k; h++)
{
for(int t = 0; t < 200; t++)
{
if(c[t] == b[h])
{
c[t] = -1;
}
}
} for(i = 0; i < 200; i++)
if(c[i] > 0)
printf("%5d", c[i]);
}

Answer 4

首先i,j不可能都是素数(3,5,7,11,13...)不然p就知道了
i+j的和sub不可能分解为另外两个素数之和,因为s确信p不知道
循环找解

Answer 5

to syl08341(沈阳老零):
如果sum知道的是16的话，可能解是(3,13)，那么Product 知道的将是39，则Sum 先生不敢说“确信你也不知道。”!

Answer 6

先发表两个函数，其它的代码正在编写中。
#include <stdio.h>
#include <math.h>int ss[50], ss_len = 0; // 保存１００以内所有素数 及其长度
int p[100]; // 
int sp[200], sp_len = 0; // S+P可能的和 void fun1() // 求１００以内所有素数存入数组中， 并count其长度
{
int i, j, k;
for(i = 3; i < 100; i += 2)
{
bool flag = true;
j = (int) sqrt(i);
for(k = 3; k <= j; k++)
{
if(i % k == 0)
flag = false;
}
if(flag)
ss[ss_len++] = i;
}
}void fun2() // 求Ｓ＋Ｐ之和可能的数，存入ＳＰ，并count其长度
{
int i, j, sum[1000], sum_len = 0;
ss[ss_len] = 2; // 差点忘记了２这个数，它不是素数，但如果是素数的２倍的话，Ｐ就知道了。
for(i = 0; i < ss_len+1; i++)
{
for(j = 0; j < ss_len+1; j++)
{
sum[sum_len++] = ss[i] + ss[j];
}
} for(i = 0; i < 200; i++)
sp[i] = i+1;
for(i = 0; i < 5; i++)
sp[i] = -1; for(i = 0; i < 1000; i++)
{
for(j = 5; j < 200; j++)
{
if(sp[j] == sum[i])
{
sp[j] = -1;
}
}
} int temp[200];
sp_len = 0;
for(i = 0; i < 200; i ++)
{
if(sp[i] > 0 && sp[i] < 200)
temp[sp_len++] = sp[i];
}
for(i = 0; i < sp_len; i++)
sp[i] = temp[i];
}void main()
{
fun1();
fun2();
}

Answer 7

/*思路：完全想通了。sum = i+j;  5 < sum < 198;
分解Sum为i, j; (sum = i + j)
计算sum = i*j;
分解sum为i, j; (sum = i * j)
计算sum = i+j;
最后一步的sum可有多个解。但是有且只有一个sum不等于任意两个素数之和
*/

Answer 8

to Panr:不对，只有一个解
to 沈阳老零：思路已经接近了，但不要老是局限于考虑素数。
　　我上午还有课，先下了。

Answer 9

#include <stdio.h>
#include <math.h>int ss[50], ss_len = 0; // 保存１００以内所有素数 及其长度
int cant[200]; // 不可能的Ｓ＋Ｐ
int sp[200], sp_len = 0; // S+P可能的和 void fun1() // 求１００以内所有素数存入数组中， 并count其长度
{
int i, j, k;
for(i = 3; i < 100; i += 2)
{
bool flag = true;
j = (int) sqrt(i);
for(k = 3; k <= j; k++)
{
if(i % k == 0)
flag = false;
}
if(flag)
ss[ss_len++] = i;
}
}void fun2() // 求Ｓ＋Ｐ之和可能的数，存入ＳＰ，并count其长度
{
int i, j, sum[1000], sum_len = 0;
ss[ss_len] = 2; // 差点忘记了２这个数，它不是素数，但如果是素数的２倍的话，Ｐ就知道了。
for(i = 0; i < ss_len+1; i++)
{
for(j = 0; j < ss_len+1; j++)
{
sum[sum_len++] = ss[i] + ss[j];
}
} for(i = 0; i < 200; i++)
sp[i] = i+1;
for(i = 0; i < 5; i++)
sp[i] = -1; for(i = 0; i < 1000; i++)
{
for(j = 5; j < 200; j++)
{
if(sp[j] == sum[i])
{
sp[j] = -1;
}
}
} int temp[200];
sp_len = 0;
for(i = 0; i < 200; i ++)
{
if(sp[i] > 0 && sp[i] < 200)
temp[sp_len++] = sp[i];
}
for(i = 0; i < sp_len; i++)
sp[i] = temp[i];
}void fun3() // 得出S+P不可能的数
{
int i;
for(i = 0; i < 200; i++)
cant[i] = i + 1;
for(i = 0; i < sp_len; i++)
cant[sp[i]-1] = -1;
}void fun4() // 得出结果
{
int sum, imulj, i1, j1, sum1, i, j, k, count_flag = 0, result_i, result_j;
int count_y = 0;
bool flag; // 判断是否为结果
for(sum = 5; sum < 198; sum++)
{
if(cant[sum-1] == -1)
continue;
for(i = 2; i < sum/2; i++)
{
j = sum - i;
imulj = i * j;
count_flag = 0;
for(i1 = 2; i1 < sqrt(imulj); i1++) // 数量大的话，应该在控制处改为i1 < sqrt(imulj);
{
if(imulj % i1 == 0)
j1 = imulj / i;
sum1 = i1 + j1;
flag = true;
if(cant[sum1-1] > 0)
flag = false;
/* for(k = 0; k < 200; k++)
{
if(sum1 == cant[k])
{
flag = false;
result_i = i1;
result_j = j1;
k = 200;
}
}*/
if(flag)
{
count_flag++;
}
}
if(count_flag == 1)
{
printf("i = %d\tj = %d\t", i, j);
count_y++;
}
}
}
}void main()
{
fun1();
fun2();
fun3();
fun4();
}
/*思路：完全想通了。sum = i+j;  5 < sum < 198;
分解Sum为i, j; (sum = i + j)
计算sum = i*j;
分解sum为i, j; (sum = i * j)
计算sum = i+j;
最后一步的sum可有多个解。但是有且只有一个sum不等于任意两个素数之和
*/

Answer 10

上面“也不可能是两个相等的数，也就是说这两个数之和为奇数。”有误。
exam:16*16

Answer 11

/*让我们分析一下：什么情况下Ｓ肯定不知道答案？
当两数之和大于６是，Ｓ就肯定不知道答案。
什么情况下Ｐ肯定不知道答案？
１。在积为两素数下乘时，
２。在积为素数的两倍时，
３。在积为一个数的平方时，
以上三种情况Ｐ直接可得出答案。
除去这三种情况，Ｐ肯定不知道答案。Ｓ说Ｐ一定不知道答案，
那么就是说Ｓ知道的和不论如何分解，都不可能是两个素数，
也不可能是素数＋２，
也不可能是两个相等的数，也就是说这两个数之和为奇数。// 这里有误，exam:16*16Ｓ说了以后Ｐ知道了答案。
就是说Ｐ所知道的积可以有多种分解方法，
但是排除掉他能直接知道结果的３种情况后，
有且只有一种结果。然后Ｓ也知道答案了。
说明Ｓ所知道的和分解后
有且只有一种结果可以让Ｐ得出结果。根据以上思路，编程
*/
#include <stdio.h>
#include <math.h>int ss[50], ss_len = 0; // 保存１００以内所有素数 及其长度
int cant[200]; // 不可能的Ｓ＋Ｐ
int sp[200], sp_len = 0; // S+P可能的和 void fun1() // 求１００以内所有素数存入数组中， 并count其长度
{
int i, j, k;
for(i = 3; i < 100; i += 2)
{
bool flag = true;
j = (int) sqrt(i);
for(k = 3; k <= j; k++)
{
if(i % k == 0)
flag = false;
}
if(flag)
ss[ss_len++] = i;
}
}void fun2() // 求Ｓ＋Ｐ之和可能的数，存入ＳＰ，并count其长度
{
int i, j, sum[1000], sum_len = 0;
ss[ss_len] = 2; // 差点忘记了２这个数，它不是素数，但如果是素数的２倍的话，Ｐ就知道了。
for(i = 0; i < ss_len+1; i++)
{
for(j = 0; j < ss_len+1; j++)
{
sum[sum_len++] = ss[i] + ss[j];
}
} for(i = 0; i < 200; i++)
sp[i] = i+1;
for(i = 0; i < 5; i++)
sp[i] = -1; for(i = 0; i < 1000; i++)
{
for(j = 5; j < 200; j++)
{
if(sp[j] == sum[i])
{
sp[j] = -1;
}
}
} int temp[200];
sp_len = 0;
for(i = 0; i < 200; i ++)
{
if(sp[i] > 0 && sp[i] < 200)
temp[sp_len++] = sp[i];
}
for(i = 0; i < sp_len; i++)
sp[i] = temp[i];
}void fun3() // 得出S+P不可能的数
{
int i;
for(i = 0; i < 200; i++)
cant[i] = i + 1;
for(i = 0; i < sp_len; i++)
cant[sp[i]-1] = -1;
}void fun4()
{
int sum, i, j, imulj, i1, j1, k, sum1;
bool flag_i, flag_i1;
int count_i, count_i1; for(sum = 7; sum < 199; sum++)
{
flag_i = true;
count_i = 0;
for(i = 2; i <= sum/2; i++)
{
j = sum - i;
imulj = i * j;
k = (int)sqrt(imulj);
flag_i1 = true;
count_i1 = 0;
for(i1 = 2; i1 <= k; i1++)
{
if(imulj % i1 == 0)
{
j1 = imulj / i1;
sum1 = i1 + j1;
if(sum1 < 198)
{
if(cant[sum1-1] > 0)
flag_i1 = false;
if(flag_i1)
{
count_i1++;
}
}
}
}
if(count_i1 == 1)
count_i++;
}
if(count_i == 1)
printf("i = %d\tj = %d\n", i, j);
}
}void main()
{
fun1();
fun2();
fun3();
fun4();
}

Answer 12

下面是我的程序，但是好像不是很正确，贴上来先，晕，共找出1930组解，可能
我对下面两句话还没有完全理解，然后这才是问题的关键：Ｓ说了以后Ｐ知道了答案。
然后Ｓ也知道答案了。
// SumProduct.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include <string.h>
#include <math.h>#define MIN_NUMBER     2
#define MAX_NUMBER     99
#define MAX_SUM_LIST   100
#define MAX_PRIME_NUM  (MAX_NUMBER+1)struct sum_type
{
    unsigned char i;
    unsigned char j;
};int prime_flag[MAX_PRIME_NUM];
int sum_cancel[MAX_NUMBER+MAX_NUMBER+1];
int product_count[MAX_NUMBER*MAX_NUMBER+1];/* 求2-maxnum的素数序列 */
void findprime(int maxnum)
{
    //prime_flag清零
    memset(prime_flag, 0, sizeof(int)*MAX_PRIME_NUM);
    prime_flag[0] = 1;      //0,1都不是素数, 值为0表示是素数，为1时表示是合数
    prime_flag[1] = 1;    for(int check=2; check<maxnum; check++)
    {
        if(0 == prime_flag[check])  //找到序列中第一个不是合数的数(即是素数)
        {
            for(int n=2; n<=maxnum/check; n++)
                prime_flag[check*n] = 1;    //去掉这个素数的所有2以上的倍数
        }
    }
}
/* 计算任意两个素数相加的值, 这些值在计算SUM的时候是要去掉的 */
void pluseachprime(int maxnum)
{
    //sum_cancel清零
    memset(sum_cancel, 0, sizeof(int)*(MAX_NUMBER+MAX_NUMBER+1));
    for(int prime1=2; prime1<maxnum; prime1++)
    {
        if(0 == prime_flag[prime1])
        {
            for(int prime2=2; prime2<maxnum; prime2++)
            {
                if(0 == prime_flag[prime2])
                    sum_cancel[prime1+prime2] = 1;  //1表示是要去掉的SUM
            }
        }
    }
}/* 计算sum可分解为sum=i+j的个数和序列 */
int checksum(int sum, sum_type *sumlist)
{
    int scount=0;
    int i,j;    //sumlist清零
    memset(sumlist, 0, sizeof(sum_type)*MAX_SUM_LIST);    for(i=2; i<=sum/2; i++)
    {
        j=sum-i;
        if(j <= MAX_NUMBER)
        {
            sumlist->i=i;
            sumlist->j=j;
            sumlist++;
            scount++;
        }
    }    return(scount);
}/* 计算product=i*j的分解方法的个数 */
int checkproduct(sum_type &sumtype)
{
    int product;
    int pcount=0;
    int i,j;
    i = sumtype.i;
    j = sumtype.j;    if(0 == prime_flag[i] && 0 == prime_flag[j])    //如果i,j都是素数则必然只能有一种积的分解
        return(1);    product = i*j;    if(0 == product_count[product])     //product是否已经计算过?如是，则不必重复计算
    {
        for(int multi=2; multi<=sqrt(product); multi++)
        {
            if(0 == (product % multi))  //product是否可以整除multi?
            {
                pcount++;
            }
        }
        product_count[product] = pcount;
    }
    else
        pcount = product_count[product];    return(pcount);
}int main(int argc, char* argv[])
{
    int sum;
    int length;
    int products;
    int total=0;
    sum_type sumlist[MAX_SUM_LIST];    //product_count清零
    memset(product_count, 0, sizeof(int)*MAX_NUMBER*MAX_NUMBER);    //找出2-MAX_PRIME_NUM的素数序列
    findprime(MAX_PRIME_NUM);    //计算任意两个素数相加的值, 这些值在计算SUM的时候是要去掉的
    pluseachprime(MAX_PRIME_NUM);    //搜索和为4-198的i,j值
    for(sum=4; sum<=198; sum++)
    {
        //排除等于两个素数之和的sum
        if(0 == sum_cancel[sum])
        {
            sum_type *plist = sumlist;
            if((length = checksum(sum, plist)) > 1) //sum的分解可能性要大于1，否则S就知道了
            {
                for(int index=0; index<length; index++)
                {
                    //product的分解可能性也要大于1,否则P也就知道了
                    if((products = checkproduct(sumlist[index])) > 1)
                    {
                        int i,j;
                        i = sumlist[index].i;
                        j = sumlist[index].j;
                        printf("i=%d, j=%d,\t sum=%d, product=%d.\n",
                            i, j, i+j, i*j);
                        /*
                        if(total % 21 == 20)
                        {
                            printf("press Enter to continue...\n");
                            char s[1];
                            gets(s);
                        }
                        */
                        total++;
                    }
                }
            }
        }
    }
    printf("\nHello everybody :-)\n");
    printf("total = %d.\n", total);
    return 0;
}

Answer 13

睡觉去了，晚上再来改进，现在改进了一下checkproduct（）：/* 计算product=i*j的分解方法的个数 */
int checkproduct(sum_type &sumtype)
{
    int product;
    int pcount=0;
    int i,j;
    int multi;
    int faciend;
    int sum;    i = sumtype.i;
    j = sumtype.j;    if(0 == prime_flag[i] && 0 == prime_flag[j])    //如果i,j都是素数则必然只能有一种积的分解
        return(1);    product = i*j;    if(0 == product_count[product])     //product是否已经计算过?如是，则不必重复计算
    {
        for(multi=2; multi<=sqrt(product); multi++)
        {
            if(0 == (product % multi))  //product是否可以整除multi?
            {
                faciend = product / multi;  //被乘数
                sum = multi + faciend;      //乘数和被乘数之和
                if(sum < MAX_NUMBER*2)
                {
                    if(0 == sum_cancel[sum])
                        pcount++;
                }
            }
        }
        product_count[product] = pcount;
    }
    else
        pcount = product_count[product];
    
    return(pcount);
}

Answer 14

又改进了一下，只剩下248组解了，不知道正解在不爱其中，应该在吧。/* 计算product=i*j的分解方法的个数 */
int checkproduct(sum_type &sumtype)
{
    int product;
    int pcount=0, pvalid=0;
    int i,j;
    int multi;
    int faciend;
    int sum;
    bool bCut = false;    i = sumtype.i;
    j = sumtype.j;    //如果i,j都是素数则必然只能有一种积的分解
    if(0 == prime_flag[i] && 0 == prime_flag[j])
        return(1);    product = i*j;    if(0 == product_count[product])     //product是否已经计算过?如是，则不必重复计算
    {
        for(multi=2; multi<=sqrt(product); multi++)
        {
            if(0 == (product % multi))  //product是否可以整除multi?
            {
                faciend = product / multi;  //被乘数
                sum = multi + faciend;      //乘数和被乘数之和
                if(sum <= MAX_NUMBER*2)
                {
                    pcount++;
                    if(0 == sum_cancel[sum])
                        pvalid++;
                }
            }
        }
        if(pvalid == 1 && pcount > 1)
            pcount = 2;
        else
            pcount = 1;
        product_count[product] = pcount;
    }
    else
        pcount = product_count[product];
    
    return(pcount);
}

Answer 15

To 沈阳老零：很遗憾，没有正确的解。解题的关键在于弄清S先生和P先生的推理过程，是不是素数倒是其次，因为计算机解题完全可以漫天撒网。这是我们上硕士《人工智能》课时老师出的一道题（计算机专业），但根本不需要什么高深的理论，关键是思路要清晰。

Answer 16

To Shines:没错，你说的这两句话正是问题的关键。但程序好象不对劲，应该是还没思路还没理清...

Answer 17

To Shines:
Thanks,我犯了一个常识性的错误，２也是素数

Answer 18

下面是我的思路：
从SUM入手。
SUM的所有分解中，有且只有一个product = i * j满足下面条件
     product所有分解中，有且只有一个sum1 = i1 + j1满足下面条件
            sum1的所有分解中，product1 = i2 * j2都有２个以上的解
然后将根据上面的思路编程。现在才发现程序设计中，文档的工作很重要，可以使你少作许多无用功。编程中…

Answer 19

下面是一个失败的尝试，有５０组解，不知道错误在哪里？
/*下面是我的思路：
从SUM入手。
SUM的所有分解中，有且只有一个product = i * j满足下面条件
     product所有分解中，有且只有一个sum1 = i1 + j1满足下面条件
            sum1的所有分解中，product1 = i2 * j2都有２个以上的解
然后将根据上面的思路编程。*/
#include <stdio.h>
#include <math.h>int analyze(int product) // 返回product可以分解为多少组数的乘积。
{
int i, k, result = 0;
k = (int) sqrt(product);
for(i = 2; i <= k; i++)
{
if(product % i == 0)
result++;
} return result;
}int main()
{
int sum, product, i, j, i1, j1, i2, j2, sum1, product1, count_product, count_sum1, k, k1;
int temp_result = 0;
bool flag_sum1;
for(sum = 0; sum < 99; sum++)
{
count_product = 0;
for(i = 2; i <= sum/2; i++)
{
j = sum - i;
product = i * j;
k = (int) sqrt(product);
k1 = product / 200 + 1; // 为了防止出现 j1 大于200
count_sum1 = 0; for(i1 = k1; i1 <= k; i1++)
{
if(product % i1 == 0)
j1 = product / i1;
sum1 = i1 + j1;
flag_sum1 = true; for(i2 = 2; i2 <= sum1/2; i2++)
{
j2 = sum1 - i2;
product1 = i2 * j2;
if(analyze(product1) < 2)
{
flag_sum1 = false;
break;
}
} if(flag_sum1)
count_sum1++;
}
if(count_sum1 == 1)
{
count_product++;
printf("i = %d\tj = %d\t", i, j);
temp_result++;
}
}
if(count_product == 1)
printf("SUM is %d\n", sum);
} return 0;
}

Answer 20

"Ｓ知道了：则所有可能分解的方法中，只有一种能够让Ｐ知道。"
"Ｐ知道了：则所有可能分解的方法中，只有一种能够让他一定不知道。"
"Ｓ知道Ｐ一定不知道：无论和如何分解，乘积必然有不止一种分解方法。"
Very接近正确了，但你还是没有利用上所有的条件。

Answer 21

思路最重要，程序是其次，不要没想清楚就开始写。
想要答案的话，请留E-mail地址。
我手头上只有答案的DOC档，其中有个图在帖子里很难表示出来。

Answer 22

题目中至少含有以下条件：
1、从二者之和推不出i和j
2、从二者之积推不出i和j
3、i,j满足：从二者之和与二者之积都推不出i和j，但知道确切的乘积的话就能唯一的确定两个因子。（P先生的推理过程）
4、i,j满足：从二者之和与二者之积都推不出i和j，但在知道乘积后就能推出，再根据二者和，就能确定i和j。（S先生的推理过程）现在应该不太难了吧

Answer 23

唉！今天编了一天的程序，搞得头晕脑涨。
不编写了。请把答案传到
头一次在ＣＳＤＮ发现这么有趣的东西，以后有什么好东西，
继续贴出来，让大家一起高兴高兴。最后把我的最后一个程序贴出来，以供大家参考。
/*下面是我的思路：
从SUM入手。
SUM的所有分解中，有且只有一个product = i * j满足下面条件
     product所有分解中，有且只有一个sum1 = i1 + j1满足下面条件
            sum1的所有分解中，product1 = i2 * j2都有２个以上的解
然后将根据上面的思路编程。*/
#include <stdio.h>
#include <math.h>int analyze(int product) // 返回product可以分解为多少组数的乘积。
{
int i, k, result = 0;
k = (int) sqrt(product);
for(i = 2; i <= k; i++)
{
if(product % i == 0)
result++;
} return result;
}int main()
{
int sum, product, i, j, i1, j1, i2, j2, sum1, product1, count_product, count_sum1, k;
bool flag_sum1;
for(sum = 6; sum < 199; sum++)
{
count_product = 0;
for(i = 2; i <= sum/2; i++) // sum分解
{
j = sum - i;
product = i * j;
k = (int) sqrt(product);
count_sum1 = 0; for(i1 = 2; i1 <= k; i1++) // product 分解
{
if(product % i1 == 0)
j1 = product / i1;
if(j1 > 99)
continue;
sum1 = i1 + j1;
flag_sum1 = true; for(i2 = 2; i2 <= sum1/2; i2++) // sum1分解
{
j2 = sum1 - i2;
product1 = i2 * j2;
if(analyze(product1) > 2) // product1分解
flag_sum1 = false;
} if(flag_sum1)
count_sum1++;
}
if(count_sum1 == 1)
count_product++;
}
if(count_product == 1)
{
printf("i = %d\tj = %d\t", i, j);
printf("SUM is %d\n", sum);
}
} return 0;
}

Answer 24

cyberdb
给你开了一个贴子，名字为cyberdb接分。
感谢你给出了一个让人高兴，让人头痛的问题

Answer 25

楼主把答案帮忙传一下吧，我也想知道答案。[email protected]

Answer 26

TO syl08341(沈阳老零):
  http://expert.csdn.net/Expert/topic/1639/1639212.xml?temp=.5416529一个更有意思的问题 呵呵

Answer 27

今天才看到这个东东!
最好楼主不要将答案放在这里!
我希望能自己解决它!
同时希望楼主能把答案发给我一份：[email protected]
我会尽量自己解决，不过在我失去信心的时候，我还是希望可以知道答案!
谢谢!

Answer 28

在还没有充分发现题目的条件之前，我还是延续一下syl08341(沈阳老零)的思路，
他的思路我还是满赞同的，就是反过来想：/*思路，从最后一句往前想
Ｓ知道了：则所有可能分解的方法中，只有一种能够让Ｐ知道。         //正确
Ｐ知道了：则所有可能分解的方法中，只有一种能够让他一定不知道。   //也很正确
Ｓ知道Ｐ一定不知道：无论和如何分解，乘积必然有不止一种分解方法   //这个我还没有很理解，
                                        //道理是对的，可是我不知道为什么要用这个分析
*/那么，我们正过来想：
3）S先生和P先生均不知道i和j究竟是什么。S先生只知道二者的和，P先生只知道i二者的积。
//S不知道，说明sum不可能是4,5,sum>=6，好像sum(和)还有可利用的价值，因为如果就这么简单，问题就很难解决了；
//P不知道，说明product(积)不可能是两个素数的乘积，反过来说，sum也不可能是两个素数的和，其他条件还未发现。4）S先生和P先生相遇。有下面一段对话：
　　S先生：“我不知道这两个数是多少，我只知道二者的和，但我确信你也不知道。”
　　P先生：“我原来只知道二者的积，但听你这么一说，我现在知道i和j分别是多少了。”
　　S先生：“我现在也知道了”
//S确信P也不知道，说明product可分解可能是2种及2种以上，并满足前面的条件(没有充分分析出可用条件，这里都是关键)
//P听S一说就知道了，从二者之和与二者之积都推不出i和j，但知道确切的乘积的话就能唯一的确定两个因子
//S听说P知道了，自己也知道了，从二者之和与二者之积都推不出i和j，但在知道乘积后就能推出，再根据二者和，就能确定i和j。后面是抄楼主的，这是我的分析过程，可能对理清思路有用，好好看。

Answer 29

syl08341(沈阳老零)
精神可嘉阿
我把我n久以前的答案贴出来吧
其实这个问题很多BBS上都讨论过了，算法版说不定就有
ft
详细的算法和程序找不到了
结果记得应该是4,13

Answer 30

答案已E-mail发出。由于邮件服务器好象不太稳定，不知有没有重发或漏发。如果未收到或还有人想要，请留言。

Answer 31

贴个正确解法的程序，下面是运行结果：i=4,  j=13,  sum=17,  product=52.total = 1.//我原来的思路并没有太大错误，只是限制的条件不够严格，导致解过多，
//细想了一下上面的回复，终于找到问题在哪，虽然我的方法跟楼主的肯定不一样
//但也一样解决问题，呵呵。// SumProduct.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include <string.h>
#include <math.h>#define MIN_NUMBER     2
#define MAX_NUMBER     99
#define MAX_SUM_LIST   100
#define MAX_PRIME_NUM  (MAX_NUMBER+1)struct sum_type
{
    unsigned char i;
    unsigned char j;
};int prime_flag[MAX_PRIME_NUM];
int sum_cancel[MAX_NUMBER*2+1];
int product_count[MAX_NUMBER*MAX_NUMBER+1];int sum_flag[MAX_NUMBER*2+1];
int product_flag[MAX_NUMBER*MAX_NUMBER+1];/* 求2-maxnum的素数序列 */
void findprime(int maxnum)
{
    //prime_flag清零
    memset(prime_flag, 0, sizeof(int)*MAX_PRIME_NUM);
    prime_flag[0] = 1;      //0,1都不是素数, 值为0表示是素数，为1时表示是合数
    prime_flag[1] = 1;    for(int check=2; check<maxnum; check++)
    {
        if(0 == prime_flag[check])  //找到序列中第一个不是合数的数(即是素数)
        {
            for(int n=2; n<=maxnum/check; n++)
                prime_flag[check*n] = 1;    //去掉这个素数的所有2以上的倍数
        }
    }
}
/* 计算任意两个素数相加的值, 这些值在计算SUM的时候是要去掉的 */
void pluseachprime(int maxnum)
{
    //sum_cancel清零
    memset(sum_cancel, 0, sizeof(int)*(MAX_NUMBER*2+1));
    for(int prime1=2; prime1<maxnum; prime1++)
    {
        if(0 == prime_flag[prime1])
        {
            for(int prime2=2; prime2<maxnum; prime2++)
            {
                if(0 == prime_flag[prime2])
                    sum_cancel[prime1+prime2] = 1;  //1表示是要去掉的SUM
            }
        }
    }
}/* 计算sum可分解为sum=i+j的个数和序列 */
int checksum(int sum, sum_type *sumlist)
{
    int scount=0;
    int i,j;    //sumlist清零
    memset(sumlist, 0, sizeof(sum_type)*MAX_SUM_LIST);    for(i=2; i<=sum/2; i++)
    {
        j=sum-i;
        if(j <= MAX_NUMBER)
        {
            sumlist->i=i;
            sumlist->j=j;
            sumlist++;
            scount++;
        }
    }    return(scount);
}/* 计算sum可分解为sum=i+j的个数和序列 */
int checksum_length(int sum)
{
    int scount=0;
    int i,j;    for(i=2; i<=sum/2; i++)
    {
        j=sum-i;
        //如果i,j都是素数则跳过不计
        if(0 == prime_flag[i] && 0 == prime_flag[j])
            break;
        if(i <= MAX_NUMBER && j <= MAX_NUMBER)
        {
            scount++;
        }
    }    return(scount);
}/* 计算product=i*j的分解方法的个数 */
int checkproduct(int i, int j)
{
    int product;
    int pcount=0, pvalid=0;
    int multi;
    int faciend;
    int sum;
    bool bCut = false;    //如果i,j都是素数则必然只能有一种积的分解
    if(0 == prime_flag[i] && 0 == prime_flag[j])
        return(1);    product = i*j;    if(0 == product_count[product])     //product是否已经计算过?如是，则不必重复计算
    {
        for(multi=2; multi<=sqrt(product); multi++)
        {
            if(multi > MAX_NUMBER) break;
            if(0 == (product % multi))  //product是否可以整除multi?
            {
                faciend = product / multi;  //被乘数
                if(faciend <= MAX_NUMBER)
                {
                    sum = multi + faciend;      //乘数和被乘数之和
                    if(sum <= MAX_NUMBER*2)
                    {
                        pcount++;
                        if(0 == sum_cancel[sum])
                        {
                            int sumlength = checksum_length(sum);
                            if(sumlength > 1)
                                pvalid++;
                        }
                    }
                }
            }
        }
        ///*
        if(pvalid == 1 && pcount > 1)
            pcount = 2;
        else
            pcount = 1;
        //*/
        //pcount = pvalid;
        product_count[product] = pcount;
    }
    else
        pcount = product_count[product];
    
    return(pcount);
}int main(int argc, char* argv[])
{
    int sum;
    int length;
    int products;
    int i,j;
    int total=0;
    bool bIsOK;
    int bCount=0;
    sum_type sumlist[MAX_SUM_LIST];    //product_count清零
    memset(product_count, 0, sizeof(int)*MAX_NUMBER*MAX_NUMBER);    //product_flag,sum_flag清零
    memset(product_flag, 0, sizeof(int)*MAX_NUMBER*MAX_NUMBER);
    memset(sum_flag, 0, sizeof(int)*(MAX_NUMBER*2+1));    //找出2-MAX_PRIME_NUM的素数序列
    findprime(MAX_PRIME_NUM);    //计算任意两个素数相加的值, 这些值在计算SUM的时候是要去掉的
    pluseachprime(MAX_PRIME_NUM);    //搜索和为4-198的i,j值
    for(sum=4; sum<=198; sum++)
    {
        //排除等于两个素数之和的sum
        if(0 == sum_cancel[sum])
        {
            sum_type *plist = sumlist;
            bIsOK = true;
            bCount = 0;
            if((length = checksum(sum, plist)) > 1) //sum的分解可能性要大于1，否则S就知道了
            {
                for(int index=0; index<length; index++)
                {
                    i = sumlist[index].i;
                    j = sumlist[index].j;
                    //product的分解可能性也要大于1,否则P也就知道了
                    if((products = checkproduct(i, j)) > 1)
                    {
                        bCount++;
                        product_flag[i*j]++;
                        sum_flag[i+j]++;
                        //printf("i=%d, j=%d,\t sum=%d, product=%d.\n",
                        //  i, j, i+j, i*j);
                        /*
                        if(total % 200 == 199)
                        {
                            printf("press Enter to continue...\n");
                            char s[1];
                            gets(s);
                        }
                        //*/
                        //total++;
                    }
                    else
                        bIsOK = false;
                }
                if(!bIsOK && bCount==1)
                {
                    //printf("sum = %d,\n", sum);
                    for(index=0; index<length; index++)
                    {
                        i = sumlist[index].i;
                        j = sumlist[index].j;
                        //product的分解可能性也要大于1,否则P也就知道了
                        if((products = checkproduct(i, j)) > 1)
                        {
                            printf("i=%d,\t j=%d,\t sum=%d,\t product=%d.\n",
                                i, j, i+j, i*j);
                            total++;
                        }
                    }
                }
            }
        }
    }
    int repeats=0;
    for(int n=4; n<=MAX_NUMBER*MAX_NUMBER; n++)
    {
        if(product_flag[n] > 1)
        {
            //printf("product = %d.\n", n);
            repeats++;
        }
    }
    printf("\ntotal = %d.\n", total);
    return 0;
}

Answer 32

我在www.vckbase.com/bbs给出了这个题目及配偶题的解答，答案分别是(4,13)(69,96)// deduce.cpp : Defines the entry point for the console application.
// by 罗恩(rone) 2003-6-23#include "stdafx.h"
#define __COMMENT1__
#ifdef __COMMENT1__
/*原题目
1）两个数i和j，1＜i,j＜100
2）两个很聪明的人，分别称为S先生和P先生
3）S先生和P先生均不知道i和j究竟是什么。S先生只知道二者的和，P先生只知道i二者的积。
4）S先生和P先生相遇。有下面一段对话：
　　S先生：“我不知道这两个数是多少，我只知道二者的和，但我确信你也不知道。”
　　P先生：“我原来只知道二者的积，但听你这么一说，我现在知道i和j分别是多少了。”
　　S先生：“我现在也知道了”
　　
　　请提供一个思路或写一个程序解出这个问题（i,j的值）。
*/
#else
/*反题目
1）两个数i和j，1＜i,j＜100
2）两个很聪明的人，分别称为S先生和P先生
3）S先生和P先生均不知道i和j究竟是什么。S先生只知道二者的和，P先生只知道i二者的积。
4）S先生和P先生相遇。有下面一段对话：
　　P先生：“我不知道这两个数是多少，我只知道二者的积，但我确信你也不知道。”
　　S先生：“我原来只知道二者的和，但听你这么一说，我现在知道i和j分别是多少了。”
　　P先生：“我现在也知道了”
　　
　　请提供一个思路或写一个程序解出这个问题（i,j的值）。
*/
#endif
bool between(int m)
{
    return m>1 && m<100;
}
bool rule1(int m,int n)//S不知道条件
{
    int sum = m+n;
    return (sum >4 && sum < 198);
}bool rule2(int m,int n)//P不知道条件
{
    int product = m* n;
    int i,count =0;
    for(i =2 ; i< 100; i++)
    {
        if(i * i > product )
        {
            break;
        }
        if((product %i) != 0)
        {
            continue;
        }        if(!between(product /i))
        {
            continue;
        }
        count ++;
    }
    return count >1;
}
bool rule3(int m,int n)//S知道“P不知道”的条件
{
    int sum = m+ n;
    int i;
    int count = 0;
    for(i =2; i< 100 ; i++)
    {
        if(!between(sum -i))
        {
            continue;
        }
        if(!rule2(i,sum-i))
        {
            return false;
        }
    }
    return true;
}bool rule4(int m,int n)//P所知道的积中，满足上述三条件的只有一组
{
    int product = m*n;
    int i;
    int count = 0;
    for(i =2 ; i< 100 ; i++)
    {
        if( i* i > product )
        {
            break;
        }
        if((product % i)!= 0)
        {
            continue;
        }
        if(!between(product /i) )
        {
            continue;
        }
        if(rule1(i,product/i) && rule2(i,product/i) && rule3(i,product/i))
        {
            count ++;
        }
    }
    return count ==1;
}bool rule5(int m,int n)//S知道的和分解中，只有一种满足上述4各条件
{
    int sum = m+n;
    int i,count = 0;
    for( i =2 ; i < 100 ; i++)
    {
        if(i +i > sum)
        {
            break;
        }        if(!between(sum-i))
        {
            continue;
        }
        if(rule1(i,sum-i) && rule2(i,sum-i) && rule3(i,sum-i)&&rule4(i,sum-i))
        {
            count ++;
        }
    }
    return count ==1;
}
bool rule6(int m,int n)//P知道S肯定不知道的条件
{
    int product;
    product = m*n;
    int i;
    for(i=2; i <100 && i*i < product ; i++)
    {
        if((product %i ) != 0)
        {
            continue;
        }
        if(!between(product))
        {
            continue;
        }
        if(!rule1(i,product/i))
        {
            return false;
        }
    }
    return true;
}
bool rule7(int m,int n)
{//有条件2和条件6只能有一种满足
    int sum = m+n;
    int i;
    int count =0;
    for(i=2; i < 100 && i +i <  sum; i++)
    {
        if(!between(sum -i))
        {
            continue;
        }
        if(rule2(i,sum-i) && rule6(i,sum-i))
        {
            count ++;
        }
    }
    return count ==1;
}
int rule8(int m,int n)
{
    int product = m* n;
    int i;
    int count;
    count =0;
    for(i=2 ; i< 100 && i*i< product;i++)
    {
        if((product %i )!=0)
        {
            continue;
        }
        if(!between(product/i))
        {
            continue;
        }
        if(rule2(i,product/i) && rule6(i,product/i) && rule7(i,product/i))
        {
            count ++;
        }
    }
    return count ==1;
}
#include <iostream.h>int main(int argc, char* argv[])
{
    int m,n;
    for(m=2 ; m< 100 ; m++)
    {
        for(n =m ; n< 100 ; n++)
        {#ifdef __COMMENT1__
            if(!rule1(m,n))
            {
                continue;
            }
            if(!rule2(m,n))
            {
                continue;
            }
            if(!rule3(m,n))
            {
                continue;
            }
            if(rule4(m,n)&& rule5(m,n))
            {
                cout<<"m="<<m<<",n="<<n<<endl;
            }
#else
            if(!rule2(m,n))
            {//P知道结果
                continue;
            }
            if(!rule6(m,n))
            {
                //P不知道S肯定不知道
                continue;
            }
            if(!rule7(m,n))
            {//S还是不知道
                continue;
            }
            if(rule8(m,n))
            {
                cout<<"m="<<m<<",n="<<n<<endl;
            }
#endif
        }
    }
return 0;
}