James b602b04036 | ||
---|---|---|
.. | ||
doc | ||
test | ||
Readme.md | ||
main.cpp | ||
main.exe |
Readme.md
『入门』(递归专题)最大公约数之辗转相除法
[问题描述]
辗转相除法,又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法,其可追溯至3000年前。而在中国则可以追溯至东汉出现的《九章算术》。
教学案例,必须使用递归函数完成求解!
输入两个正整数n和m,均小于10^9。求解n和m的最大公约数。
[输入格式]
一行,两个整数,空格间隔。
[输出格式]
一个整数值,n和m的最大公约数。
[输入样例]
12 21
[输出样例]
3