附录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]); }  

评论