這是很多程式的入門練習題，尤其是使用遞迴呼叫(recursive call)的方式。
如何找出兩個數的最大公因數呢?
最常見的方式是輾轉相除法---輾轉相除法，又名歐幾里得演算法(Euclidean algorithm)乃求兩個正整數之最大公因數的演算法。
這是已知最古老的演算法, 其可追溯至前300年。首次出現於歐幾里得的《幾何原本》(第VII卷，命題i和ii)中，而在中國則可以追溯至東漢出現的《九章算術》。這演算法並不需要把二數作質因數分解。
以下分別以C++實作這兩個方法:
《九章算術》
計算最大公因數
請輸入兩個數字:
1st: 96
2nd: 72
96>72, 96-72=24
24<72, 72-24=48
24<48, 48-24=24
24=24, 最大公因數為:24
請按任意鍵繼續 . . .
#include <iostream>
using namespace std;
int fun(int a, int b)
{
if(a>b)
{
cout << a << ">" << b << ", " << a << "-" << b << "=" << a-b << endl;
return fun(a-b,b);
}
else if(a<b)
{
cout << a << "<" << b << ", " << b << "-" << a << "=" << b-a << endl;
return fun(a,b-a);
}
else
{
cout << a << "=" << b << ", ";
return (a);
}
}
int main(){
int x,y;
cout << "計算最大公因數\n" << "請輸入兩個數字:\n";
cout << "1st: ";
cin >> x;
cout << "2nd: ";
cin >> y;
cout << "最大公因數為:" << fun(x,y) << endl;
system("Pause");
return 0;
}
《幾何原本》
計算最大公因數
請輸入兩個數字:
1st: 96
2nd: 72
96>72, 96%72=24
72%24=0, 最大公因數為:24
請按任意鍵繼續 . . .
#include<iostream>
using namespace std;
int fun(int a, int b){
if(a%b){
cout<<a<<">"<<b<<", "<<a<<"%"<<b<<"="<<a%b<<endl;
return fun(b, a%b);
}
else{
cout<<a<<"%"<<b<<"=0, ";
return (b);
}
}
int main(){
int x,y;
cout<<"計算最大公因數\n"<<"請輸入兩個數字:\n";
cout<<"1st: ";
cin>>x;
cout<<"2nd: ";
cin>>y;
if(x>y)
cout<<"最大公因數為:"<<fun(x,y)<<endl;
else if(x<y)
cout<<"最大公因數為:"<<fun(y,x)<<endl;
else
cout<<"最大公因數為:"<<x<<endl;
system("Pause");
return 0;
}
