C语言练习——求两个数的最大公约数(三种算法)

给定两个整数,让你求这两个数的最大公约数

最大公约数顾名思义就是:这几个整数共有的约数中最大的一个。

目录

1. 辗转相除法

2.更相减损法

3.穷举法 


1. 辗转相除法

思路:

(1)将两个整数求余数a%b = c;如果c = 0,则b为最大公约数

(2)如果c != 0,则让a = b, b = c,继续执行a%b = c;判断条件为c是否为零

例如:a = 15,b = 18

c = a%b = 15%18 = 15,c = 15,c此时不等于0;

则进行a = b,b = c;a = 18,b = 15;

继续执行c = a%b = 18%15 = 3,此时c=3不为0;

执行a = b, b = c;a = 15,b = 3;

继续进行c = a%b = 15%3 = 0;此时c = 0循环结束。

代码如下:

#include<stdio.h>
int main()
{
	int a, b, c;
	printf("请输入两个整数:");
	scanf("%d%d", &a, &b);
	c = a % b;
	while (c != 0)
	{
		a = b;
		b = c;
		c = a % b;
	}
	printf("最大公约数为:%d", b);
	return 0;
}

2.更相减损法

思路:

(1)如果a = b;则a或b就是最大公约数

(2)如果a != b;若a>b,则a = a-b;若a<b,则b = b-a;一直执行到a = b循环结束

例如:a = 15,b = 18

因为a != b且a<b,则b = a-b = 18-15 = 3,

b = 3,a>b,则a = a-b = 15-3 = 12 ,

a = 12,a>b,则a = a-b =12-3 = 9,

a = 9,a>b,则a = a-b =9-3 = 6,

a = 6,a>b,则a = a-b =6-3 = 3,

a = 3,a = b = 3,此时a = b = 3循环结束。

代码如下:

#include <stdio.h>
int main()
{
	int a, b;
	printf("请输入两个整数:");
	scanf("%d %d", &a, &b);
	while (a != b)
	{
		if (a > b)
			a = a - b;
		else
			b = b - a;
	}
	printf("最大公约数为:%d\n", a);

	return 0;

}

3.穷举法 

思路:

(1)选出a和b最小的数放入c中,然后分别用a和b对c求余数,看是否能被c整除,同时能被c整除则c是这两个数的最大公约数

(2)如果不能被c同时整除,c进行减一(c--),一直执行到a和b同时能被c整除。

例如:a = 15,b = 18

把较小值赋给c,c = 15,a%c = 15%15 = 0,b = b%c = 18%15 = 3,不能同时被c整除,循环继续 c--;

a%c = 15%14 = 1,b = b%c = 18%14 = 4,不能同时被c整除,循环继续 c--;

....(不一一列举了)

a%c = 15%3 = 0,b = b%c = 18%3 = 0,能同时被c整除,循环结束。

代码如下:

#include<stdio.h>  
int main()
{

	int a, b;
	int c = 0;
	printf("请输入两个整数:");
	scanf("%d %d", &a, &b);
	c = (a > b) ? b : a;   //三目运算符 将最小的赋给c
	while (a % c != 0 || b % c != 0)    
	{
		c--;
	}
	printf("最大公约数为:%d\n", c);

}

最后,文章结束啦!!

上一篇:面试题32 - I. 从上到下打印二叉树


下一篇:如何将flash动画设为电脑桌面