Dwumiany spoj - błędna odpowiedź

Question

)Cześć

Zajmuję się zadaniem dwumiany ze spoja. link: https://pl.spoj.com/problems/BINOMS/

Przejrzałem już 10 tematów, próbowałem zmieniać typy zmiennych, sposoby liczenia silnii, nawet porobiłem ify do sytuacji wyjątkowych typu (0,0) (123,123), (12,0) itd. Dodatkowo sprawdzałem wyniki na wolframie i wszystko się zgadzało. Sędzia zwraca błędną odpowiedź, proszę o pomoc

#include <iostream>
#include <iomanip>

using namespace std;

long double factorial(long double &f)
{
        for(int i = f-1; i >= 1; i --)
        {
            f*=i;
        }

        return f;
}

int main()
{
    long double n;
    long double k;
    long double nk;

    int t;
    cin >> t;

    for(int i = 0; i < t; i ++)
    {
        cin >> n >> k;

        nk = n-k;

        cout << setprecision(10);
        if((n==0)&&(k==0)) cout << 1 << endl;
        else if((n!=0)&&(k==0)) cout << n << endl;
        else if(n==k) cout << 1 << endl;

        else cout << factorial(n)/(factorial(k)*factorial(nk)) << endl;
    }

    return 0;
}

 

Answer 1

Spróbuj wypisać i zweryfikować wartości wychodzące z factorial().

To, że wynik "nie przekracza 1 000 000 000" nie oznacza, że licznik/mianownik go nie przekracza.

Comments

Zgadza się, wynik chociażby 100!, jest niepoprawny, domyślam się, że błąd leży w typie long double, ale gdy próbuję zmienić na np. long long int to to komputer nawet 80! nie policzy, co należy zrobić?

---

Po co wyliczać całą silnię? Przyjrzyj się symbolowi Newtona, tam się większość rzeczy skraca, wystarczy to ładnie zapisać. Wyliczanie silni to zawsze zły pomysł że względu na szybko rosnące wartości

---

Wyliczałem silnię bo taka była moja pierwsza myśl na program, a skoro wyniki programu zgadzały się z wolframem to stwierdziłem, że w silnii błąd nie leżał. Poprawiłem program, ale teraz wywala błąd wykonania(SIGFPE). Sprawdziłem kod i wydaje mi się, że nie dzielę przez zero ani nic takiego. Bez ifa w linii 42 dla danych wejsciowych (1,20,19) wypluwał dziwne wyniki. Jakieś propozycje co mogę poprawić? Oto kod

#include <iostream>

using namespace std;

int K(int f)
{
    for(int i = f-1; i >= 1; i --)
    {
        f*=i;
    }

    return f;
}

int NK(int nk, int n)
{
    for(int i = nk+1; i <= n; i ++)
    {
        nk*=i;
    }

    return nk;
}

int main()
{
    int n, k, nk;
    int t;

    cin >> t;

    for(int i = 0; i < t; i ++)
    {

        cin >> n >> k;

        nk = n - k + 1;

        if((n==0)&&(k==0)) cout << 1 << endl;
        else if((n!=0)&&(k==0)) cout << n << endl;
        else if (n==k) cout << 1 << endl;
        else if ((n==k+1)) cout << n << endl;// o tym ifie mowa
        else cout << NK(nk,n)/K(k) << endl;
    }

    return 0;
}