Wątek zablokowany 2015-09-27 19:01 przez msm.

Silnia int

0

Witam, robię program http://pl.spoj.com/problems/BINOMS/ napisałem go, program dobrze działa dla małych liczb, przy większych program wywala. Jakieś pomysły na optymalizacje tych liczb czy coś?

 #include <iostream>

using namespace std;

int main()
{
    int liczbaprob;
    cin>>liczbaprob;
    for(int i=0; i<liczbaprob; i++)
    {
        long long int e=1;
        long long int c=1;
        int d;
        int b;
        cin >>d;
        int f;
        f=d;
        if(d==0)
            c=1;
        else
        {
            for(int j=0; j<d; j++)
            {
                c=c*d*(d-1);
                d--;
                d--;
            }
        }
        int a;
        cin>>a;
        b=f-a;
        if(b==0)
            e=1;
        else
        {
            for(int j=0; j<b; j++)
            {
                e=e*b*(b-1);
                b--;
                b--;
            }
        }
        long long int g=1;
        if(a==0)
            g=1;
        else
        {
            for(int j=0; j<a; j++)
            {
                g=g*a*(a-1);
                a--;
                a--;
            }
        }

        cout <<c/(e*g)<<endl;
    }
    return 0;
}
0

Zapewne przekraczasz zakres użytego typu.. silnia bardzo szybko daje ogromne wyniki.

0

Tak, wiem że przekraczam. Tylko co zrobić żeby nie przekraczać?

0

Na początek zacznij od sensownego nazwania zmiennych. Potem wywal powtarzające się kawałki kodu do osobnej funkcji. A potem dopiero można pomyśleć o optymalizacji.

0
Garniturek napisał(a):

przy większych program wywala.

Zawsze kiedyś wywali. Zrób na BigInteger buaha :D

0

Poczytaj o symbolu Newtona

1

Jest takie ograniczenie aby wynik nie przekroczył 1000 000 000(10^9), czyli nie ma problemu ze zmieszczeniem wyniku w zmiennej liczbowej. Pierwsza mśl to jest taka, że kiedy oblicza się dwumian newtona to zawsze dobrze się skraca(tu przydaje się tradycyjna matma i nieco doświadczenia w niej) Np. Kiedy masz wyznaczyć liczbę 2-elementowych zbiorów ze zbioru 1000 elementów to wzór to 1000!/2!998! co uprości się do (1000999)/2! i łatwo to zaprogramować. Ale już dla liczb 1000 i 500 nie będzie tak różowo, zostaną nadal duże liczby wiec odpada, przynajmniej ciężko to zrealizowac. Jednak dwumian newtona ma inna ciekawa zależność, która tu chyba sie przyda. Otoż jego wartosci układają się w tzw. trójkąt Pascala, ktorego wartości można wyznaczyć rekurencyjnie jednocześnie mając pewność, że nie wyjdziesz poza zakres.

5

Należy na zmianę dzielić i mnożyć (nie liczyć silni). Np. C(13,6) = ((((13/1)*12)/2)*11)/3...

1
bogdans napisał(a):

Należy na zmianę dzielić i mnożyć (nie liczyć silni). Np. C(13,6) = ((((13/1)*12)/2)*11)/3...

Aby zoptymalizować jeszcze można ewentualnie wybrać mniejszą z liczb k i n-k i w zależności od tego liczyć Twoją metodą C(n,k) lub C(n,n-k)

2

Pop pierwsze niech zacznie od napisania osobnej funkcji:

unsigned int NewtonSymbol(unsigned int n, unsigned int m) {
    …
}

Pakowanie wszystkiego do main to duży problem i im szybciej się tego oduczy tym lepiej.

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