求兩個或N個數(shù)的最大公約數(shù)(gcd)和最小公倍數(shù)(lcm)的較優(yōu)算法
//兩個數(shù)的最大公約數(shù)--歐幾里得算法
int gcd(int a, int b)
{
if (a < b)
swap(a, b);
if (b == 0)
return a;
else
return gcd(b, a%b);
}
//n個數(shù)的最大公約數(shù)算法
//說明:
//把n個數(shù)保存為一個數(shù)組
//參數(shù)為數(shù)組的指針和數(shù)組的大小(需要計算的數(shù)的個數(shù))
//然后先求出gcd(a[0],a[1]), 然后將所求的gcd與數(shù)組的下一個元素作為gcd的參數(shù)繼續(xù)求gcd
//這樣就產(chǎn)生一個遞歸的求ngcd的算法
int ngcd(int *a, int n)
{
if (n == 1) return *a;
return gcd(a[n-1], ngcd(a, n-1));
}
//兩個數(shù)的最小公倍數(shù)(lcm)算法
//lcm(a, b) = a*b/gcd(a, b)
int lcm(int a, int b)
{
return a*b/gcd(a, b);
}
//n個數(shù)的最小公倍數(shù)算法
//算法過程和n個數(shù)的最大公約數(shù)求法類似
//求出頭兩個的最小公倍數(shù),再將欺和大三個數(shù)求最小公倍數(shù)直到數(shù)組末尾
//這樣產(chǎn)生一個遞歸的求nlcm的算法
int nlcm(int *a, int n)
{
if (n == 1)
return *a;
else
return lcm(a[n-1], nlcm(a, n-1));
}
posted on 2010-10-02 14:20
Vontroy 閱讀(3577)
評論(1) 編輯 收藏 引用 所屬分類:
數(shù)論