Dwumian Newtona - błędny wynik

Odpowiedz Nowy wątek
2019-01-28 02:00
0

Dobry wieczór. Piszę program, w którym potrzebne jest mi obliczenie symbolu Newtona. W tym celu napisałem stosowną funkcję. Problem w tym, że już po pierwszym teście (n=49, k=6) funkcja zwraca błędną wartość (12224520 zamiast 13983316). Szukałem różnych implementacji, jednak wszystkie iteracyjne nie różnią się od mojej. Co może być nie tak?

#include <iostream>

uint64_t binomial(uint64_t n, uint64_t k) {
    if(k>n-k) {
        k=n-k;
    }

    uint64_t result=1;
    for(uint64_t i=1; i<=k; ++i)
    {
        result*=(n-i+1)/i;
    }
    return result;
}

int main()
{
    //test

    uint64_t x=binomial(49, 6);
    std::cout<<x<<std::endl;

    return 0;
}
edytowany 2x, ostatnio: furious programming, 2019-01-28 02:44
Pokaż pozostałe 2 komentarze
5 i 3 to słabo, 10, 20, uint_64 powinien pociągnąć. - lion137 2019-01-28 02:10
Wykłada się na 9 i 4, 9 i 5 - niepamietamloginu 2019-01-28 02:10
To słabo z algorytmem, nie obiecuję, że dziś, ale jutro na pewno dam Ci dokładna analizę. - lion137 2019-01-28 02:11
Dodam, że dla par 9 i 4, 9 i 5, 9 i 6 wynik jest ten sam - 72. - niepamietamloginu 2019-01-28 02:28
@niepamietamloginu i @lion137: na demat dyskutujcie w postach. - furious programming 2019-01-28 02:45

Pozostało 580 znaków

2019-01-28 02:46
1

Już znalazłem błąd. Część (n-i+1)/i jest typu int. Można więc albo rozbić to działanie na dwie oddzielne instrukcje (najpierw mnożenie, a potem dzielenie), albo zrzutować i na double.

edytowany 1x, ostatnio: niepamietamloginu, 2019-01-28 02:47

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0