写了个垃圾代码...也发上来吧...
//鬼谷子问徒
//孙膑,庞涓都是鬼谷子的徒弟,一天鬼谷子出了这道题目:他从2到99选出两个不同的整数,把积告诉孙,把和告诉庞.庞说:我虽不能确定这两个数是什么,但是我肯定你也不知道这两个数是什么.孙说:我本来的确不知道,但是听你这么一说,我现在能确定这两个数字了.庞说既然你这么说,我现在也知道这两个数字是什么了.请问这两个数字是什么?为什么?
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
//设此二数为x, y, 和为sum=x+y, 积为prod
const int N=100;
map<int, set<int>> products;
bool IsPrime(int n)
{
for (int i=2; i*i<=n; i++)
if (n%i==0) return 0;
return 1;
}
//sum是否满足命题1: 知道和sum, 对于任意使x+y==sum的x,y, x*y的因数分解(分解为2~99之间的整数之积)方法数>1
bool IsFirst(int sum)
{
int prod,cnt=0;
//将sum分解为x+y, 其中, 2<=x<=sum/2, sum/2<=y<=sum-2,
for (int x=2,y; x<=sum/2; x++)
{
y=sum-x;
if (y >=100) continue;//y显然是<=99
prod=x*y;
//如果x与y均是质数, 显然分解方法只有一个...
if (IsPrime(x)&&IsPrime(y)) return 0;
//计算分解方法数
cnt=0;
for (int t=2; t*t<prod; t++)
if (prod%t==0 &&prod/t<N )
cnt++;
if (cnt<2) return 0;
}
return 1;
}
//根据第一句话, 我们得出了sum及prod的可能值集products
//对于每个sum, 有一个相应的prod集
//同样, 孙也得出了products集合, 但他从此集合中推断出了x,y
//也就是推断出了sum, 而我们推断不出来, 是因为他知道x*y的值prod
//所以, prod在集合products中出现并且只出现一次,所以在products中
//同时属于两个sum的prod值要从相应集合中排除.
void Second()
{
map<int,set<int>>::iterator it=products.begin();
map<int, int> prodCnt;
for (; it!=products.end(); it++)
{
for (set<int>::iterator it_set=it->second.begin();
it_set!=it->second.end(); it_set++)
prodCnt[*it_set]++;
}
for (it=products.begin(); it!=products.end(); it++)
{
for (set<int>::iterator it_set=it->second.begin();
it_set!=it->second.end(); )
{
if (prodCnt[*it_set]>1) it_set=it->second.erase(it_set);
else
it_set++;
}
}
}
//
void Third()
{
map<int,set<int>>::iterator it=products.begin();
for (;it!=products.end(); it++)
if (it->second.size()==1)
{
int sum=it->first, prod=*(it->second.begin()), x=(sum-(int)sqrt(sum*sum-4*prod+0.1))/2;
printf("解为: sum=%d\tprod=%d\n即x=%d\ty=%d\n", sum, prod, x, sum -x);
}
}
void Display()
{
printf("当前的嫌疑解(状态表)为:\n");
puts("和sum的取值: \t乘积prod的取值:");
map<int,set<int>>::iterator it=products.begin();
for (; it!=products.end(); it++)
{
printf("%d:
", it->first);
for(set<int>::iterator it_set=it->second.begin(); it_set!=it->second.end(); it_set++)
printf(" %d", *it_set);
puts("\n");
}
}
int main ()
{
//对sum进行枚举,暴力啊暴力...我喜欢暴力
//和sum取值范围为2+3到98+99 其实sum的上界可以优化到55...
for (int sum=5, cnt=0; sum<=197; sum++)
{
if (IsFirst(sum))
{
for (int i=2; i<=sum/2; i++)
products[sum].insert(i*(sum-i));
}
}
//输出当前解的可能范围:
Display();
//处理第二句话
Second();
//输出当前解的可能范围:
Display();
Third();
return 0;
}
2008-06-12 23:20
