正文

"S、P先生数学谜题"算法分析及源代码(2)2005-11-13 13:54:00

【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/goal00001111/6862.html

分享到：

附录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分解的两个数之和是否属于集合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;
  }
 }
}


 

阅读(2545) | 评论(0)


版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！

评论

暂无评论
您需要登录后才能评论，请 登录 或者 注册