作者gaiger (hallowed be my name)
看板C_and_CPP
標題Re: [問題] c語言求gcd的副程式
時間Mon Nov 30 01:21:15 2009
為何不用迴圈寫?
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
1F：推 AstralBrain:原來那篇是用迴圈啊XD 11/30 01:24
2F：→ james732:那篇的感覺是... 程式並不是原po自己寫的 XD 11/30 01:38
3F：推 AstralBrain:看起來是史前時代的c code... 11/30 01:40
4F：推 AstralBrain:好 事情忙完了所以來認真吐槽一下 11/30 01:49
5F：→ AstralBrain:1. maxIter是多餘的 迴圈一定會在中間break的地方停止 11/30 01:50
6F：→ AstralBrain:2. if(smaller == 1)那段永遠不會執行到 11/30 01:50
7F：→ AstralBrain: 如果smaller是1, 會先進去c==0那邊 11/30 01:51
8F：推 AstralBrain:3. if(a > b)那段也是多餘的 11/30 01:53
9F：→ AstralBrain: sorry上面看錯.. 你沒有用c直接取代bigger.. 11/30 01:54
10F：→ AstralBrain: 3.當我沒說XD 11/30 01:54
11F：→ gaiger:故意寫的很蠢，不想搞暈新手 11/30 01:56
12F：→ gaiger:4.還有 if(c == 0) 可直接把c廢了 11/30 01:57
13F：推 AstralBrain:我覺得寫這麼長反而會搞暈別人@@ 11/30 01:57
14F：→ gaiger:寫成 if( !(bigger%smaller) ) 11/30 01:58
15F：→ gaiger:寫成 for(int i = 0; ;) 不會比較優雅 11/30 02:00
16F：推 AstralBrain:可以寫個while(true)就好 i根本沒必要存在 11/30 02:05
17F：→ AstralBrain:我的重點不在code長短 而是有永遠不會走到的code 11/30 02:05
18F：推 softwind:這code... 很強大... 我認輸... 11/30 02:31
19F：推 AstralBrain:4. 剛剛才發現你沒有用mod而是用減法.. 11/30 02:37
20F：→ AstralBrain: 所以maxIter根本就是錯的 11/30 02:38
21F：→ AstralBrain: 考慮gcd(1001, 2) maxIter=log(1001)+1=10 11/30 02:39
22F：→ AstralBrain: (咦 這樣第一次進for loop就錯了..) 11/30 02:40
23F：→ AstralBrain: 不知道該從哪裡開始吐槽.. 11/30 02:40
24F：→ AstralBrain: 進for loop之後 smaller=1001-2=999 bigger=2 11/30 02:41
25F：→ AstralBrain: 這裡開始整個亂掉 不用到maxIter就先炸了.. 11/30 02:42
26F：→ gaiger:嗯 謝謝樓上修正 11/30 03:10