附录1： 根据算法（一）写出的程序代码： /* S、P先生数学谜题*/ /*梁见斌   2005-11-14*/ #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分解的两个数之和是否属于集合Sint 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;  } }}  

评论