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

Silnia int

2015-09-22 14:42
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;
}
podałeś chyba zły link do zadania - stryku 2015-09-22 15:03

Pozostało 580 znaków

2015-09-22 14:46
0

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

Pozostało 580 znaków

2015-09-22 14:58
0

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

@Shalom to jest celowe wprowadzanie w blad (komentarz powyzej) - fasadin 2015-09-22 15:26
@fasadin niestety, to głupota w czystej postaci ;) - Shalom 2015-09-22 15:27

Pozostało 580 znaków

2015-09-22 14:58
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.

Pozostało 580 znaków

2015-09-22 15:20
Krwawy Szczur
0
Garniturek napisał(a):

przy większych program wywala.

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

Pozostało 580 znaków

2015-09-22 15:46
0

Poczytaj o symbolu Newtona

Pozostało 580 znaków

2015-09-22 15:54
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.

Pozostało 580 znaków

2015-09-22 16:01
5

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


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2015-09-22 16:04
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)

Masz rację. - bogdans 2015-09-22 16:08

Pozostało 580 znaków

2015-09-22 21:18
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.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.

Pozostało 580 znaków

2015-09-22 21:54
0

Okej, mam coś takiego. Spoj mi wyrzuca, błąd "Przekroczenie limitu czasowego". Jakieś pomysły lub uwagi nie dotyczące nawet tego problemu tylko ogólnie programu?

#include <iostream>
using namespace std;
int f(int m, int n)
{
    if(n==0 || n==m)return 1;
    else if (n>0 && m>0 && m>n)
        return f(m-1, n-1) + f(m-1, n);
}
int main()
{
    int liczbaprob;
    cin>>liczbaprob;
    for(int i=0; i<liczbaprob; i++)
    {
     int n;
  int m;
 cin >>m;
 cin>>n;
cout<<f(m, n)<<endl;
    }
    return 0;
}

Pozostało 580 znaków

Liczba odpowiedzi na stronę

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