K
kaneboy
Unregistered / Unconfirmed
GUEST, unregistred user!
以下是CSDN的网友写出的程序。
/*************************************************************已知两个数字为1~30的，
甲知道两数只和，
乙知道两数之积，
甲问乙："你知道是那两个数吗？"乙说："不知道"。
乙问甲："你知道是那两个数吗？"甲说："也不知道"。
于是，乙说："那我知道了"
随后甲也说："那我也知道了"
这两个数是什么？
/*************************************************************/
//算法说明：使用排除法，排除那些不可能的和数、积数
#include "stdafx.h"
#include "stdio.h"
#include "math.h"
int main(int argc, char* argv[])
{
int sum[61];//和数表，为0表示被排除了
int prod[901];//积数表，为0表示被排除了
int i,k,m,index;
int prime[]={1,2,3,5,7,11,13,17,19,23,29};//质数,此处包含了1，因为有时要用到1
//初始化和数表
for(i=0;i<61;i++) sum=1;
//初始化积数表
for(i=0;i<901;i++) prod=0;
for(i=30;i>1;i--)
{
for(k=1;k<=i;k++)
{
prod[k*i]=1;
}
}
/************************************************************ 根据：知道两数积的人不知道这两个数，则可以排除以下可能的积
1、两个质数的积(>30)
2、两个大数（>15）的积
3、一个大质数(>15)和一个任意数的积
4、一个质数的三次方(>30)
5、三个质数的积，其中一个质数与其他两个中任意一个的积都大于30
/************************************************************/
// 排除两个质数的积(>30)
for(i=0;i<11;i++)
{
prod[prime]=0;
for(k=0;k<11;k++)
{
index=prime*prime[k];
if(index>30)
prod[index]=0;
}
}
//排除两个大数（>15）的积
for(i=16*16;i<901;i++)
{
prod=0;
}
//排除一个大质数(>15)和一个任意数的积
for(i=7;i<11;i++)
{
for(k=1;k<31;k++)
{
prod[prime*k]=0;
}
}
//排除一个质数的三次方(>30)
for(i=1;i<5;i++)
{
index=prime*prime*prime;
if(index>30)
prod[index]=0;
}
//排除三个质数的积，其中一个质数与其他两个中任意一个的积都大于30
for(i=1;i<11;i++)
{
for(k=1;k<11;k++)
{
for(m=1;m<11;m++)
{
//在这里假设prime为“其中一个质数”
//prime[k]、prime[m]为“其他两个”
if((prime*prime[k]<31)¦¦(prime*prime[m]<31))continue;
index=prime*prime[k]*prime[m];
if(index < 256) prod[index]=0;
}
}
}
/************************************************************ 根据：知道两数和的人不知道这两个数，则可以排除以下可能的和数
1、太大的和数，太小的和数
2、将和分解成任意两个数，他们的积都被排除了
/*************************************************************/
//太大的和数，太小的和数：0，1，2，3，59，60
sum[0]=0;
sum[1]=0;
sum[2]=0;
sum[3]=0;
sum[59]=0;
sum[60]=0;
//
int lim=256;//对匹配数量的限制
//此值太大，导致循环次数过多
//可以为5或更小，不过，小于4时，结果会出现偏差
//取lim值为3时，结果很特别，请朋友们试一下,你知道为什么吗？
//但不可以比3还小
int kp=900;//积数的最多可能性
int ks=60;//和数的最多可能性
int key=2;//确认次数，用于确认积数的可能性、和数的可能性已经相对稳定
while(key>0)//反复利用条件,进行迭代运算
{
//将和分解成任意两个数，他们的积都被排除了,这样的和应该去掉
for(i=1;i<60;i++)
{
if(sum!=1)continue;//先去掉已经被排除了的和数
//将和数分解成两个数：i=k+(i-k)
//用这两个数的积去匹配积
index=i/2;
m=0;//匹配计数器
for(k=1;k<=index;k++)
{
if((i-k<=30)&&(prod[k*(i-k)]==1))//匹配成功
m++;//计数器加1
}
if(m==0) sum=0;//排除那些一次也没有匹配成功的和数
}
//这里要利用“乙知道了”的条件
for(i=1;i<256;i++)//这里用256，是因为>=256的积已经被排除了
{
if(prod!=1)continue;//先去掉已经被排除了的积
//将积分解为两个数i=k(i/k) 这里i%k==0
//用k+i/去匹配和数 （在这里要根据积枚举出所有的和数）
index=(int)sqrt(i);
m=0;//匹配计数器
for(k=1;k<=index;k++)
{
if( (i%k==0) &&
(i/k<=30) &&
(k+i/k<60) &&
(sum[k+i/k]==1))//匹配成功
m++;//计数器加1
}
if(m==0) prod=0;//去掉不可匹配的积
if(m>lim) prod=0;//如果匹配的可能性太多，则不可能“乙知道了”
//
}
//
//这里要利用“甲也知道了”的条件
for(i=1;i<61;i++)
{
if(sum!=1)continue;//先去掉已经被排除了的和数
//将和数分解成两个数：i=k+(i-k)
//用这两个数的积去匹配积
index=i/2;
m=0;//匹配计数器
for(k=1;k<=index;k++)
{
if((i-k<=30)&&(prod[k*(i-k)]==1))//匹配成功
m++;//计数器加1
}
if(m>lim) sum=0;//如果匹配的可能性太多，则不可能“甲也知道了”
else
if(lim==1)
{
if(m!=1)sum=0;
}
}
/*************************************************** 根据和，去掉不可能的积,这里主要取最大和最小两个极限值
/***************************************************/
//限制最大的积
for(i=60;i>=0;i--)
{
if(sum>0)
{
m=i;
break;
}
}
//
m=(m/2)*(m-m/2);
for(i=m+1;i<901;i++)
{
prod=0;
}
//限制最小的积
for(i=1;i<61;i++)
{
if(sum>0)
{
m=i;
break;
}
}
//
m=m-1;
for(i=m-1;i>0;i--)
{
prod=0;
}
//根据现有的和数，组合出所有的积，排除那些不在里面的积
int temp[257];
for(i=0;i<257;i++)temp=0;
for(i=1;i<60;i++)
{
//
if(sum==0)continue;
for(k=i;k>1;k--)
{
m=k*(i-k);
if(m>256)continue;
temp[m]=1;
}
}
for(i=1;i<257;i++)
{
if(temp==0)prod=0;//排除
}
/*************************************************** 根据积，去掉不可能的和,这里主要取最大和最小两个极限值
/***************************************************/
//限制最大的和
for(i=256;i>=0;i--)
{
if(prod>0)
{
m=i;
break;
}
}
if(i*m==0)break;
m=1+m;
if(m<60)
for(i=m+1;i<60;i++)sum=0;
//限制最小的和
for(i=1;i<256;i++)
{
if(prod>0)
{
m=i;
break;
}
}
if(i*m==0)break;
i=(int)sqrt(m);
m=i+m/i;
for(i=m-1;i>0;i--)sum=0;
///////////////////////////////////////////////////////
//判断还有没有循环的意义
k=0;
for(i=1;i<901;i++)
{
if(prod>0)k++;
}
m=0;
for(i=1;i<61;i++)
{
if(sum>0)m++;
}
//
if((kp==k)&&(ks==m)&&(lim<2)) key--;//确认
if(kp*ks==0) break;//再也没有循环的意义，跳出循环
kp=k;ks=m;//下一次确认的条件
if(lim>1)lim--;
///////////////////////////////////////////////////
}
//输出积数
printf("The product:/r/n");
k=0;
for(i=1;i<901;i++)
{
if(prod>0)
{
k++;
printf("%7d",i);
if(k%10==0)printf("/r/n");
}
}
printf("/r/n");
printf("/r/n");
//输出和数
k=0;
printf("The sum:/r/n");
for(i=1;i<61;i++)
{
if(sum>0)
{
k++;
printf("%7d",i);
if(k%10==0)printf("/r/n");
}
}
printf("/r/n");
printf("/r/n");
printf("/r/n");
return 0;
}
/*************************************************************已知两个数字为1~30的，
甲知道两数只和，
乙知道两数之积，
甲问乙："你知道是那两个数吗？"乙说："不知道"。
乙问甲："你知道是那两个数吗？"甲说："也不知道"。
于是，乙说："那我知道了"
随后甲也说："那我也知道了"
这两个数是什么？
/*************************************************************/
//算法说明：使用排除法，排除那些不可能的和数、积数
#include "stdafx.h"
#include "stdio.h"
#include "math.h"
int main(int argc, char* argv[])
{
int sum[61];//和数表，为0表示被排除了
int prod[901];//积数表，为0表示被排除了
int i,k,m,index;
int prime[]={1,2,3,5,7,11,13,17,19,23,29};//质数,此处包含了1，因为有时要用到1
//初始化和数表
for(i=0;i<61;i++) sum=1;
//初始化积数表
for(i=0;i<901;i++) prod=0;
for(i=30;i>1;i--)
{
for(k=1;k<=i;k++)
{
prod[k*i]=1;
}
}
/************************************************************ 根据：知道两数积的人不知道这两个数，则可以排除以下可能的积
1、两个质数的积(>30)
2、两个大数（>15）的积
3、一个大质数(>15)和一个任意数的积
4、一个质数的三次方(>30)
5、三个质数的积，其中一个质数与其他两个中任意一个的积都大于30
/************************************************************/
// 排除两个质数的积(>30)
for(i=0;i<11;i++)
{
prod[prime]=0;
for(k=0;k<11;k++)
{
index=prime*prime[k];
if(index>30)
prod[index]=0;
}
}
//排除两个大数（>15）的积
for(i=16*16;i<901;i++)
{
prod=0;
}
//排除一个大质数(>15)和一个任意数的积
for(i=7;i<11;i++)
{
for(k=1;k<31;k++)
{
prod[prime*k]=0;
}
}
//排除一个质数的三次方(>30)
for(i=1;i<5;i++)
{
index=prime*prime*prime;
if(index>30)
prod[index]=0;
}
//排除三个质数的积，其中一个质数与其他两个中任意一个的积都大于30
for(i=1;i<11;i++)
{
for(k=1;k<11;k++)
{
for(m=1;m<11;m++)
{
//在这里假设prime为“其中一个质数”
//prime[k]、prime[m]为“其他两个”
if((prime*prime[k]<31)¦¦(prime*prime[m]<31))continue;
index=prime*prime[k]*prime[m];
if(index < 256) prod[index]=0;
}
}
}
/************************************************************ 根据：知道两数和的人不知道这两个数，则可以排除以下可能的和数
1、太大的和数，太小的和数
2、将和分解成任意两个数，他们的积都被排除了
/*************************************************************/
//太大的和数，太小的和数：0，1，2，3，59，60
sum[0]=0;
sum[1]=0;
sum[2]=0;
sum[3]=0;
sum[59]=0;
sum[60]=0;
//
int lim=256;//对匹配数量的限制
//此值太大，导致循环次数过多
//可以为5或更小，不过，小于4时，结果会出现偏差
//取lim值为3时，结果很特别，请朋友们试一下,你知道为什么吗？
//但不可以比3还小
int kp=900;//积数的最多可能性
int ks=60;//和数的最多可能性
int key=2;//确认次数，用于确认积数的可能性、和数的可能性已经相对稳定
while(key>0)//反复利用条件,进行迭代运算
{
//将和分解成任意两个数，他们的积都被排除了,这样的和应该去掉
for(i=1;i<60;i++)
{
if(sum!=1)continue;//先去掉已经被排除了的和数
//将和数分解成两个数：i=k+(i-k)
//用这两个数的积去匹配积
index=i/2;
m=0;//匹配计数器
for(k=1;k<=index;k++)
{
if((i-k<=30)&&(prod[k*(i-k)]==1))//匹配成功
m++;//计数器加1
}
if(m==0) sum=0;//排除那些一次也没有匹配成功的和数
}
//这里要利用“乙知道了”的条件
for(i=1;i<256;i++)//这里用256，是因为>=256的积已经被排除了
{
if(prod!=1)continue;//先去掉已经被排除了的积
//将积分解为两个数i=k(i/k) 这里i%k==0
//用k+i/去匹配和数 （在这里要根据积枚举出所有的和数）
index=(int)sqrt(i);
m=0;//匹配计数器
for(k=1;k<=index;k++)
{
if( (i%k==0) &&
(i/k<=30) &&
(k+i/k<60) &&
(sum[k+i/k]==1))//匹配成功
m++;//计数器加1
}
if(m==0) prod=0;//去掉不可匹配的积
if(m>lim) prod=0;//如果匹配的可能性太多，则不可能“乙知道了”
//
}
//
//这里要利用“甲也知道了”的条件
for(i=1;i<61;i++)
{
if(sum!=1)continue;//先去掉已经被排除了的和数
//将和数分解成两个数：i=k+(i-k)
//用这两个数的积去匹配积
index=i/2;
m=0;//匹配计数器
for(k=1;k<=index;k++)
{
if((i-k<=30)&&(prod[k*(i-k)]==1))//匹配成功
m++;//计数器加1
}
if(m>lim) sum=0;//如果匹配的可能性太多，则不可能“甲也知道了”
else
if(lim==1)
{
if(m!=1)sum=0;
}
}
/*************************************************** 根据和，去掉不可能的积,这里主要取最大和最小两个极限值
/***************************************************/
//限制最大的积
for(i=60;i>=0;i--)
{
if(sum>0)
{
m=i;
break;
}
}
//
m=(m/2)*(m-m/2);
for(i=m+1;i<901;i++)
{
prod=0;
}
//限制最小的积
for(i=1;i<61;i++)
{
if(sum>0)
{
m=i;
break;
}
}
//
m=m-1;
for(i=m-1;i>0;i--)
{
prod=0;
}
//根据现有的和数，组合出所有的积，排除那些不在里面的积
int temp[257];
for(i=0;i<257;i++)temp=0;
for(i=1;i<60;i++)
{
//
if(sum==0)continue;
for(k=i;k>1;k--)
{
m=k*(i-k);
if(m>256)continue;
temp[m]=1;
}
}
for(i=1;i<257;i++)
{
if(temp==0)prod=0;//排除
}
/*************************************************** 根据积，去掉不可能的和,这里主要取最大和最小两个极限值
/***************************************************/
//限制最大的和
for(i=256;i>=0;i--)
{
if(prod>0)
{
m=i;
break;
}
}
if(i*m==0)break;
m=1+m;
if(m<60)
for(i=m+1;i<60;i++)sum=0;
//限制最小的和
for(i=1;i<256;i++)
{
if(prod>0)
{
m=i;
break;
}
}
if(i*m==0)break;
i=(int)sqrt(m);
m=i+m/i;
for(i=m-1;i>0;i--)sum=0;
///////////////////////////////////////////////////////
//判断还有没有循环的意义
k=0;
for(i=1;i<901;i++)
{
if(prod>0)k++;
}
m=0;
for(i=1;i<61;i++)
{
if(sum>0)m++;
}
//
if((kp==k)&&(ks==m)&&(lim<2)) key--;//确认
if(kp*ks==0) break;//再也没有循环的意义，跳出循环
kp=k;ks=m;//下一次确认的条件
if(lim>1)lim--;
///////////////////////////////////////////////////
}
//输出积数
printf("The product:/r/n");
k=0;
for(i=1;i<901;i++)
{
if(prod>0)
{
k++;
printf("%7d",i);
if(k%10==0)printf("/r/n");
}
}
printf("/r/n");
printf("/r/n");
//输出和数
k=0;
printf("The sum:/r/n");
for(i=1;i<61;i++)
{
if(sum>0)
{
k++;
printf("%7d",i);
if(k%10==0)printf("/r/n");
}
}
printf("/r/n");
printf("/r/n");
printf("/r/n");
return 0;
}
]