附录2：
根据算法（二）写出的程序代码：
/* S、P先生数学谜题*/
/*梁见斌 2005-11-14*/
#include <stdio.h>
#include <stdlib.h>
#define M 2
#define N 99
//初步列出所有可能的p的值（M*M〈= p〈= N*N），并把每一个p的xy组合的个数作为p[i]的值
void possible1_p(int *p);
//根据p的不可能的值的集合 进一步确定 s的不可能的值的集合 ，即设该元素值为s[x+y] = 1;
void possible_us(int *s, int p[]);
//根据s的不可能的值的集合，推出s的可能的值的集合
int possible2_s(int *s);
//根据p的不可能的值的集合，推出p的可能的值的集合
int possible2_p(int *p);
//根据P的话判断出p[]的可能的值的集合
int possible3_p(int *p, int s[], int len_p, int len_s);
//根据S的话判断出s[]的可能的值的集合
int possible3_s(int *s, int p[], int len_s, int len_p);
//根据P和S的可能的值的集合，判断出X，Y的可能的值的集合
int possible_xy(int p[], int s[], int len_s, int len_p, int *px, int *py);
//输出最后的结果
void print(int x[], int y[], int len);
int main( void )
{
int len_s=0, len_p=0, len_xy;
int s[N+N+1]={0}, p[N*N+1]={0}, *ps, *pp;
int x[N]={0}, y[N]={0}, *px, *py;
ps = s;
pp = p;
px = x;
py = y;
possible1_p(pp);//初步列出所有可能的p的值
possible_us(ps, p);//根据p的不可能的值的集合 进一步确定 s的不可能的值的集合
len_s = possible2_s(ps);//根据s的不可能的值的集合，推出s的可能的值的集合
len_p = possible2_p(pp);//根据p的不可能的值的集合，推出p的可能的值的集合
len_p = possible3_p(pp, s, len_p, len_s);//根据P的话判断出p[]的可能的值的集合
len_s = possible3_s(ps, p, len_s, len_p);//根据S的话判断出s[]的可能的值的集合
//根据P和S的可能的值的集合，判断出X，Y的可能的值的集合
len_xy = possible_xy(p, s, len_s, len_p, px, py);
print(x, y, len_xy);//输出最后的结果
system("pause");
return 0;
}
// 寻找p的可能的值的集合，并把构成其值的可能组合的个数作为数组p[]的元素的值
void possible1_p(int *p)
{
int i, x, y;
for(i=M*M; i<=N*N; i++) //穷举p所有的可能值，把构成其值的可能组合的个数存入数组p[]
for(x=M; x<=N; x++) // M<=X<=Y<=N ，X*Y=P
{
y = i/x;
if(y>=M && y<=N && y>=x && x*y==i)
p[i]++;;
if(p[i] > 1) //为节省时间，当p[i] > 1时即可跳出循环，分析下一个数
break;
}
}
//根据p的不可能的值的集合进一步确定 s的不可能的值的集合
void possible_us(int *s, int p[])
{
int i, x, y;
for(i=M*M; i<=N*N; i++) //穷举s所有的可能值，把构成其值的可能组合的个数存入数组s[]
{
if(p[i] == 1) //若构成p[i]的组合是唯一的，则该p不可能，即构成p[i]的两个数被排除
{
for(x=M; x<=N; x++) // M<=X<=Y<=N ，X*Y=P
{
y = i/x;
if(y>=M && y<=N && y>=x && x*y==i)
s[x+y] = 1;//被排除的两个数所构成的s[x+y]元素也被排除
}
}
}
}
//根据s的不可能的值的集合进一步确定 s的可能的值的集合
int possible2_s(int *s)
{
int i, k=0, add[N+N]={0};
for(i=M+M; i<=N+N; i++) //穷举s所有的可能值，数组元素表示构成其值的xy可能组合的个数
{
if(s[i] != 1) //若构成s[i]的组合不是唯一的，则该s是可能的，把它归入add[k]
add[k++] = i;
}
for(i=0; i<k; i++)//把add[k]复制到s[i]，得到新的数组s[i]
s[i] = add[i]; //注意此时s[i]中元素的值不再表示构成其值的xy可能组合的个数
return k; //而是表示一个可能的和
}
//根据p不可能的值的集合，推出p的可能的值的集合
int possible2_p(int *p)
{
int i, k=0, mul[N*N]={0};
for(i=M*M; i<=N*N; i++) //穷举p所有的可能值，数组元素表示构成其值的xy可能组合的个数
{
if(p[i] != 1 && p[i] != 0) //若构成p[i]的组合不是唯一的，则该p是可能的，把它归入 mul[k]
mul[k++] = i;
}
for(i=0; i<k; i++) //把mul[k]复制到p[i]，得到新的数组p[i]
p[i] = mul[i]; //注意此时p[i]中元素的值不再表示构成其值的xy可能组合的个数
return k; //而是表示一个可能的积
}
//根据P的话判断出p[]的可能的值的集合
int possible3_p(int *p, int s[], int len_p, int len_s)
{
int i, j, x, y;
int k=0, sum=0, mul[N*N]={0};
for(i=0; i<len_p; i++)
{
sum=0;
for(x=M; x<=N; x++) // M<=X<=Y<=N ，X*Y=P
{
y = p[i] / x;
if(y>=M && y<=N && y>=x && x*y==p[i])
for(j=0; j<len_s; j++)
if(x+y == s[j])
sum++; //累积满足x*y==p[i]的xy的组合在s中出现（即同时满足x+y == s[j]）的次数
}
if(sum == 1) //若只出现一次，则该xy组合为正确答案之一 ，所以P先生率先知道了答案
mul[k++] = p[i]; //把对应的x*y==p[i]存入数组mul[k]
}
for(i=0; i<k; i++) //把mul[k]复制到p[i]，得到新的数组p[i]
p[i] = mul[i]; //注意，S先生很聪明，当P先生说知道答案后，S先生也推出了数组p[i]
return k;
}
//根据S的话判断出s[]的可能的值的集合
int possible3_s(int *s, int p[], int len_s, int len_p)
{
int i, j, x, y;
int k=0, sum=0, add[N+N]={0};
for(i=0; i<len_s; i++)
{
sum=0;
for(x=M; x<=N; x++) // M<=X<=Y<=N ，X*Y=P
{
y = s[i] - x;
if(y>=M && y<=N && y>=x)
for(j=0; j<len_p; j++)
if(x*y == p[j])
sum++; //累积满足x+y==s[i]的xy的组合在p中出现（即同时满足x*y == p[j]）的次数
}
if(sum == 1) //若只出现一次，则该xy组合为正确答案之一 ，所以S先生也知道了答案
add[k++] = s[i];//把对应的x+y==s[i]存入数组add[k]
}
for(i=0; i<k; i++) //把add[k]复制到s[i]，得到新的数组s[i]
s[i] = add[i];
return k;
}
//根据P和S的可能的值的集合，判断出X，Y的可能的值的集合
int possible_xy(int p[], int s[], int len_s, int len_p, int *px, int *py)
{
int x, y, i, j, k=0;
for(i=0; i<len_s; i++) //遍历s[]
{
for(x=M; x<=s[i]; x++)
{
y = s[i] - x;
if(y>=M && y<=N && y>=x)
for(j=0; j<len_p; j++) //遍历p[]
if(x*y == p[j])
{
px[k] = x; //解不定方程x+y = s
py[k] = y; // x*y = p
k++;
}
}
}
return k;
}
//输出最后的结果
void print(int x[], int y[], int len)
{
int i;
if(len == 0)
printf("No answer !!\n");
else
for(i=0; i<len; i++)
printf("number %d : x=%d, y=%d\n", i+1, x[i], y[i]);
}
评论