[C++] Liczba Catalana

[blackbird936]

Co tu nie gra ?

Kod: Zaznacz cały

#include <iostream>
#include <conio.h>
using namespace std;

int catalan(int n)
{
    if (n==0 || n==1)
        return 1;
    else
    {
        int x=0;
        for(int i=0;i<n-1;i++)
            x=x+(catalan(i)*catalan(n-1-i));
        return x;
    }
}
int main()
{
    cout << "Liczba Catalana" << endl;
    cout<<"Podaj liczbe"<<endl;
    int n;
    cin>>n;
    cout<<catalan(n)<<endl;

    getch();
    return 0;
}

[Ser Cubus]

na przyszłość, pisz jaki masz błąd ...

zgaduję, że chodzi o bibliotekę
zamiast #include <conio.h> wstaw #include <cstdlib>
zamiast getch() wstaw system("pause")

[blackbird936]

na przyszłość, pisz jaki masz błąd ...

zgaduję, że chodzi o bibliotekę
zamiast #include <conio.h> wstaw #include <cstdlib>
zamiast getch() wstaw system("pause")

Z biblioteką akurat w porządku. Dziwne wyniki podaje

[93Michu93]

W pętli liczysz \(\displaystyle{ i}\) do \(\displaystyle{ n-2}\), a powinieneś do \(\displaystyle{ n-1}\).
Zmień warunek na \(\displaystyle{ i<n}\)

[blackbird936]

nie, bo wtedy jest jeszcze gorzej

[93Michu93]

Kod: Zaznacz cały

#include <iostream>
using namespace std;

int catalan(int n)
{
	int i;
	int wynik=0;
    if (n==0 || n==1)
    {
    	wynik=1;
    }
    else
    {
        for(i=0;i<n;i++)
            wynik=wynik+(catalan(i)*catalan(n-1-i));
    }
    return wynik;
}
int main()
{
    cout << "Liczba Catalana" << endl;
    cout<<"Podaj liczbe"<<endl;
    int n;
    cin>>n;
    cout<<catalan(n)<<endl;

    return 0;
}

wyniki takie jak na wikipedii, pamiętaj, że liczysz wyrazy od \(\displaystyle{ 0}\).

[zeus_156]

Jako, że korzystasz z wzoru \(\displaystyle{ C_{n}=\sum_{i=0}^{n-1} C_{i} \cdot C_{n-1-i}}\) w pętli for musisz też uwzględnić element kiedy zmienna \(\displaystyle{ i}\) jest równa \(\displaystyle{ n-1}\).
Dlatego ta linijka powinna wyglądać tak for(int i=0; i<=n-1; i++). Taki zapis poprawi czytelność kodu, szczególnie jeżeli kod piszesz na zaliczenie.

Dokładnie ten sam temat został omówiony tu: https://www.matematyka.pl/341747.htm
Znajdziesz tam parę wskazówek jak przyspieszyć wykonywanie tego kodu (zawiera pełen kod).

[adri@n]

Podaję przykładowy działający algorytm:

Kod: Zaznacz cały

#include <iostream>

using namespace std;

int catal(int n)
{
    if(n==0)
        return 1;
    int suma=0;
    for(int i=0;i<=n-1;i++)
        suma=suma+catal(i)*catal(n-i-1);
    return suma;
}
int main()
{
    int a;
    cout << "Podaj indeks dla którego chcesz obliczy wartoœc liczby Catalana = Cn." << endl;
    cout << "Wprowadz n = ";
    cin >> a;
    cout << "Liczba Catalana dla podanego indeksu n = "<<a<< " wynosi: "<<catal(a);
        return 0;
}

Może się komuś przyda, bo jest z deklaracją funkcji