[問題] 請問一個GCD的演算法

看板C_and_CPP作者 (SPAM)時間12年前 (2012/08/06 21:57), 編輯推噓17(17推 0噓 20→)
留言37則, 20人參與, 最新討論串1/1
int gcd (int a, int b){ while(b ^= a ^= b ^= a %= b); return a; } 想請問有沒有大大知道這個公式是怎麼來的!? 多謝! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.0.109
→
08/06 22:01, , 1F
這個寫法是不好的 請別用
08/06 22:01, 1F
推
08/06 22:06, , 2F
嗯，不要用 ＠＠
08/06 22:06, 2F
推
08/06 22:07, , 3F
b^=a^=b^=a 相當於a,b互換，所以就a %= b之後互換繼續除
08/06 22:07, 3F
推
08/06 22:11, , 4F
寫普通的輾轉相除就好
08/06 22:11, 4F
→
08/06 22:42, , 5F
八戒!
08/06 22:42, 5F
→
08/06 22:46, , 6F
我相信一定有人看到這樣的code會爆炸的
08/06 22:46, 6F
→
08/06 22:47, , 7F
wow我沒想過用^做交換的
08/06 22:47, 7F
→
08/06 23:26, , 8F
可讀性好差= =看得好痛苦
08/06 23:26, 8F
推
08/06 23:56, , 9F
我已經爆炸了
08/06 23:56, 9F
推
08/07 00:15, , 10F
主要問題就是五樓說的置底第八戒
08/07 00:15, 10F
→
08/07 00:15, , 11F
而且用 ^= 一條式子交換變數的方法我在 #1Deo3lyi 也指出了
08/07 00:15, 11F
→
08/07 00:16, , 12F
它不是在任何地方都會照所想的作用的
08/07 00:16, 12F
推
08/07 00:19, , 13F
寫這種幹啥啊 之後的人看到會崩潰吧
08/07 00:19, 13F
→
08/07 12:52, , 14F
感謝開解！
08/07 12:52, 14F
→
08/07 13:03, , 15F
^=限制多，還是自己用temp換保險的多
08/07 13:03, 15F
推
08/07 14:14, , 16F
還可以縮成一行, 超屌的
08/07 14:14, 16F
推
08/07 19:26, , 17F
while(a%=b && b%=a);
08/07 19:26, 17F
→
08/07 19:26, , 18F
return a + b;
08/07 19:26, 18F
推
08/07 19:46, , 19F
樓上的要加括號 不然 && 是比 %= 優先的
08/07 19:46, 19F
推
08/07 20:16, , 20F
請問 *p++ = *k++ , 這樣也算違反八戒嗎??
08/07 20:16, 20F
→
08/07 20:17, , 21F
意思是說對p ( or k )來說有違反嗎?
08/07 20:17, 21F
→
08/07 20:33, , 22F
忘記了orz
08/07 20:33, 22F
→
08/07 20:56, , 23F
*p++ = *k++ 是正確的
08/07 20:56, 23F
推
08/07 21:10, , 24F
int *p; p = (int *) &p; *p++ = 4; 好亂
08/07 21:10, 24F
推
08/08 00:57, , 25F
就算我知道那個演算法 打死我也不會這樣寫
08/08 00:57, 25F
推
08/08 09:02, , 26F
寫好懂的版本，給編譯器最佳化就好了。
08/08 09:02, 26F
→
08/08 09:48, , 27F
return (b==0 ? a : a%b);
08/08 09:48, 27F
→
08/08 09:49, , 28F
return (b==0 ? a : gcd(a%b) );
08/08 09:49, 28F
→
08/08 09:49, , 29F
return (b==0 ? a : gcd(b,a%b) ); //一直打錯orz
08/08 09:49, 29F
推
08/08 23:22, , 30F
(爆炸)
08/08 23:22, 30F
推
08/09 21:17, , 31F
Mini大, 可以幫忙解惑一下為什麼那樣是對的嗎??(*p++ = *k++
08/09 21:17, 31F
推
08/09 23:29, , 32F
p 改值一次，k 改值一次，k 原先指的地方提取一次，
08/09 23:29, 32F
→
08/09 23:29, , 33F
p 原先所指的地方為了修改這個值提取一次寫入一次
08/09 23:29, 33F
→
08/09 23:29, , 34F
所以是 OK 的
08/09 23:29, 34F
→
08/09 23:30, , 35F
四個變數有三個有寫入 但沒有變數寫入兩次
08/09 23:30, 35F
→
08/09 23:31, , 36F
也沒有變數是不為了改值而提取值的 因此沒有違反八戒
08/09 23:31, 36F
推
08/11 14:03, , 37F
感謝 LPH66大 讓我想一下 @_@|| 我比較笨..晚點再問問題
08/11 14:03, 37F
‣ 更多 spam 的文章
文章代碼(AID): #1G7yrFKY (C_and_CPP)