Re: [問題] c語言求gcd的副程式
看板C_and_CPP作者gaiger (hallowed be my name)時間16年前 (2009/11/30 01:21)推噓8(8推 0噓 18→)留言26則, 4人參與討論串1/2 (看更多)
為何不用迴圈寫?
int gcd(int a, int b)
{
int c;
int gcdnumber;
int maxIter;
maxIter = (int)log(double((a>b? a : b) ) + 1;
int bigger, smaller;
if(a > b){
bigger = a;
smaller = b;
}
else
{
bigger = b;
smaller = a;
}/*if a> b*/
int temp;
for(int i = 0; i< maxIter; i++){
c = bigger%smaller;
if(c == 0){
gcdnumber = smaller;
break;
}
else
{
if(smaller == 1){
gcdnumber = 1;
break;
}/*if(smaller == 1)*/
temp = smaller;
smaller = bigger - smaller;
bigger = smaller;
}/*if c == 0*/
}/*for maxiter*/
return gcdnumber;
}/* gcd */
大多數書都是講遞迴
但遞迴真的缺點不少:較慢，浪費較多計義體
且新手會被搞暈
※ 引述《badbadook ( 嗨浪)》之銘言：
: 1 int gcd(u,v)
: 2 int u,v;
: 3 {
: 4 int t;
: 5 do
: 6 {
: 7 if(u<v)
: 8 {t=u;u=v;v=t;};
: 9
: 10 u=u-v;
: 11 }
: 12 while (u!=v);
: 13
: 14 return(u);
: 15 }
: 請問7-10行的意義為何?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.178.67
推
11/30 01:24, , 1F
11/30 01:24, 1F
→
11/30 01:38, , 2F
11/30 01:38, 2F
推
11/30 01:40, , 3F
11/30 01:40, 3F
推
11/30 01:49, , 4F
11/30 01:49, 4F
→
11/30 01:50, , 5F
11/30 01:50, 5F
→
11/30 01:50, , 6F
11/30 01:50, 6F
→
11/30 01:51, , 7F
11/30 01:51, 7F
推
11/30 01:53, , 8F
11/30 01:53, 8F
→
11/30 01:54, , 9F
11/30 01:54, 9F
→
11/30 01:54, , 10F
11/30 01:54, 10F
→
11/30 01:56, , 11F
11/30 01:56, 11F
→
11/30 01:57, , 12F
11/30 01:57, 12F
推
11/30 01:57, , 13F
11/30 01:57, 13F
→
11/30 01:58, , 14F
11/30 01:58, 14F
→
11/30 02:00, , 15F
11/30 02:00, 15F
推
11/30 02:05, , 16F
11/30 02:05, 16F
→
11/30 02:05, , 17F
11/30 02:05, 17F
推
11/30 02:31, , 18F
11/30 02:31, 18F
推
11/30 02:37, , 19F
11/30 02:37, 19F
→
11/30 02:38, , 20F
11/30 02:38, 20F
→
11/30 02:39, , 21F
11/30 02:39, 21F
→
11/30 02:40, , 22F
11/30 02:40, 22F
→
11/30 02:40, , 23F
11/30 02:40, 23F
→
11/30 02:41, , 24F
11/30 02:41, 24F
→
11/30 02:42, , 25F
11/30 02:42, 25F
→
11/30 03:10, , 26F
11/30 03:10, 26F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：