logic_problem.cpp

逻辑问题

*****************************************************************************************
//一道QQ上的题目							    *
//												*
//两个人A，B，数字为2～100之间的共99个自然数。	*
//现找出两个数，把其和告诉A，把其积告诉B。然后	*
//问A知道不知道是哪两个数，A说：“虽然我不知道	*
//，但是肯定B也不知道。”再问B，B说：“本来我	*
//不知道，但是听到A说这句话，现在我知道了。”	*
//A听到B说他知道了，然后就说：“现在我也知道了	*
//”。那么这两个数是多少呢？					*
//                                              *
//----------------------------------------------*
//算法步骤:
//1.找出所有A和B都不能肯定的数，并建立一个列表
//2.从上述数表每次取出一个数c,把它进行加法拆分(a[1]+b[1],a[2]+b[2],...,a[n]+b[n])
//3.取遍每一组拆分，把每组拆分进行如下操作：
//  3-1.把a[i]与b[i]相乘，并将结果进行乘法拆分
//  3-2.把每组拆分结果分别相加
//  3-3.在列表中查看相加结果是否存在,若存在，记w为1，否则记为0
//  3-4.统计a[i]与b[i]这组分拆中w为1的次数
//4.若数c的加法分拆中只有一组a[i0]与b[i0]的w为1的次数(analysis)为1，
//  则可确定所求的两个数就是a[i0]与b[i0]
//
//作者：Henry King & 死神
//******************************************************************************************

#include <iostream>
#include <cmath>

using namespace std;

int prime[25]={2,3,5,7,11,13,17,19,
	23,29,31,37,41,43,47,
	53,59,61,67,71,73,79,
	83,89,97};										//2～100的质数
int a,b;											//最终所求的结果
int M[199];											//所有A和B都不能肯定的数（未筛选）
int m;												//用于筛选数表的变量
int i=0,j=0;										//计数变量
int c[84];											//重新排序好的数表
int sum_s[50][2];									//存放分拆的数组
int x;												//暂存数表变量
int y,z;											//暂存加法拆分变量
int sum;											//乘法拆分相加结果
int temp,w,analysis;
void func1(int&, int&);							    //查询函数 
void func2(int&, int&, int&);						//乘法分拆函数	

int main()
{
	for(i=0; i<=198; i++)
	{
		M[i]=i+1;									//建立1~199的数表
	}
	for(i=0; i<=24; i++)
	{
		for(j=i+1; j<=24; j++)
		{
			m=prime[i]+prime[j];
			M[m-1]=0;
		}
		m=prime[i]*(prime[i]+1);
		if(m<=198) M[m-1]=0;		   			    //找出A与B均不能肯定的数
	}
	cout << "A与B均不能肯定的数如下:\n";
	j=0;
	for(i=0; i<=198; i++)
		if(M[i]>5)
		{
			cout << M[i] <<" ";
			c[j]=M[i];
			j++;
		}										    //重新排序好的数表
	cout << "\n所求结果是:";
	for(j=0; j<=83; j++)
	{
		analysis=0;
		x=c[j];										//读取数表中的一个数
		temp=x/2-2;
		for(i=0; i<=temp; i++)
		{
			sum_s[i][0]=i+2;
			sum_s[i][1]=x-(i+2);
			y=sum_s[i][0];
			z=sum_s[i][1];							//加法拆分
			func2(y, z, w);							//乘法拆分+查询数表
			analysis+=w;							//统计w为1的次数
		}
		if(analysis==1) 
			cout <<	'\n' << a << " and " 
			     << b << '\n';		                //输出结果
	}
	return 0;
}

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

void func1(int& x,int& w)
{
	int y=0;
	for(int i=0; i<=83; i++)
	{
		if(x==c[i]) y++;							//与数表对比
		else continue;
	}
	w+=y;
}

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

void func2(int& x, int& y, int& w)
{
	int product,temp;
	product=x*y;
	temp=sqrt(product);
	for(int i=2; i<=temp; i++)
	{
		if(product%i==0)
		{
			if(i!=product/i)
			sum=i+product/i;					   //乘法拆分并将结果相加
			func1(sum,w);
		}
		else continue;
	}
	if(w>=2) w=0;
	else 
	{
		a=x; 
		b=y;
	}

}

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