欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言实现辗转相除法(两种方法)

程序员文章站 2024-03-12 16:12:20
...

辗转相除法:

又名“欧几里德算法”
C语言实现辗转相除法(两种方法)
图片来自搜狗搜索。

 

第一种方式:

根据定义就可以写出一种比较简单的实现方法:、

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
	int a,b,c;
	scanf("%d %d",&a,&b);
	c=a%b;
	while(c!=0)
	{
		a=b;
		b=c;
		c=a%b;	
	}
	printf("%d",b);//将除数输出 
	return 0;
}

 

第二种方式:

熟练掌握辗转相除法之后,可以用递归的形式来实现:

#include <stdio.h>
#include <stdlib.h>

//递归函数
int gcd(int a,int b){
	if(b==0) return a;//返回a,即返回上一步的b 
	return gcd(b,a%b);
}

int main(int argc, char *argv[]) {
	int a,b;
	scanf("%d %d",&a,&b);
	printf("%d",gcd(a,b));
	return 0;
}
相关标签: 算法和数据结构

上一篇: Python文件和输入输出

下一篇: