Home > Web Front-end > JS Tutorial > body text

JavaScript fun questions: lowest common denominator

黄舟
Release: 2017-02-04 15:31:53
Original
1545 people have browsed it

You have a list, and each pair of numbers in it represents the numerator and denominator of a fraction:

[ [numer_1, denom_1] , ... [numer_n, denom_n] ]
Copy after login

All numbers are positive integers.

You have to find the smallest common denominator D, replace the original denominator denom with D, and change the numerator so that the values ​​they represent remain unchanged.

For example:

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

Here, the lowest common denominator of 2,3,4 is 12, so the denominator is changed to 12, and the numerator is changed accordingly to maintain the same value.

1/2 and 6/12 are the same size, and 1/3 and 4/12 are also the same size.

The key to this question is to find the lowest common denominator, or the lowest common multiple of all denominators.

So, we first need a scm method to find the least common multiple, which receives an array as a parameter.

It starts accumulating from the largest element of the array to see if each array element can be divisible. If so, it is the least common multiple

//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;  
    }  
}
Copy after login

Of course, this method is not efficient, it is best to find The least common multiple method uses the greatest common divisor.


Then it’s easy to handle. Take out the second item of all arrays in the list, which is the denominator item, form a new array, and pass it into the scm method to get the lowest common denominator. .

Finally, just traverse the list and concatenate the strings.

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;  
}
Copy after login

The above is the content of JavaScript interesting questions: the lowest common denominator. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!


Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template