积和猜数.cpp

这个包里收藏很多好玩的算法

/////////////////////////////////////////////
//----------foryou.cpp---------------------//
/////////////////////////////////////////////
//设有两个自然数a,b，2〈a,b<=99。A先生知道这两数的和，B先
//生知道这两数的积。
//他们两人进行了如下的对话：
//  A：我知道你不知道这两个数是什么，但我也不知道。
//  B：现在我知道这两个数了。
//  A：现在我也知道这两个数了。
//由这些条件，试确定a，b。
//-------------------------------------------
/***********************************************
分析：
B从A的话中的到的重要信息：
1.a+b不能表示为两个素数之和。
2.a,b之间没有大于50的素数判断。

***********************************************/

#include <fstream.h>
#include <math.h>
//--------------------------------------------
//判断一个素数，若是素数，返回1。
int Prime(int n)
{int i;
for(i=2;i<=sqrt(n);i++)
if (n%i==0)
return 0 ;
  //cout <<n<< "  IS PRIME NUMBER "<<endl;
return 1;
}
//---------------------------------------------


//---------------------------------------------
//判断一个数能否表示为两个100以内的素数之和，若能，返回1。
int PrimeSum(int x)
{
if(x<5) return 0;
if(x>200) return 0;
if(x>6&&x%2==0) return 1; //根据歌德巴赫猜想，
//偶数是可以表示为两个素数之和的。
int i,j;
for(i=2; i<=x/2;i++)
{j=x-i;
if(j>=100) continue;
if(Prime(i)&&Prime(j)) return 1;
}
return 0;
}
//----------------------------------------------

//----------------------------------------------
//B根据条件a+b不能表示为两个素数之和，a,b之间没有大于50的素数判断。
//如果排除了其他组合，则返回1。
//B是知道积的人
int B(int a,int b)
{ int sum,p;
sum=a+b;
if(Prime(a)&&Prime(b)) return 1;  //若a,b都为素数，返回1。
if(Prime(a)&&a>50) return 1;  //若a>50且为素数，返回1。
if(Prime(b)&&b>50) return 1;
if (PrimeSum(sum)) return 0;
int i,m;
m=a*b;
for(i=2;i<=m/2;i++)
if(i!=a&&i!=b&&m%i==0)
{p=i+m/i;
if(!PrimeSum(p)) return 0;
  }
return 1;
}
//----------------------------------------------
//如果A根据B(a,b)=1排除了其他组合，返回1。
//A是知道和的人。
int A(int a,int b)
{ int i,n;
n=a+b;
for(i=2;i<=n/2;i++)
if(i!=a&&i!=b)
if(B(i,n-i)) return 0; 
return 1;
}
//-----------------------------------------------
void main()
{
ofstream fout("youknow.txt");  //输出文件。
int a,b;
for(a=2;a<=100;a++)    //不妨设b>=a
for(b=a;b<=100;b++)
{ if(Prime(a)&&a>50)  continue;
if(Prime(b)&&b>50)  continue;  //a,b之中不能有大于50的素数
if(Prime(a)&&Prime(b)) continue; //a,b不能都是素数。
if (PrimeSum(a+b)) continue;  //a+b不能是两个素数之和。
if(B(a,b))  //如果B能判断，则给A判断。
{
if(A(a,b))
{
cout <<" 正确答案:  ";
cout <<" a="<<a<<"  "<<"b="<<b<<endl;
cout <<" -----------------------------------"<<endl;
}
}
else continue;

}

fout.close();
}