JavaScript趣題:最小公分母

你有一個列表,裡面的每一對數都代表瞭一個分數的分子與分母:

[ [numer_1, denom_1] , … [numer_n, denom_n] ]

所有的數字都是正整數。

你得找出最小的公分母D,並用D替換原來的分母denom,並且改變分子numer,使得他們表示的數值不變。

例如:

[ [1, 2], [1, 3], [1, 4] ] // => (6,12)(4,12)(3,12)

在這裡,2,3,4的最小公分母是12,所以分母改為12,同時分子相應做出改變,以維持數值不變。

1/2和6/12是一樣大的,1/3和4/12也一樣大。

這個題目關鍵是找最小公分母,或者說所有分母的最小公倍數。

所以,我們首先需要一個求最小公倍數的scm方法,它接收一個數組作參數。

它從數組最大的元素開始累加,看是否每一個數組元素都能整除,如果能,那就是最小公倍數。

//smallest common multiple
function scm(array){
    var max = Math.max.apply(null,array);
    signal:
    while(true){
        for(var i=0;i

當然,這個方法效率不高,最好求最小公倍數的方法是借助最大公約數。

然後就好辦瞭,取出列表中所有數組的第二項,也就是分母項,組成新數組,傳入scm方法,得出最小公分母。

最後,遍歷列表,拼接字符串就可以瞭。

function convertFrac(lst){
    var array = [];
    var str = "";
    for(var i=0;i
   

發佈留言