求N个数的最大公约数和最小公倍数及Hankson的“逆问题”（C语言）

一．题目要求
基本要求：求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。
1.程序风格良好(使用自定义注释模板)
2.提供友好的输入输出，并进行输入数据的正确性验证。
提高要求：
Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x满足：
1、 x和a0的最大公约数是a1；
2、 x和b0的最小公倍数是b1。
Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。
输入格式
输入第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。
输出格式
输出共n行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的x，请输出0；
若存在这样的x，请输出满足条件的x的个数；
样例输入
2
41 1 96 288
95 1 37 1776
样例输出
6
2
二．题目分析（流程图）
1.基本要求：
求N个数的最大公约数和最小公倍数及Hankson的“逆问题”（C语言）
main()函数
divisor ()函数
2.提高要求

main()函数

Count()函数
三．算法实现
1.基本要求

/*利用for循环调用 divisor()和multiple()函数求出N个数的最大公约数与最小公倍数*/    
#include <stdio.h>
#include <stdlib.h>
int divisor (int a,int b)    /*自定义函数求两数的最大公约数*/
{
  int  temp;          /*定义整型变量*/
  if(a<b)             /*通过比较求出两个数中的最大值和最小值*/
    { temp=a;a=b;b=temp;} /*设置中间变量进行两数交换*/
   while(b!=0)           /*通过循环求两数的余数，直到余数为0*/
    {
      temp=a%b;
      a=b;              /*变量数值交换*/
      b=temp;
    }
  return (a);            /*返回最大公约数到调用函数处*/ 
}
int multiple (int a,int b)  /*自定义函数求两数的最小公倍数*/
{
  int divisor (int a,int b); /*自定义函数返回值类型*/
  int temp;
  temp=divisor(a,b);  /*再次调用自定义函数，求出最大公约数*/
  return  (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/
}

int main(void)  
{
	int N,i,t1,t2;
	int *p;
	printf("请您输入数据的个数：\n");
	scanf("%d",&N);
	printf("请输入%d个数：\n",N);
	p=(int *)malloc(N*sizeof(int));
	for(i=0;i<N;i++)
	{
		scanf("%d",p+i); 
	}
	t1=t2=*p; 
	for(i=0;i<N-1;i++)
	{
	t1=divisor(t1,*(++p));     
	t2=multiple(t2,*p);              
	}
	printf("The higest common divisor is %d\n",t1);  
	printf("The lowest common multiple is %d\n", t2);
	free(p); 
	return 0; 
}

2.提高要求：

/*输入N组数据，每组均为四个正整数a0，a1，b0，b1其中应满足(a0%a1==0)&&(b1%b0==0)，
x的值满足:
1. a1=gcd(x,a0)
2. b1=multiple(x,b0);
3. a1<x<b1.
利用for循环遍历出符合要求的x，令cnt++；输出cnt的值。  */ 

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
	int a0;
	int a1;
	int b0;
	int b1;
}ElemSN; 
int gcd (int a,int b)                           //求两个数的最大公约数 
{  if(a%b==0)
       return b;   
else  
       return gcd(b,a%b);
}

 int multiple (int a,int b)                  //求两个数的最小公倍数 
{
  int gcd(int a,int b);             
  int temp;
  temp=gcd(a,b);                       
  return (a*b/temp);                
}
int Judge(int a0,int a1,int b0,int b1)
{
	if((a0%a1)||(b1%b0))
	 {
	       printf("输入错误！请重新输入数据：\n");
	       return 1;
	 }
}
int Count(int a0,int a1,int b0,int b1)
{                                   
	 int cnt=0;      
	 for(int x=a1;x<=b1;x++)         //x的取值范围：a1<x<b1
	       if((a1==gcd(x,a0))&&(b1==multiple(x,b0)))
	             {
	                  cnt++;
	             }
    return cnt;
}

int main(void)
{
	int n,i,h=0;
	ElemSN *q; 
	printf("请输入数据的组数：\n");
	scanf("%d",&n);
	q=(ElemSN *)malloc(4*n*sizeof(int));
	printf("请输入数据：\n");
	for(i=0;i<n;i++)
	{
		do{
			scanf("%d%d%d%d",&q[i].a0,&q[i].a1,&q[i].b0,&q[i].b1);
			h=Judge(q[i].a0,q[i].a1,q[i].b0,q[i].b1);
		}while(h);
	}
	printf("--------------------------------\n");
	printf("输入的数据为：\n");
	for(i=0;i<n;i++)
	{ 
       printf("%5d%5d%5d%5d\n",q[i].a0,q[i].a1,q[i].b0,q[i].b1);
	}
	printf("结果为：\n");	
	for(i=0;i<n;i++)
	{
       printf("%d\n",Count(q[i].a0,q[i].a1,q[i].b0,q[i].b1));
	}
	free(q);
	return 0;
}

四．测试及运行结果
1.基本要求：
求N个数的最大公约数和最小公倍数及Hankson的“逆问题”（C语言）

2.提高要求：
（1）输入a0、a1、b0、b1满足要求：

（2）输入第一组数据的a0、a1、b0、b1不满足要求，然后重新输入：

（3）输入第一组数据满足要求，而第二组数据不满足要求，然后重新输入第二组数据，再次验证是否满足要求，然后输出结果：
求N个数的最大公约数和最小公倍数及Hankson的“逆问题”（C语言）
五．经验归纳：
在这次的程序算法设计中，多次运用malloc分配动态存储单元，然后在程序的最后用free（）语句释放存储单元，已熟练掌握malloc的用法，并且malloc（）很适合给这两个程序分配存储单元，不会分配多余的存储单元，节省存储空间。在这次的提高要求中，刚开始没有理解题目意思，无从下手，然后又读了几遍题后，豁然开朗。因此在今后的写题过程中，我会认真读题，理解题意，只有这样才能编写出符合题意的代码。

求N个数的最大公约数和最小公倍数及Hankson的“逆问题”（C语言）

相关推荐