[CSDN] JavaScript趣题:最小公分母

发表于:  阅读量:10688

摘要

你有一个列表,里面的每一对数都代表了一个分数的分子与分母:[[numer_1,denom_1],...[numer_n,denom_n]]所有的数字都是正整数。你得找出最...

你有一个列表,里面的每一对数都代表了一个分数的分子与分母:

[ [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<array.length;i++){
            if(max % array[i]){
                max++;
                continue signal;
            }
        }
        return max;
    }
}

当然,这个方法效率不高,最好求最小公倍数的方法是借助最大公约数。

然后就好办了,取出列表中所有数组的第二项,也就是分母项,组成新数组,传入scm方法,得出最小公分母。

最后,遍历列表,拼接字符串就可以了。

function convertFrac(lst){
    var array = [];
    var str = "";
    for(var i=0;i<lst.length;i++){
        array.push(lst[i][1]);
    }
    var result = scm(array);
    for(var i=0;i<lst.length;i++){
        str += "(" + result / lst[i][1] * lst[i][0] + "," + result + ")";
    }
    return str;
}



关键词: JavaScript趣题

上一篇:  栈的模拟实现

下一篇:  HDU5692Snacks(线段树)

渝ICP备16002246号 Copyright © 2017. Singee77.com