首页 > 代码库 > 华为机试—多个数的最大公约数

华为机试—多个数的最大公约数

题目:求最大公约数

输入一组正整数(数量小于20),输出其最大公约数。

输入:121 33 44 11 1111

输出:11


基本思路:

从第一个数开始,和第二个数比较找它两的最大公约数,然后找出的最大公约数和第三个数比较,依次类推。。。


#include <stdio.h>

int gcd(int a,int b)
{
	return a%b?gcd(b,a%b):b;
}

int main()
{
	int N,a[20],k,i;
	while(~scanf("%d",&N))
	{
		for(i=0;i<N;i++)
			scanf("%d",&a[i]);

		k=a[0];
		for(i=1;i<N;i++)
		{
			k=gcd(k,a[i]);
		}

		printf("%d\n",k);
	}
	return 0;
}


测试结果,可能想的不周全,欢迎查漏补缺:


技术分享




华为机试—多个数的最大公约数