Warum ist meine Subfactorial-Funktion um eins deaktiviert?

Question

Ich arbeite an einer Subfunktion in JavaScript implementieren, um die Gesamtzahl der möglichen Störungen für n Elemente zu berechnen, und ich habe etwas vermasselt. Meine Berechnung scheint immer eine hohe oder eine niedrige zu sein. Was habe ich vermasselt? Ist es ein Rundungsfehler?

function subfactorial (x) { 
 
    x = parseInt(x); 
 
    var i; 
 
    var sub = 0; 
 
    var sum = 0; 
 
    sum += factorial(x); 
 
    for (i = 0; i < x; i++) { 
 
    sub += (Math.pow(-1, i)/factorial(i)); 
 
    } 
 
    return sum * sub; 
 
} 
 

 
function factorial (y) { 
 
    var negative = y < 0; 
 
    y = parseInt(Math.abs(y)); // Ints only 
 
    var acc = 1; 
 
    for (y; y > 0; y--) { 
 
    acc *= y; 
 
    } 
 
    return negative ? -acc : acc; 
 
} 
 

 
function getSubfactorial() { 
 
    var val = document.getElementById('subfac').value; 
 
    document.getElementById('result').innerHTML = subfactorial(val); 
 
}

<label for="subfac">Subfactorial input:</label> 
 
<input type="number" id="subfac"> 
 
<button type="button" onClick="getSubfactorial()">Get Subfactorial</button> 
 
<div id="result"></div>

Zum Beispiel subfactorial(3) 3 kehrt, wenn die Antwort sollte 2. subfactorial(4) 8 zurückkehrt, wenn die Antwort sollte 9. subfactorial(5) Returns 45 (mit einem Gleitkomma- Rundungsfehler), wenn die Antwort sollte 44 sein und so weiter und so fort. Es scheint zu alternieren, dass es zu niedrig und zu hoch zwischen geraden und ungeraden Zahlen ist.

Die Formel Ich verwende kommt dies sein:

In TeX:

!x = x! \sum_{k=0}^{x}\frac {(-1)^k}{k!}

Rendered TeX:

Answer 1

Sie werden lachen:

for (i = 0; i < x; i++) { 

Das ist nicht, was die Summe Symbol bedeutet. Es sollte

sein

for (i = 0; i <= x; i++) { 

Auch das ist die wörtlichste Art, Subfactorial vorstellbar zu implementieren. Die Potenzierung ist nur eine Möglichkeit, "zwischen positiv und negativ zu oszillieren" - aber in Javascript gibt es etwa 10 bessere Möglichkeiten, dies zu tun. Und es gibt keinen Grund, Floating-Point zu verwenden (oder sich darum zu kümmern). Anstatt 1/k zu berechnen! und dann Multiplikation mit x !, berechnen x!/k !, die als

getan werden kann

var factDiv = function(x, k) { 
    return (k >= x) ? 1 : (x * factDiv(x-1,k)); 
} 

Und dann subfactorial() kann definiert werden als

var subfactorial = x => { 
    var p = 1; 
    var sum = 0; 
    for (var k=0; k <= x; k++) { 
    sum += p * factDiv(x, k); 
    p *= -1; 
    } 
    return sum; 
} 

Answer 2

Die Summe geht von x = 0 nach x enthalten. Ändern Sie die Ausgangsbedingung des for Schleife

function subfactorial (x) { 
 
    x = parseInt(x); 
 
    var i; 
 
    var sub = 0; 
 
    var sum = 0; 
 
    sum += factorial(x); 
 
    for (i = 0; i <= x; i++) { 
 
    sub += (Math.pow(-1, i)/factorial(i)); 
 
    } 
 
    return sum * sub; 
 
} 
 

 
function factorial (y) { 
 
    var negative = y < 0; 
 
    y = parseInt(Math.abs(y)); // Ints only 
 
    var acc = 1; 
 
    for (y; y > 0; y--) { 
 
    acc *= y; 
 
    } 
 
    return negative ? -acc : acc; 
 
} 
 

 
function getSubfactorial() { 
 
    var val = document.getElementById('subfac').value; 
 
    document.getElementById('result').innerHTML = subfactorial(val); 
 
}

<label for="subfac">Subfactorial input:</label> 
 
<input type="number" id="subfac"> 
 
<button type="button" onClick="getSubfactorial()">Get Subfactorial</button> 
 
<div id="result"></div>

Answer 3

Dies scheint es zu beheben.

for (i = 0; i <= x; i++) { 
    sub += (Math.pow(-1, i)/factorial(i)); 
} 

Ändern Sie die Schleife zu i < = x. Noch ein paar Rundungsfragen. Wahrscheinlich eine Javascript-Sache. Sieht so aus, als ob es jetzt die richtigen Zahlen bekommt.