【递归】辗转相除法

　

辗转相除法

 

辗转相除法; 又名欧几里德算法（Euclidean algorithm），是求最大公约数的算法

原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。并一直递归

#include<iOStream>
using namespace std;
/*辗转相除法：两个整数的最大公约数等于，大的除以小的余数，一直递归，直到整除余0后的整数
最小公倍数为两个公约数之积除以最大公约数 */ 
int gcd(int a,int b);
int main()
{
	int a,b,c,g;
	cout<<"please input two numbers";
	cin>>a,b;
	c=a*b;
	g=gcd(a,b);
	cout<<"最大公约数为"<<g<<"最小公倍数为"<<c/g; 
	return 0;
}

int gcd(int a,int b)
{
	if(b==0)
	 return a;
	else
	return gcd(b,a%b);
}

推导过程:==心疼自己没学好数学

相关阅读

使用递归下降法实现的简单计算器

最近在学编译原理，讲完了递归下降法，老师就布置了一个作业，使用递归下降法实现一个简易计算器。需求：实现简单的四则运算功能，有简单界

原来连续两次递归调用很简单

void rec(int N) { //为了区分这两个递归，分别为它们取个别名好了 if (N>0){  rec(N - 1);//rec1 rec(N - 10)

Java经典递归算法

1.斐波那契数列package com.luna.base; public class BirthRabbit { public static void main(String[] args) { int i = 1;