求最大公约数的递归方法(写给和我一样的初学者)

作者在 2011-03-29 21:38:14 发布以下内容
学习程序有一些经典的求解算法我们必须得掌握,
像本例——求两个非0自然数的最大公约数——是学习C语言时必要理解的。
为解决它,通常的函数编写是这样的:
int fun(int a,int b)
{
 int tmp;
 if(a<b)
 {
  tmp=a;
  a=b;
  b=tmp;
 }
 while(b!=0)
 {
  tmp=a;
  a=b;
  b=tmp%b;
 }
 return a;
}
这里给出一个解决上述问题的递归函数——
int fun(int a,int b)
{
 int temp;
 if(a<b)
 {
  temp=a;
  a=b;
  b=temp;
 }
 if(b==0) return a;
 else return fun(b,a%b);
}
显然,第二个短小而更加有吸引力。
Cyuyan | 阅读 2417 次
文章评论,共11条
李臣
2011-04-01 00:18
1
是的,那个欧几里得算法很经典。很多编程书中讲递归时都有提到它。但我认为那个判断大小没有必要,可以直接写成下面这样:<br />
int fun(int a,int b)<br />
{<br />
 if(b==0) return a;<br />
 else return fun(b,a%b);<br />
}
尤慕思(作者)
2011-04-01 12:31
2
<div class="quote"><span class="q"><b>李臣</b>: 是的,那个欧几里得算法很经典。很多编程书中讲递归时都有提到它。但我认为那个判断大小没有必要,可以直接写成下面这样:<br />
int fun(int a,int b)<br />
{<br />
 if(b==0) r</span></div>谢谢你你说明这一点,让我很受启发<br />
第一个函数的判断大小也没有必要了<img src="image/face/2.gif" class="face">
baijingchao
2011-04-04 20:29
3
肯定没必要,不过被除数小的话就会自动交换的!
baijingchao
2011-04-04 20:30
4
肯定没必要,不过被除数小的话就会自动交换的!
尤慕思(作者)
2011-04-05 17:55
5
<div class="quote"><span class="q"><b>baijingchao</b>: 肯定没必要,不过被除数小的话就会自动交换的!</span></div>自动交换怎么解啊<img src="image/face/11.gif" class="face">
潜修僧
2011-04-10 12:49
6
根据线性代数中f(x)=q(x)*g(x)+r(x),其中f(x),g(x),q(x),r(x)分别为被除数,除数,商,余数;则f(x),g(x)和g(x),r(x)有相同的公因式。<br />
利用这个原理来写递归算法求最大公约数。
尤慕思(作者)
2011-04-11 22:51
7
<div class="quote"><span class="q"><b>潜修僧</b>: 根据线性代数中f(x)=q(x)*g(x)+r(x),其中f(x),g(x),q(x),r(x)分别为被除数,除数,商,余数;则f(x),g(x)和g(x),r(x)有相同的公因式。<br />
利用这个原理来写递归算法</span></div>有点受伤,俺不是大学生,俺不是高中生,俺把你的题读了好多遍——不懂啊<br />
俺一直在努力,一直有差距--好好学习,俺不灰心<img src="image/face/2.gif" class="face">
潜修僧
2011-04-14 11:48
8
对不起呀,只是说一下而已!其实大学生也没什么,只是多个文凭而已!最关键的一个人要努力学习就行了,相信你终有一天会实现自己理想的,一起加油吧!
尤慕思(作者)
2011-04-14 20:49
9
<div class="quote"><span class="q"><b>潜修僧</b>: 对不起呀,只是说一下而已!其实大学生也没什么,只是多个文凭而已!最关键的一个人要努力学习就行了,相信你终有一天会实现自己理想的,一起加油吧!</span></div>没事没事,呵呵<img src="image/face/2.gif" class="face">
梦幻天涯
2011-06-10 13:50
10
分享学习心得,共同进步,
尤慕思(作者)
2011-06-12 22:45
11
<div class="quote"><span class="q"><b>梦幻天涯</b>: 分享学习心得,共同进步,</span></div><img src="image/face/2.gif" class="face">三Q
游客请输入验证码
浏览71081次
最新评论