第二次程序设计与方法优化作业

作者：A.y.

日期：2019/3/23

上机环境：Visual C++ 6.0

一、问题描述：
(1)求N个数的最大公约数和最小公倍数。
(2)设某未知正整数x满足:x和a0的最大公约数是a1;x和b0的最小公倍数是b1;求出满足条件的正整数x的个数。

二、算法设计思路：
定义一个整型数组用来存放这N个数;
display1()函数中将N个数中最小的数赋值给temp,判断是否每个数除以temp的余数都为0,若是,则temp为最大公约数,否则temp–,再进行上述判断,直至temp=1;
display2()函数将N个数中最大的数赋值给temp,判断是否temp除以每个数的余数都为0,若是,则temp为最小公倍数,否则temp++,再进行上述判断。
judgement1()和judgement2()函数分别用来求两数的最大公约数和最小公倍数,CountNumber()函数中定义变量number用来表示符合条件的x的个数，将x的初始值赋为a1,分别使用judgement1()函数和judgement2()函数判断x与a0的最大公约数和b0的最小公倍数是否为a1,b1,若是,则number++,然后x++再进行上述判断,否则直接x++再进行上述判断,执行上述操作直至x=b1;number的值即为满足条件的x的个数。

算法设计流程图：
1.基本要求：
第二次程序设计与方法优化作业
2.提高要求：

三、代码实现：

#include<stdio.h>
#define MAX 100
int n,m;
void display1(int  a[])                           /*求N个数的最大公约数*/
{
	int i,j,temp,symbol;                          /*symbol用来判断是否每个数与temp的余都为0*/
	temp=a[0];
	for(i=0;i<n;i++)
		if(temp>a[i])
			temp=a[i];
	for(i=temp;i>0;i--)
	{
		symbol=n;
		for(j=0;j<n;j++)
		{
			if(a[j]%i==0)
				symbol--;
			if(symbol==0)
			{
				printf("\n\t最大公约数为:%d\n",i);
				return;
			}
		}
	}
}
void display2(int a[])                            /*求N个数的最小公倍数*/
{
	int i,j,temp,symbol;
	temp=a[0];
	for(i=0;i<n;i++)
		if(temp<a[i])
			temp=a[i];
	symbol=n;
	while(symbol!=0)
	{
		for(j=0;j<n;j++)
		{
			if(temp%a[j]==0)
				symbol--;
		}
		if(symbol==0)
		{
			printf("\n\t最小公倍数为:%d\n",temp);
			return;
		}
		temp++;
		symbol=n;
	}
}
int judgement1(int a,int b)                  /*计算最大公约数*/
{
	int temp;
	if(a<b)
	{
		temp=a;
		a=b;
		b=temp;
	}
	for(temp=b;temp>0;temp--)                     /*利用穷举法计算最大公约数*/
	{
		if(a%temp==0&&b%temp==0)
			return temp;
	}
	return (1);
}
int judgement2(int a,int b)                       /*计算最小公倍数*/
{
	int i=1;
	if(a>b)                                       /*利用穷举法计算最小公倍数*/
	{
		while(i*a%b!=0)
			i++;
		return a*i;
	}
	else
	{
		while(i*b%a!=0)
			i++;
		return b*i;
	}
}
void CountNumber(int b[MAX][4])                   /*计算符合条件的x的个数*/
{
	int x,number;
	int i,j;
	for(i=0;i<m;i++)
	{
		number=0;
		for(x=b[i][1];x<=b[i][3];x++)
		{
			j=x;
			if((b[i][1]==judgement1(b[i][0],j))&&(b[i][3]==judgement2(b[i][2],j)))
				number++;
		}
		printf("\n%d\n",number);
	}
}
			
int main()
{
	int a[MAX];                                   /*数组a[]存储N个判断的数*/
	int b[MAX][4];                                /*数组b[][]存储进行判断的m组数据*/
	printf("\n\t请输入整数个数:");
	scanf("%d",&n);
	printf("\n\t请输入整数:");
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	display1(a);
	display2(a);
	printf("\n请输入判断组数:");
	scanf("%d",&m);
	printf("\n请输入每组数据:");
	for(i=0;i<m;i++)
	{
		for(int j=0;j<4;j++)
			scanf("%d",&b[i][j]);
	}
	CountNumber(b);
	return 0;
}

四、调试截图：
第二次程序设计与方法优化作业

第二次程序设计与方法优化作业
五、测试截图：
display1()函数
代码截图:

运行截图：

display2()函数:
代码截图:

运行截图：

CountNumber()函数:
代码截图:

运行截图：

六、源代码运行截图：

个人总结
对于算法的逻辑思路有了更清晰的认知，对于解决问题的基本方法在脑子里有了更深刻的概念，在解决这个问题的时候x的取值范围是我遇到最大问题，最后还是在仔细看了一遍问题描述的时候我才找到的办法。

第二次程序设计与方法优化作业

相关推荐