Program obliczajacy wartosc symbolu Newtona.

0

Witam.
Mam problem z tym programem. Po wpisaniu zmiennych spełniających warunek program zawiesza się. Proszę o rzucenie okiem i porady ;) Oto kod:

#include <iostream>

using namespace std;

int n,k,a,b,c,x,y,z,i;

int main()
{
    cout<<"\t\tProgram do obliczania wartosci symbolu Newtona.Warunek: o<k<n \n\n";
    cout<<"\t\t\n\nPodaj wartosc zmiennej n : ";
    cin>>n;

    while(n<0)
    {
        cout<<"\t\tZmienna n nie moze byc mniejsza od zera, podaj inna liczbe!";
        cin>>n;
    }

    cout<<"\t\t\n\nPodaj wartosc zmiennej k : ";
    cin>>k;

    while(k<0)
    {
        cout<<"\t\t\n\nZmienna k nie moze byc mniejsza od zera, podaj inna liczbe!";
        cin>>k;
    }

    while(n<k ||n<0||k<0)
    {
        cout<<"\t\t\n\nPodales zmienne ktore sa niezgodne z warunkiem podanym na poczatku. Wprowadz inne zmienne !";
        cout<<"\t\tPodaj n:";
        cin>>n;
        cout<<"\t\tPodaj k:";
        cin>>k;
    }

    if(k==0)
    {
        cout<<"\t\tWartosc n nad k wynosi 1 !";
    }
    if(k==n)
    {
        cout<<"\t\tWartosc n nad k wynosi 1 !";
    }
    else
    {
        if(n == 0)
        {
            a=1;

            b = k;
            for( i = k; k != 1; k = i-1)
            {
                y=y*(k-1);
                k=k-1;
            }
            b=y;

            c = n-k;

            for( i = c; c != 1; i = i-1)
            {
                z=z*(c-1);
                c = c-1;
            }
            c=z;


            cout<<"Przy podanych wspolczynnikach dwumian Newtona przyjmuje wartosc rowna: "<<(a)/(b*c);



        }
        else
        {
            a = n;
            for( i = n; n != 1; i = i-1)
            {
                x=x*(n-1);
                n=n-1;
            }
            a=x;

            b = k;
            for( i = k; k != 1; k = i-1)
            {
                y=y*(k-1);
                k=k-1;
            }
            b=y;

            c = n-k;
            for( i = n-k; n-k != 1; i = i-1)
            {
                z=z*(n-k-1);
                c = c-1;
            }
            c=z;


            cout<<"Przy podanych wspolczynnikach dwumian Newtona przyjmuje wartosc rowna: "<<(a)/(b*c);




        }
    }
    return 0;

}
 
0
  1. Dowiedz się jak najszybciej co to są funkcje.

  2. Jak użyjesz debuggera to od razu się dowiesz co jest nie tak ;-)

for( i = k; k != 1; k = i-1)
            {
                y=y*(k-1);
                k=k-1;
            }

Zastanów się nad tym kawałkiem i podobnymi, przeanalizuj krok po kroku.
4.

 int n,k,a,b,c,x,y,z,i;

Koniecznie musisz je globalnie dawać? Wrzuć do maina i zainicjuj każdą lepiej, bo wydaje mi się, że w wypełniając je zerami masz potem odlot przy y=y*(k-1);

0

n może być ujemne, a nawet nie calkowite

przyklad obliczen
{8\choose 3} = 8/1<em>7/2</em>6/3
nie sprytniej?

0
       if(n == 0)
        {
// (...)
        }
        else
        {
// (...)
        }

Po co to rozgraniczenie? Niepotrzebnie, liczyć się będzie zawsze tak samo. Nie powtarza się prawie identycznego kodu w różnych miejscach. wystarczy zamienić n z k miejscami.

Również trzeba wykorzystać, że:
{n\choose k} = {n\choose {n-k}}
czyli np.
{8\choose 5} = {8\choose 3} = \frac{8}{1} \cdot \frac{7}{2} \cdot \frac{6}{3}

Tak więc jako 'k' w rzeczywistości należy przyjąć min(k, n - k). Jak pokazaliśmy wystarczy użyć jednej pętli. Zauważ, że będą dwa indeksy, jeden będzie maleć a drugi rosnąć. Musisz tylko obliczyć od jakich wartości wystartują i na jakich się skończą.

0

Trochę się nudzę.

        if(k>n/2)
        {
            k=n-k;
        }
        long wynik=1;
        int m=1;
        for(int i=n;i>n-k;i--)
        {
            wynik*=i;
            wynik/=m;
            m++;
        }
0

Symbol Newtona można policzyć używając tylko dodawania. Dzięki temu unika się dużych liczb i liczenie jest dramatycznie szybsze:

http://pl.wikipedia.org/wiki/Tr%C3%B3jk%C4%85t_Pascala

0

Skąd masz tę całkowicie nieprawdziwą informację o szybkości dodawania?
C(34,17) = 2333606220
Czas obliczen - rekurencja z zapamietywaniem (w ms): 1.8137729999999999
Ilosc wywolan: 187
C(34,17) = 2333606220
Czas obliczen - rekurencja bez zapamietywania (w ms): 49609.369007
Ilosc wywolan: 4667212439
C(34,17) = 2333606220
Czas obliczen - naprzemienne dzielenie mnozenie (w ms): 0.06759899999999999

0

Zwykła rekurencja:

    private long Newton(int n,int k)
    {
        licznik2+=1;
        if(k>n/2)
        {
            k=n-k;
        }
        if(k==0)
        {
            return 1;
        }
        return Newton(n-1,k-1)+Newton(n-1,k);
    }

Rekurencja z zapamiętywaniem wyników:

private Hashtable<Point,Long> wyniki=new Hashtable<Point,Long>();
...
    private long Newton(int n,int k)
    {
        if(k>n/2)
        {
            k=n-k;
        }
        licznik1++;
        if(k==0)
        {
            return 1;
        }
        Point p=new Point(n-1,k-1);
        long a=0;
        if(wyniki.get(p)==null)
        {
            a=Newton(n-1,k-1);
            wyniki.put(p,a);
        }
        else
        {
            a=wyniki.get(p);
        }
        p=new Point(n-1,k);
        long b=0;
        if(wyniki.get(p)==null)
        {
            b=Newton(n-1,k);
            wyniki.put(p,b);
        }
        else
        {
            b=wyniki.get(p);
        }
        return a+b;
    }
0
bogdans napisał(a)

Nie, sposób skrócony jest dokładny. Algorytm z dodawaniem jest sensowny gdy potrzebujesz cały trójkąt Pascala, dla pojedynczego symbolu Newtona jest zły.

Sprawdziłem, masz rację. Jakimś cudem w tej metodzie nie ma zaokrągleń, nie zagłębiałem się w podstawy matematyczne, więc zwracam honor.
Poniżej metoda z Trójkątem Pascala - podaję nie żeby udowodnić że jest szybszy, tylko żeby nie było że się nie da...
Poza tym przepełnia się trochę później niż metoda "skrócona" (która nie daje rady już przy 100/10 przy 32 bitach).

// binomial coefficient / symbol newtona (Trojkat Pascala)
#include <iostream>
#include <vector>

using namespace std;

int main() {
  typedef unsigned int uint;
  uint n = 34;
  uint k = 17;
  uint wynik;
  uint osize = 1;
  uint col;

  vector<uint> vect;

  if(k>n/2)
  {
      k=n-k;
  }

  vect.resize(1);
  vect[0] = 1;
  for(uint row=1; row <= n; row++)
  {
    if (row % 2 == 0) {
      vect.resize(vect.size()+1);
      col = vect.size()-1;
      vect[col] = 2 * vect[col-1];
    }
    for(col = osize - 1; col >= 1; col--)
      vect[col] = vect[col] + vect[col-1];
    osize = vect.size();
  }

  wynik = vect[k];

  cout << "Wynik (" << n << " po " << k << ") = " << wynik << endl;
  return 0;
}
0

To że metoda skrócona wcześniej nie daje rady jest oczywiste. Przy dodawaniu wszystkie wyniki pośrednie są mniejsze od końcowego. Wystarczy więc by C(n,k) mieściło się w wybranym typie. Przy algorytmie skróconym ostatnią operacją jest dzielenie przez k, zatem konieczne jest by również k*C(n,k) mieściło się w wybranym typie.

0
Xitami napisał(a)

dziedzina w totolotkowym zakresie

Dla porównania - wersja dla Trójkąta Pascala:
http://ideone.com/JBnC6

(robione na szybko)

Wersja 1.2 - po uwzględnieniu pomysłów z komentarzy i dodaniu kilku prawdopodobnie zbędnych walidacji:
http://ideone.com/MySek

0

a może policzymy dla gigalotka, powiedzmy - zakład ma 10000 liczb

ideone, 5 sekund, wyświetlić binomial[2n,n], wygrywa większe n
(java v C może być kłopot)

0

@Xitami, jestem prz komputerze, który nie pamięta mojego hasła. Dziwne jest to, że program @vpiotra (korzystający z 8-bajtowego typu unsigned) już dla n==34 zawodzi.

0

policzyłem binomial(2*46200, 46200) z wyświetleniem 4.98 sekundy (52 wiersze C)

0

binom(44090*2,44090), Java, czas = 5 sekund (obliczenia i wypisanie), 28 wierszy w tym 6 zawierających tylko klamerkę.

0

{2\cdot100'000\choose 100'000}=178056...350784 60'204 cyfry, 4.98 sek.

0

Zainteresowało mnie pytanie: jak liczyć symbole Newtona. W wyścigach z @xitamim (Twój nick się odmienia?) nie mam szans, więc ograniczyłem się do porównania czterech sposobów:
A) multyplikatywny (C(n,k)=((n/1)*(n-1))/2...,
B) prosta rekurencja (C(n,k)=C(n-1,k-1)+C(n-1,k)),
C) rekurencja z zapamiętywaniem, (sprawdź w magazynie czy jest w nim C(n,k), jeśli jest to pobierz z magazynu, jeśli nie, to oblicz korzystając z rekurencji i dodaj do magazynu)
D) tworzenie częściowego trójkąta Pascala - w każdym wierszu liczymy tylko wyrazy do indeksu k.
Podsumowanie:
używanie B) powinno być prawnie zakazane,
D) jest kilkakrotnie szybszy od C),
A) i D) mają podobne czasy wykonania, w pobliżu wierzchołka trójkąta Pascala szybszy jest D), potem górę bierze A), przy ograniczonych typach całkowitych (int, long, long long,...) w sposobie A) trochę wcześniej (tzn. dla trochę mniejszych k,n) następuje przepełnienie.

0

z pomocą kolegi Legendre'a troszkę poprawiłem wynik - C(200'000, 100'000) mam policzone w 0.02 sek. :) ale jako rozkład na iloczyn potęg liczb pierwszych, tak by pokazać strawny wynik potrzebuję aż 0.25 sek.
Przyjąłem, że liczę w pozycyjnym układzie o podstawie 10'000, czyli mogę liczyć C(n, k) dla (około) n<(2^32-1)/10000=429496
I tak C(429480,214740) policzyłem w 1.03 sek.

0

Moje wyniki:

    Newton Data:	(4, 1)  	(4, 2)  	(5, 2)  	(34, 17)	(36, 18)
         MulDiv:	0.000015	0.000038	0.000038	0.00024 	0.00028
Pascal (vpiotr):	0.00011 	0.00010 	0.00012 	0.0010  	0.0011
    Pascal (Ja):	0.000020	0.000021	0.000024	0.00070 	0.00079

Wyniki w milisekundach przez uśrednione po wywołaniu w pętli (użyłem QTestLib), GCC Linux (laptop Lenovo T410).
Wielkich liczb nie chciało mi się robić.

0

dla małych liczb (gdy C(n,k) < MAX_INT) poza rekurencją każda metoda dobra
gdy liczby większe przydałaby się pomoc Karatsuby i Fouriera

a tak żeby się zapamiętało i może komu się przyda http://ideone.com/8nk5e

0

Wersja trochę bardziej podrasowana pod względem wydajności:
http://ideone.com/uAUR7

Można by jeszcze usunąć warunek

if (row % 2 == 0)

, ale chyba szkoda prądu.

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