面試題目記錄(2)
2020/07/01閱讀時間約 1 分鐘
題目敘述
輸入兩個數字N1、N2
輸出N1、N2、兩數的最大公因數、兩數的最小公倍數
輸出N1、N2、兩數的最大公因數、兩數的最小公倍數
解題思考
求解最大公因數算是基本題，使用輾轉相除法找出答案，進一步再找出最小公倍數，為國中數學基礎。
實作
建立輾轉相除法的function gcd()，以遞迴方式呈現。最小公倍數以下方質因數分解後的例子作為說明:
N1 = 12, 即2*2*3
N2 = 30, 即2*3*5
因此最大公因數為共同的2*3
最小公倍數為最大公因數去乘上兩數分別多出來的部分，即N1中的2還有N2中的5
所以最大公因數為2*3 = 6，最小公倍數為(2*3)*2*5 = 60
N2 = 30, 即2*3*5
因此最大公因數為共同的2*3
最小公倍數為最大公因數去乘上兩數分別多出來的部分，即N1中的2還有N2中的5
所以最大公因數為2*3 = 6，最小公倍數為(2*3)*2*5 = 60
感想
我認為最大的考點在於求最大公因數時輾轉相除法的實作，可以使用遞迴或是迴圈加上變數交換來寫。最小公倍數的部分倒是沒記得公式，只記得基本原理上的求法。
當然！結果上是相同的。
留言0
查看全部
