UC知道为什么求最大公约数要这样呢??有没有别的算法
来源：百度知道 编辑：UC知道 时间：2024/05/27 20:50:24
我知道求最大公约数的算法,#include <iostream>
#include<iostream>
using namespace std;
int main()
{
int gongYue(int ,int);
cout<<"Please input two integer:";
int x,y,i;
cin>>x>>y;
i=gongYue(x,y);
cout<<i;
return 0;
}
int gongYue(int a,int b )
{
int t;
if(a<b)t=a,a=b,b=t;
t=a%b;
while(t!=0)
{
a=b;
b=t;
t=a%b;
}
return b;
}
不过为什么是这样呢??
这个算法怎么解释??
#include<iostream>
using namespace std;
int main()
{
int gongYue(int ,int);
cout<<"Please input two integer:";
int x,y,i;
cin>>x>>y;
i=gongYue(x,y);
cout<<i;
return 0;
}
int gongYue(int a,int b )
{
int t;
if(a<b)t=a,a=b,b=t;
t=a%b;
while(t!=0)
{
a=b;
b=t;
t=a%b;
}
return b;
}
不过为什么是这样呢??
这个算法怎么解释??
你的这个就是欧几里德算法~O(∩_∩)O~
是求最大公约数最好的算法~
http://baike.baidu.com/view/795549.htm
看看这个链接你就会明白的 呵呵
是个经典的算法O(∩_∩)O~
在我知道这个算法前是用自己编的算法，
但效率跟这个没法比的~O(∩_∩)O~所以没必要用其它算法
最大公约数就是该数本身
还需要求吗
..................
这个算法的思想是辗转相除呀！！！
用短除法