"S/P先生数学谜题"算法分析及源代码

附录1：
根据算法（一）写出的程序代码：
#include <stdio.h>
#include <stdlib.h>
#define M 2
#define N 200

typedef struct{  //存放两个数之和或积的集合
 int x;
 int y;
 int data;
} SP1;
 
int possible_up(SP1 *up); // 寻找p的不可能的值的集合
//根据p的不可能的值的集合 进一步确定 s的不可能的值的集合
int put_us(SP1 *us, SP1 up[], int len_us, int len_up);
int out_s(SP1 us[], SP1 *s, int len);//根据s的不可能的值的集合，推出s的可能的值的集合
int out_p(SP1 up[], SP1 *p, int len); //根据p的不可能的值的集合，推出p的可能的值的集合
int judge1(SP1 *p, SP1 s[], int len_p, int len_s);//根据P的话判断出P的可能的值的集合
int judge_s(int x, int y,  SP1 s[], int len);//判断P分解的两个数之和是否属于集合S
int judge2(SP1 *s, SP1 p[], int len_s, int len_p);//根据S的话判断出S的可能的值的集合
int judge_p(int x, int y, SP1 p[], int len); //判断S分解的两个数之积是否属于集合P
//根据P和S的可能的值的集合，判断出X，Y的可能的值的集合
int possible_xy(SP1 p[], SP1 s[], int len_s, int len_p, int *px, int *py);
void print(int x[], int y[], int len);//输出最后的结果
void print1(FILE *fp, SP1 a[], int len); //输出us或up到文件
void print2(FILE *fp, SP1 a[], int len); //输出us.x,us.y或up.x,up.y到文件                                   
int Is_sushu(int n);//判断 n 是否为素数
void Paixu(SP1 *a, int len);//按从小到大排列

int main( void )
{
  FILE *fp;
  char filename[20]; //存放文件名
    int len_us=0, len_up = 0, len_s = 0, len_p = 0, len_xy = 0;
    SP1 us[N*N]={0}, up[N*N]={0}, *pus, *pup;
  SP1 s[N+N]={0}, p[N*N]={0}, *ps, *pp;
  int x[N] = {0}, y[N] = {0}, *px, *py;
 
  printf("\nEneter a filename: ");
    gets(filename);
    //为指针分配空间
    if ( (fp=fopen(filename,"w")) == NULL)
    {
        fprintf(stderr,"\nError opening file %s .\n",filename);
      exit(1);
    } 
  pus = (SP1 *)malloc(sizeof(SP1));
  if(!pus)
  {
   printf("error");
   return 1;   
  }
  pup = (SP1 *)malloc(sizeof(SP1));
  if(!pup)
  {
   printf("error");
   return 1;   
  }
  ps = (SP1 *)malloc(sizeof(SP1));
  if(!ps)
  {
   printf("error");
   return 1;   
  }
  pp = (SP1 *)malloc(sizeof(SP1));
  if(!pp)
  {
   printf("error");
   return 1;   
  }
  pus = us;   //将指针指向数组
  pup = up;
  ps = s;
  pp = p;
  px = x;
  py = y;
 
  len_up = possible_up(pup); // 寻找p的不可能的值的集合
   
  len_us = put_us(pus, up, len_us, len_up); // 进一步寻找s的不可能的值的集合     
    len_s = out_s(us, ps, len_us);  //推出s的可能的值的集合
    len_p = out_p(up, pp, len_up);  //推出的p可能的值的集合
  
  len_p = judge1(pp, s, len_p, len_s); //根据P的话判断出P的可能的值的集合

  len_s = judge2(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); //输出最后的结果
 
    fclose(fp);
    system("pause");
    return 0;
}

int possible_up(SP1 *up)// 寻找p的不可能的值的集合，并返回其长度
{

 int k=0, p, x, y, flag;
 
 for(p=M*M; p<=N*N; p++)//穷举p所有的可能值，把不可能值存入数组up[]
 {
  flag = 0;
  if(Is_sushu(p)) //若p为素数，直接存入数组up[] 
  {  up[k].x = 1;
   up[k].y = p;
   up[k].data = p; 
   k++;
   continue;
  }
  for(x=M; x<=N; x++) // M<=X<=Y<=N
  {
   y = p / x;
       if(y>=x && x*y==p && y>=M && y<=N)
   { 
    flag++;
    if(flag == 1)//若只有一组x，y的值满足x+y == s，则将其存入数组 up[k]
    {
     up[k].x = x;
     up[k].y = y;
     up[k].data = p; 
     k++;
    }
    else if(flag > 1) //若有多于一组x，y的值满足x+y == s，则将其踢出数组up[k]，并结束对s的分析
    {
     k--;       //将元素 us[k]删除
     break;
    } 
   }
  }
 } 
 Paixu(up, k); //将得到的 up[]排序   
 return k;
}                                                      
//根据p的不可能的值的集合 进一步确定 s的不可能的值的集合，并返回新得到的us的长度
int put_us(SP1 *us, SP1 up[], int len_us, int len_up)
{
 int i;
 
 for(i=0; i<len_up; i++)//遍历up[]，如果组成它的两个数的和在（M+M ，N+N）之间，则将其和归入us[]
 {
  if(up[i].x + up[i].y >= M+M && up[i].x + up[i].y <= N+N)
  { 
   us[len_us].x = up[i].x;
   us[len_us].y = up[i].y;
   us[len_us].data = up[i].x + up[i].y;
   len_us++;
  }
 }
 Paixu(us, len_us); //将新得到的 us[]排序
 return len_us; //返回新得到的us的长度
}
//根据s的不可能的值的集合，推出s的可能的值的集合
int out_s(SP1 us[], SP1 *s, int len)
{
 int i, j=0, flag, k=0;
 
 for(i=M+M; i<=N+N; i++)   //遍历（M+M ，N+N）
 {
  flag = 0;  //因为us是有序排列的,所以只需判断比us[j].data大的数即可,而且j也随之增加,以减少运算量
  for( ; j<len && i>=us[j].data; j++)//j不用每次都从0开始,当j>0时,只需保证i>=us[j].data即可
   if(i == us[j].data) //如果i属于us，则跳出循环，并检验下一个i 
   {
    flag = 1;
    break;
   }
  if(i<us[j].data)//如果i<us[j].data,则j自减一次,以保证i>=us[j].data
   j--;  
  if(!flag) //如果i 不属于us，则将其归入s数组
   s[k++].data = i;
 } 
 return k;
}
//根据p不可能的值的集合，推出p的可能的值的集合
int out_p(SP1 up[], SP1 *p, int len)
{
 int i, j=0, flag, k=0;
 
 for(i=M*M; i<=N*N; i++)  //遍历（M*M ，N*N）
 {
  flag = 0;//因为up是有序排列的,所以只需判断比up[j].data大的数即可,而且j也随之增加,以减少运算量
  for( ; j<len && i>=up[j].data; j++)//j不用每次都从0开始,当j>0时,只需保证i>=up[j].data即可
   if(i == up[j].data) //如果i属于up，则跳出循环 ，并检验下一个i
   {
    flag = 1;
    break;
   }
  if(i<up[j].data) //如果i<up[j].data,则j自减一次,以保证i>=up[j].data
   j--;
  if(!flag) //如果i 不属于up，则将其归入p数组
   p[k++].data = i;
 } 
 return k;
}
//根据P的话判断出P的可能的值的集合
int judge1(SP1 *p, SP1 s[], int len_p, int len_s)
{
 int i, x, y, flag;
 int mx=0, my=0, k=0;
 SP1 mul[N*N]={0};
 
 for(i=0; i<= len_p; i++)//遍历p[i]
 { 
  flag = 0;
  for(x=M; x<=N; x++)
  { 
   y = p[i].data / x;
       if(y>=x && x*y==p[i].data && y>=M && y<=N)
   {
    if(flag == 0) //把第一个满足条件x*y==p[i]的x，y组合记录下来
    {
     mx = x;
     my = y;
    }
    flag += judge_s(x, y, s, len_s);//把满足条件x*y==p[i]的x，y组合放入s中进行判断
    if(flag > 1)                   //看x+y == s[i].data是否成立
     break;
   }
  }
  if(flag == 1) //如果只有唯一的一对x，y组合满足x+y == s[i].data，则将其记录在mul[]中
  {
   mul[k].x = mx;
   mul[k].y = my;
   mul[k].data = mx*my;
   k++;
  }  
 }
 for(i=0; i<k; i++)//把 mul[] 复制 到 p[]中
 {
  p[i].x = mul[i].x;
  p[i].y = mul[i].y;
  p[i].data = mul[i].data;
 }
 return k;
}

int judge_s(int x, int y, SP1 s[], int len)//判断P分解的两个数之和是否属于集合S
{
 int i;
 
 for(i=0; i<len; i++)
  if(x+y == s[i].data)
   return 1;
 return 0;
}
//根据S的话判断出S的可能的值的集合
int judge2(SP1 *s, SP1 p[], int len_s, int len_p)
{
 int i, x, y, flag;
 int mx=0, my=0, k=0;
 SP1 add[N+N]={0};
 
 for(i=0; i<= len_s; i++)//遍历s[i]
 { 
  flag = 0;
  for(x=M; x<=N; x++)
  { 
   y = s[i].data - x;
       if(y>=M && y<=N && y>=x)
   {
    if(flag == 0) //把第一个满足条件x+y==s[i]的x，y组合记录下来
    {
     mx = x;
     my = y;
    }
    flag += judge_p(x, y, p, len_p);//把满足条件x+y==s[i]的x，y组合放入p中进行判断
    if(flag > 1)                    //看x*y==p[i].data是否成立
     break;
   }
  }
  if(flag == 1) //如果只有唯一的一对x，y组合满足x*y==p[i].data，则将其记录在add[]中
  {
   add[k].x = mx;
   add[k].y = my;
   add[k].data = mx+my;
   k++;
  } 
 }
 for(i=0; i<k; i++)
 {
  s[i].x = add[i].x;
  s[i].y = add[i].y;
  s[i].data = add[i].data;
 }
 return k;
}

int judge_p(int x, int y, SP1 p[], int len)//判断S分解的两个数之积是否属于集合P
{
 int i;
 
 for(i=0; i<len; i++)
  if(x*y == p[i].data)
   return 1;
 return 0;
}

void print1(FILE *fp, SP1 a[], int len)
{
 int i;
 for(i=0; i<len; i++)
 {
  fprintf(fp, "%d  ", a[i].data);
      fprintf(stdout, "%d  ", a[i].data);
 } 
}

void print2(FILE *fp, SP1 a[], int len)
{
  int i;
  for(i=0; i<len; i++)
  {
   fprintf(fp, "%d,%d \t", a[i].x, a[i].y);
       fprintf(stdout, "%d,%d \t", a[i].x, a[i].y);
  } 
}

int Is_sushu(int n)//判断 n 是否为素数
{
 int i, flag=1;
 
 for(i=2; i<=n/2; i++)
 {
  if(n%i == 0)
  {
   flag = 0;
   break;
  } 
 }
   return flag;
}

//根据P和S的可能的值的集合，判断出X，Y的可能的值的集合
int possible_xy(SP1 p[], SP1 s[], int len_s, int len_p, int *px, int *py)
{
 int i, j, k=0;
 
 for(i=0; i<len_s; i++)
  for(j=0; j<len_p; j++)
   if(p[j].x + p[j].y == s[i].data)
   {
    px[k] = p[j].x ;
    py[k] = p[j].y ;
    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]);
}

void Paixu(SP1 *a, int len)//按从小到大排列
{
 int i, j, min, temp;
 
 for(i=0; i<len-1; i++)
 {
  min = i;
  for(j=i; j<len; j++)
   if(a[j].data < a[min].data)
    min = j;
  if(i != min)
  {
   temp = a[i].data;
   a[i].data = a[min].data;
   a[min].data = temp;
  }
 }
}

根据算法（二）写出的程序代码：
/* S、P先生数学谜题*/

#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]);

}

责任编辑 webmaster

相关链接