Warum ist der folgende Code falsch? Binomialkoeffizient

Question

Ich mache Projekt Euler und ich bin bei Problem 15 jetzt, hier ist ein Link: https://projecteuler.net/problem=15. Ich versuche das mit Binomialkoeffizienten zu lösen. Hier ist eine Seite, die es erklärt: http://www.mathblog.dk/project-euler-15/. Sie können es unten finden.

Meine Frage ist, warum ist der folgende Code falsch? Da dies dem mathematischen Algorithmus folgt, denke ich: n-k + i/i

 int grid = 20; 
     long paths = 1; 
     for (int i = 0; i < grid; i++) 
     { 
      paths *= (grid * 2) - (grid + i) 
      paths /= (i + 1); 
     } 
     Console.WriteLine(paths); 
     Console.ReadKey(); 

Und warum ist dieser Code falsch? Dies ist genau wie die Mathblog-Seite, aber in 1 Zeile.

 int grid = 20; 
     long paths = 1; 
     for (int i = 0; i < grid; i++) 
     { 
      paths *= ((grid * 2) - i)/(i + 1); 
     } 
     Console.WriteLine(paths); 
     Console.ReadKey(); 

Aber warum ist dieser Code dann richtig? Ist es nicht dasselbe wie der vorherige Code? Und es folgt nicht genau dem mathematischen Algorithmus, oder? Weil es n-k + i/i ist, und dieser Code tut n-i/i

Thnx Jungs!

Answer 1

Wenn Sie die Berechnung combain wollen es wie dieses

paths = (path *((grid * 2) - i))/(i + 1); 

Answer 2

Vereinbarungs sein sollte, in vielen Programmiersprachen, int/int gibt einen int, * keine Gleitkommazahl. Ihre Methode impliziert, dass "Pfade" Werte annehmen sollten, die nicht int sind. In der Tat sollte keine der drei Methoden funktionieren, aber durch einen glücklichen Zufall funktionierte der letzte: Im Grunde, weil alle Zwischenwerte von "Pfaden" auch Binomialkoeffizienten sind.

Hinweis zum Debugging: Bitten Sie Ihr Programm, die Zwischenwerte auszugeben. Das hilft sehr.

*: Als Mathematiker brauche ich diese Funktion fast nie. Tatsächlich hätte die andere Konvention (int/int -> double) mein Leben als Programmierer im Durchschnitt einfacher gemacht.

---

Ich habe mir den Blog angesehen, den Sie erwähnen. Dies macht Ihre Nachricht viel verständlicher. Der Blog erwähnt eine Formel: das Produkt für i von 1 bis k von (n-k + 1)/i. So ist es mimick Sie würden

for (int i = 1; i <= grid; i++) // bounds! 
    { 
     paths *= (grid * 2) - (grid - i) // minus sign! 
     paths /= (i + 1); 
    } 

über die Tatsache schreiben müssen, dass dies mit ints arbeitet: Dies ist ein Unfall aufgrund der Tatsache, dass in den Zwischenwerten des Produkts (am Ende jeder Schleife) sind Binomialkoeffizienten während der gesamten Berechnung. Wenn Sie die Produkte und Divisionen in einer anderen Reihenfolge berechnen würden, könnten Sie sehr gut Nicht-Ganzzahlen erhalten, so dass die Berechnung wegen der Konvention int/int -> int mit einem Integer-Variablentyp für Pfad fehlschlagen würde. Der Blog ist nicht sehr hilfreich darin, dies nicht zu erwähnen.