2012年9月22日 星期六

最大公因數 (Greatest Common Divisor)

http://4rdp.blogspot.com/2012/09/blog-post_22.html

最近小朋友剛學最大公因數 (Greatest Common Divisor),問我兩數之間最大公因數求解,他說老師利用輾轉相減求之,其方法如下:

以較大數減較小數,較大數變小後,再繼續比較,直到兩數相等或其中某數值變成1

我畫了上圖解說,他很快理解原理。

例一:有兩數分別為 A = 7 和 B = 5,
A = 7 - 5 = 2, B = 5
A = 2, B = 5 - 2 = 3
A = 2, B = 3 - 2 = 1
最大公因數為 1

例二:有兩數分別為 A = 14 和 B = 10,
A = 14 - 10 = 4, B = 10
A = 4, B = 10 - 4 = 6
A = 4, B = 6 - 4 = 2
A = 4 - 2 = 2, B = 2
最大公因數為 2

有興趣的讀者可以延伸閱讀 NXT 無法使用遞歸 (Recursion) 一文,參考程式碼。

沒有留言:

張貼留言