Silnia int

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;
}

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

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

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.

Garniturek napisał(a):

przy większych program wywala.

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

Poczytaj o symbolu Newtona

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.

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

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)

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.

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;
}
 

Rekurencja to nie jest dobry pomysł. Weź do ręki kartkę i sprawdź ile razy liczysz TE SAME elementy.

Obliczanie symbolu Newtona przy pomocy prostej rekurencji (tzn. bez zapamiętywania obliczonych "po drodze" wartości) sprowadza się do dodawania jedynek. Musisz się zatem liczyć z tym, że Twój program będzie dodawał miliard jedynek. Napisałem, że należy naprzemienne dzielić i mnożyć, masz kod w Javie, przerób na C++.

    private long symbolNewtona(int n,int k)
    {
        if(k > n/2)
        {
            k = n-k;
        }
        long wynik = 1L;
        int m = 1;
        for(int i=n;i>n-k;i--)
        {
            wynik*=i;
            wynik/=m;
            m++;
        }
        return wynik;
    }

użyj stirlinga, głupku...

albo licz tak:
ln n! = ln2 + ln3 + .. lnn;

i dopiero teraz: n! = exp(ta suma);

Mam coś takiego, proszę o podpowiedź co dalej

 #include <iostream>
using namespace std;
    long int symbolNewtona(int n,int k)
    {
        if(k > n/2)
            k = n-k;
    
        long int wynik;
        int m = 1;
        for(int i=n; i>n-k; i--)
        {
            wynik=wynik * i;
            wynik=wynik/m;
            m++;
        }
        return wynik;
    }
int main()
{
    int liczbaprob;
    cin>>liczbaprob;
    for(int i=0; i<liczbaprob; i++)
    {
     int n;
  int k;
 cin >>n;
 cin>>k;
cout<<symbolNewtona(n, k)<<endl;
    }
    return 0;
}

Ja bym ten program napisał tak http://skroc.uk/bFiMj

masz głupku:

double npok(double nf, double kf)
{
  int n = nf+0.5f, k = kf+0.5f;

  if( n <= 0 || n < k ) return 0;

  if( k < n-k ) k = n-k;

  double l = 1, m = 1;         // 8 6 ->
  for(int i = n-k; i > 0; i--) // i = 2 1
    {                          // k = 7 8
      l *= ++k;
      m *= i;
    }

  return l/m;
}

A o co chodzi z

 int n = nf+0.5f, k = kf+0.5f

, jaki to dział wiedzy, bo nie mam o tym sposobi pojęcia?

A więc mam taki kod. Spoj cały czas wyrzuca błędną odpowiedź, pomocy!

#include <iostream>
using namespace std;
double npok(double nf, double kf)
{
  int n = nf+0.5f, k = kf+0.5f;

  if( n <= 0 || n < k ) return 0;

  if( k < n-k ) k = n-k;

  double l = 1, m = 1;    
  for(int i = n-k; i > 0; i--) 
    {               
      l *= ++k;
      m *= i;
    }

  return l/m;
}
int main()
{
    int liczbaprob;
    cin>>liczbaprob;
    for(int i=0; i<liczbaprob; i++)
    {
     int n;
  int m;
 cin >>m;
 cin>>n;
if(m==0 && n==0)
    cout <<"1"<<endl;
else
cout<<npok(m, n)<<endl;
    }
    return 0;
}
 

Bo słuchasz kogoś, kogoś kto tylko epitetami dobrze rzuca. Zignoruj tłusty łysy byk.
Krzywy Kot dał już prawidłowe rozwiązanie (jest mały błąd, który kompilator wykrywa, warring).

MarekR22 napisał(a):

Bo słuchasz kogoś, kogoś kto tylko epitetami dobrze rzuca. Zignoruj tłusty łysy byk.
Krzywy Kot dał już prawidłowe rozwiązanie (jest mały błąd, który kompilator wykrywa, warring).

Amator jesteś...

n po k = n!/k!(n-k)!

i teraz należy to wyliczyć - minimalnym kosztem!

zatem co z tym robimy?
skracamy zwyczajnie:

n!/k!(n-k)! = (k+1)(k+2)... / (n-k)(n-k-1) ...

ale ponieważ to jest symetryczne, tz.: n po k = n po (n-k),
np.:
5 po 2 = 120 / 26 = 10;
oraz:
5 po 3 = 120 / 62 = 10;

zatem stąd tam ten skecz z warunkiem: k < n-k ...
bo wtedy zawsze mnożymy mniej... zatem szybciej, no i większy zakres łapiemy.

100 po 98 = 100 po 2,
zatem co wybieramy - co łatwiej obliczać?

oczywiście że:
99100 / 2, zamiast: 3456*7 ...100 / 123...98;
..............

no ale ty przecież pojedziesz jeszcze gorzej, bo tak:
123 ... 100 / 12 * 12*...98;
co nie? :)

Ja pisałem jako Krzywy Kot, bo zapomniałem się zalogować na konto.
Jak myślicie co jest źle w tym programie, że mi wyrzuca błąd. Teraz jestem poza domem, więc nawet kompilatora nie odpalę. Proszę o pomoc, bo jak już zauważyliście moje umiejętności nie są na wysokim poziomie - dopiero się uczę, a to podcina skrzydła taka bezradność.

  #include <iostream>
using namespace std;
    long int symbolNewtona(int n,int k)
    {
        if(k > n/2)
            k = n-k;
 
        long int wynik;
        int m = 1;
        for(int i=n; i>n-k; i--)
        {
            wynik=wynik * i;
            wynik=wynik/m;
            m++;
        }
        return wynik;
    }
int main()
{
    int liczbaprob;
    cin>>liczbaprob;
    for(int i=0; i<liczbaprob; i++)
    {
     int n;
  int k;
 cin >>n;
 cin>>k;
cout<<symbolNewtona(n, k)<<endl;
    }
    return 0;
}

skoro masz internet to wejdz na www.ideone.com i zobacz tam jak dziala

jak pisałem kod od Kota (twój) ma mały błąd, który kompilator wykrywa. Liczyłem na to, że sam znajdziesz ten mały błąd, zwłaszcza, że kompilator cię o tym ostrzega.
Problemem jest nieznacjonalizowana zmienna.
Byk niby zrobił to samo, ale przekombinował stosując typ zmiennoprzecinkowy, bo nie zrozumiał podpowiedzi od @bogdans http://4programmers.net/Forum/1177999 i to był dla niego jedyny sposób rozwiązania problemu z dużymi wartościami. Nawet jak widzi kod od kota (ciebie) to nadal nie rozumie na czym polega jego błąd (ale zarozumiałości mu nie brakuje i śmiało rozdaje epitety).

Jest tu wielu,, którzy mogli ci dać gotowe rozważanie), ale lepiej jeśli będziemy cię naprowadzać na źródło problemu, a nie dawać gotowe rozwiązanie, bo więcej się nauczysz.
W tym duchu udzielił odpowiedzi Bogdans.

Mam program, który wedle mnie jest napisany dobrze. Na stronie ideone.com, wyświetla się "sukces", ale Spoj cały czas "Błędna odpowiedź", proszę o podpowiedź gdzie się ukrył ten diabełek!

   #include <iostream>
using namespace std;
    long int symbolNewtona(int n,int k)
    {
        if(k > n/2)
            k = n-k;

        long int wynik=1;
        for(int i=1; i<=k; i++)
        {
            wynik=wynik * (n - i + 1);
            wynik=wynik/i;

        }
        return wynik;
    }
int main()
{
    int liczbaprob;
    cin>>liczbaprob;
    for(int i=0; i<liczbaprob; i++)
    {
     int n;
  int k;
 cin >>n;
 cin>>k;
cout<<symbolNewtona(n, k)<<endl;

    }
    return 0;
}

Zmień long int na long long, pewnie w jakimś momencie wychodzi poza zakres

Tak jest!
Spoj przyjął program, wielki dzięki za pomoc! Jak znacie sposób w jaki mógłbym wam się odwdzięczyć to piszcie :)
Odezwę się niebawem z kolejnym problem. Stay tuned!

Możesz się odwdzieczac klikajac kciuki do góry :)

Poklikane :)

za dużo się podniecasz, przeczytałeś co zrobił Krzywy Kot i czym się to rożni od tego co ty napisałeś? Twoja odpowiedź dowodzi, że nie. Kod od Kota robi dokładnie to samo (może nie najładniej), ale prawidłowo, a twój kod źle i dlatego autorowi wątku twój kod nie przechodzi na SPOJu. Może SPOja jeszcze obrzuć epitetami bonie akceptuje twojego kodu. - MarekR22 dzisiaj, 09:56

Na jakim SPOJu nie przechodzi?
Pewnie jest za dobry... hihi!

Aha! To chyba bez floatów ma być - tak?

Będzie znacznie gorsze - zakres mniejszy, no ale masz:

int npok(int n, int k)
{
if( n <= 0 || n < k ) return 0;

if( k < n-k ) k = n-k;

int l = 1, m = 1;
for(int i = n-k; i > 0; i--)
{
l *= ++k;
m *= i;
}

return l/m;
}

powinno działać..