Repeating Decimal Algorithm

I'm trying to write a simple repeating decimal algorithm. Right now I'm pretty close to having something that works.

I tried to use this algorithm: How to know the repeating decimal in a fraction?

"A very simple algorithm is this: implement long division. Record every intermediate division you do. As soon as you see a division identical to the one you've done before, you have what's being repeated."

I was able to do all of the above except for detecting the repeating decimal pattern and putting it in brackets.

For the fraction 7/13 my output should be 0.[538461] right now it's 0,5,3,8,4,6,1,5,3,8,4,6,1,5,3,8,4,6,1,5.

Any suggestions on how to implement detecting the repeating decimal pattern and putting it in brackets using the algorithm I mentioned above? I know there's similar questions but I would like to implement it with my current code using the algorithm I mentioned above.

<script>
// All the prime numbers under 1,000
var primeNumbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997];

// Finds all the prime factors of a non-zero integer
// a = integer
function primeFactors(a) {
    var primeFactors = new Array(); 

    // Trial division algorithm
    for (var i = 0, p = primeNumbers[i]; i < primeNumbers.length && p * p <= a; i++, p = primeNumbers[i]) {
        while (a % p == 0) {         
                primeFactors.push(p);

                a /= p;
        }
    }

    if (a > 1) {
        primeFactors.push(a);
    }

    return primeFactors;
}

// Converts a fraction to a decimal
// i = number
// n = numerator
// d = denominator
function fractionToDecimal(n, d) {
    var pFS = primeFactors(d);

    for (var i = 0; i < pFS.length; i++) { // Go through each of the denominators prime factors

        if (pFS[i] !== 2 && pFS[i] !== 5) { // We have a repeating decimal

            var output = new Array();

            // Let's find the repeating decimal
            // Repeating decimal algorithm - uses long division
            for (var i = 0; i < 20; i++) { // For now find 20 spots, ideally this should stop after it finds the repeating decimal

                // How many times does the denominator go into the numerator evenly
                var temp2 = parseInt(n / d);

                output.push(temp2);

                var n = n % d;

                n += "0";
            }

            return "Repeating decimal: " + output;
        }
    }

    // Terminating decimal
    return "Terminating decimal: " + n / d;
}

document.write(fractionToDecimal(7, 13));
</script>

---

You've got most of it figured out, only 2 parts are missing:

Check that the numerator of long division is repeating and halt the loop. When numerator repeats, it means that we have found the repeating decimal.

Convert array to string without commas, which is easily achievable by using join('') .

Here's the relevant part of your code with the above 2 points implemented:

function fractionToDecimal(n, d) {
    var pFS = primeFactors(d);
    for (var i = 0; i < pFS.length; i++) { // Go through each of the denominators prime factors

        if (pFS[i] !== 2 && pFS[i] !== 5) { // We have a repeating decimal

            var output = new Array();
            var ns = new Array();

            // Let's find the repeating decimal
            // Repeating decimal algorithm - uses long division
            for (var i = 0; i < 20; i++) { // For now find 20 spots, ideally this should stop after it finds the repeating decimal
                // How many times does the denominator go into the numerator evenly
                var temp2 = parseInt(n / d);

                if (ns[n] === undefined) {
                    ns[n] = i;
                } else {
                    return "Repeating decimal: " + 
                        output.slice(0, 1).join('') +
                        '.' +
                        output.slice(1, ns[n]).join('') +
                        '[' + output.slice(ns[n]).join('') + ']'
                    ;
                }

                output.push(temp2);
                var n = n % d;
                n += "0";
            }           
            return "Repeating decimal: " + output;
        }
    }

    // Terminating decimal
    return "Terminating decimal: " + n / d;
}

jsFiddle with the complete code: http://jsfiddle.net/49Xks/

链接地址: http://www.djcxy.com/p/11760.html

上一篇: 如何使用基础值定义一个枚举常量

下一篇: 重复十进制算法