最大公約的兩種求法：
代碼如下：
#include<stdio.h>
int gcds(int a,int b)//stein算法
{
if(a<b){
int temp = a;
a = b;
b=temp;
}
if(0==b) //b=0返回
return a;
if(a%2==0 && b%2 ==0) //a和b都是偶數
return 2*gcds(a/2,b/2);
if ( a%2 == 0) // a是偶數，b是奇數
return gcds(a/2,b);
if ( b%2==0 ) // a是奇數，b是偶數
return gcds(a,b/2);
return gcds((a+b)/2,(a-b)/2);// a和b都是奇數
}
int gcdo(int a,int b) //歐幾里得
{
if(b==0)
return a;
if(a<b){
int temp = a;
a = b;
b=temp;
}
return gcdo(b,a%b);
}
int main()
{
int a,b;
while(scanf("%d %d",&a,&b)!=EOF)
{
printf("%d\n%d\n",gcds(a,b),gcdo(a,b));
}
return 0;
} 歐幾里得算法，當初老師給我們的時候，只是說這樣求可以求得最大公約數，沒給出證明。。
百度上搜了一下，基本證明思想a，b(a>b)的公約數和a，a%b的公約數是相同的。Stein算法證明也類似?。?
posted on 2010-09-07 12:09
jince 閱讀(777)
評論(0) 編輯 收藏 引用