所謂的歐幾里得算法( Euclidean Algorithm ),其實就是我們在 國/高 中學過的「輾轉相除法」。 如果你忘了什麼叫作「輾轉相除法」,沒關係 Jason 在這邊幫你稍微複習一下。 「輾轉相除法」最早是出現在大神-歐幾里得 的神作《幾何原本》[註一]當中,是用來求解兩個整數的最大公因數 ( Greatest Common Divisor,GCD ) 的方法。至於為啥歪國人叫歐幾里得算法,我們卻要叫輾轉相除法呢? 要我猜的話,就華人教育想說取個假掰一點的名子,自以為可以讓學生比較好記憶吧~ ㄜ.. 這段好像不能用齁,講這樣應該會被打 哈哈哈哈 應該是源自於,用這個方法演算求解的過程, 其實就是不停的用兩個數字相除取餘數,再用餘數輾轉下去相除,直至餘數為 0 時結束。
比較起來 Jason 還是覺得我在本篇封面圖用的那種計算方法看起來舒服多了,也比較容易直接寫成code。
ㄜ.. 雖然也不知道 Jason 484 Computer Science 唸太久,搞到腦迴路都被改變了xD 回到歐幾里得演算法,那為什麼像這樣利用輾轉相除的原理就可以找到最大公因數呢? 那我們利用上面的例子,A=1034 , B=893 來說明好了。 既然我們已求出GCD = 47,1034 / 47 = 22 , 893 / 47 = 19, 那我們就用先 22格跟19格分別來代表 A 跟 B,這樣應該比較好理解,參考下方 gif 圖:
我們在國小應該就學過一個概念,乘法可以視作累加;除法可以視作累減。
可以看到動圖中兩數(A、B)不停的在相互做相除(累減)的動作,
如果說你想看比較嚴謹的數學證明( 應該沒人這麼無聊吧.. ),就自己再去網路上找其他資源來看吧~ 不然你也是可以回學校問你的數學老師啦 >"< 由於歐幾里得算法可以用來找最大公因數、判斷兩數是否互質的特性,常常被應用在密碼學領域e.g.
萬丈高山始於微塵,有些在你眼裡看似很難很複雜的演算法,可能也至是基於一些再平常不過演算法、數學原理、Domain Knowledge,一層又一層,一層再一層的累積、堆砌上去的。就像你在國小學會加減乘除以後,到了國中才又辦法解二元一次方程式、一元二次方程式。 萬里江河始於點滴,其實不管身處什麼產業、正在學習什麼技能,Jason 認為都一樣啦~ 還是得要肯花時間投入學習,一點一滴累積,或許你認為今天的自己還是很廢、什麼都不會, 但只要今天的自己相比昨天的你,有再多進步一點、多累積一些,總會有爬上山頭的那一天啦! 就像歐幾里得算法, 不管進來的兩個數多大 ( 困難與挑戰多大 ); 透過不停的輾轉相除 ( 每日的學習與奮鬥 ); 數字總會越除越小 ( 進步與累積 ); 終會讓你有整除餘0的那一天。 最後附上,「歐幾里得算法」的實現代碼:
Euclidean Algorithm
[註一] 《幾何原本》由古希臘數學家歐幾里得所著,共13卷。已成為現代數學最重要的基礎!
[註二] 互質:在數學上互質的定義就是兩整數A、B,除了1 以外沒有其他的公因數,即 GCD(A,B) = 1。
2 評論
jenny
6/20/2022 01:39:48
哇 第一次懂了GCD這個code的原理
回覆
kevin
10/19/2023 19:17:52
讚讚
回覆
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|