[C++] Obliczanie wzoru Catalana

[Majka99]

Kod: Zaznacz cały

#include <iostream>

using namespace std;

int catalan(int n)
{  

	if(n==0 and n==1)
	return 1;
	for(int i=0;i<=n;i++)

	
	return catalan(i)*catalan(n-1)+catalan(n);
}




int main(int argc, char** argv) {
	
	int n;
	cin>>n;
	cout<<catalan(n)<<endl;
	return 0;
}

Mam cos takiego,lecz nie dziala,gdzie blad ?

[Ser Cubus]

if(n==0 and n==1)

nie miało być if(n==0 or n==1) ?

[bartek118]

if(n==0 and n==1)

nie miało być if(n==0 or n==1) ?

Raczej

Kod: Zaznacz cały

if(n==0 || n==1)

[Afish]

W pętli kręcisz się tylko raz i od razu zwracasz wynik, raczej nie o to chodziło. Podaj dokładnie wzór, według którego chcesz obliczać, bo na wiki jest inny.

bartek118, literały słowne są w C++.

[Majka99]

\(\displaystyle{ C_{n+1} = C_0C_n + C_1C_{n-1} + . . . + C_{n-1}C_1 + C_nC_0}\)

[bartek118]

Myślę, że jeśli z tego typu wzoru liczysz, to najlepiej tablicować wynik (chyba, że \(\displaystyle{ n}\) ma być jakieś bardzo duże, to wtedy jeśli masz ograniczenie na pamięć to warto pomyśleć nad czymś sprytniejszym. Rekurencja napisana tak ot wprost będzie wysoce nieefektywna.

[Afish]

No to masz źle pętlę oraz warunek stopu, jak już Ser Cubus wspomniał.

[zeus_156]

Wzór który podałaś jest na \(\displaystyle{ C_{n+1}}\)
Zapisując to dla \(\displaystyle{ C_{n}}\) (bo właśnie tak wykorzystujesz w programie) otrzymujemy:
\(\displaystyle{ C_{n}=\sum_{i=0}^{n-1} C_{i} \cdot C_{n-1-i}}\)
to funkcja powinna wyglądać tak:

Kod: Zaznacz cały

int catalan(int n)
{ 
   int output = 0;
   if(n <= 1) return 1;
   for(int i=0; i<=n-1; i++) 
   {
      output += catalan(i) * catalan(n-1-i);
   }
   return output;
}

Czas wykonania jest oczywiście obłędnie długi. Przydało by się zastosować zbieranie już wyliczonych danych w tablicy lub skorzystać z innego wzoru
np: \(\displaystyle{ C_{n}=\frac{2(2n-1)}{n+1} C_{n-1}}\) to funkcja powinna wyglądać tak:

Kod: Zaznacz cały

int catalan(int n)
{ 
   if(n <= 1) return 1;
   return catalan(n-1) * 2 * (2 * n - 1) / (n + 1);
}

[Ser Cubus]

if(n==0 and n==1)

nie miało być if(n==0 or n==1) ?

Raczej

Kod: Zaznacz cały

if(n==0 || n==1)

przecież obie formy są poprawne...

[zeus_156]

Dla większych wartości (dla pierwszego wzoru \(\displaystyle{ n>=20}\), dla drugiego wzoru \(\displaystyle{ n>=17}\)) dobrze by zastosować zmienne 64 bitowe.
Wtedy będzie to wyglądać tak:

Kod: Zaznacz cały

unsigned long long catalan(int n)
{ 
   unsigned long long output = 0;
   if(n <= 1) return 1;
   for(int i=0; i<=n-1; i++) 
   {
      output += catalan(i) * catalan(n-1-i);
   }
   return output;
}

lub:

Kod: Zaznacz cały

unsigned long long catalan(int n)
{ 
   if(n <= 1) return 1;
   return catalan(n-1) * 2 * (2 * n - 1) / (n + 1);
}

Działanie kodu sprawdziłem na Visual Studio 2008.

[Majka99]

Wzór który podałaś jest na \(\displaystyle{ C_{n+1}}\)
Zapisując to dla \(\displaystyle{ C_{n}}\) (bo właśnie tak wykorzystujesz w programie) otrzymujemy:
\(\displaystyle{ C_{n}=\sum_{i=0}^{n-1} C_{i} \cdot C_{n-1-i}}\)
to funkcja powinna wyglądać tak:

Kod: Zaznacz cały

int catalan(int n)
{ 
   int output = 0;
   if(n <= 1) return 1;
   for(int i=0; i<=n-1; i++) 
   {
      output += catalan(i) * catalan(n-1-i);
   }
   return output;
}

Czas wykonania jest oczywiście obłędnie długi. Przydało by się zastosować zbieranie już wyliczonych danych w tablicy lub skorzystać z innego wzoru
np: \(\displaystyle{ C_{n}=\frac{2(2n-1)}{n+1} C_{n-1}}\) to funkcja powinna wyglądać tak:

Kod: Zaznacz cały

int catalan(int n)
{ 
   if(n <= 1) return 1;
   return catalan(n-1) * 2 * (2 * n - 1) / (n + 1);
}

Wszystko rozumiem oprocz polecenia output.Czy jest to jak tablica czy polecenie ?Pierwszy raz sie z nim spotykam w jezyku c++.

[bartek118]

Wzór który podałaś jest na \(\displaystyle{ C_{n+1}}\)
Zapisując to dla \(\displaystyle{ C_{n}}\) (bo właśnie tak wykorzystujesz w programie) otrzymujemy:
\(\displaystyle{ C_{n}=\sum_{i=0}^{n-1} C_{i} \cdot C_{n-1-i}}\)
to funkcja powinna wyglądać tak:

Kod: Zaznacz cały

int catalan(int n)
{ 
   int output = 0;
   if(n <= 1) return 1;
   for(int i=0; i<=n-1; i++) 
   {
      output += catalan(i) * catalan(n-1-i);
   }
   return output;
}

Czas wykonania jest oczywiście obłędnie długi. Przydało by się zastosować zbieranie już wyliczonych danych w tablicy lub skorzystać z innego wzoru
np: \(\displaystyle{ C_{n}=\frac{2(2n-1)}{n+1} C_{n-1}}\) to funkcja powinna wyglądać tak:

Kod: Zaznacz cały

int catalan(int n)
{ 
   if(n <= 1) return 1;
   return catalan(n-1) * 2 * (2 * n - 1) / (n + 1);
}

Wszystko rozumiem oprocz polecenia output.Czy jest to jak tablica czy polecenie ?Pierwszy raz sie z nim spotykam w jezyku c++.

output w tym przypadku to po prostu nazwa zmiennej - przechowuje ona wynik sumowania w trakcie liczenia.

[zeus_156]

Nazwę zmiennej tymczasowej możesz sobie dowolnie wybrać np: x

Kod: Zaznacz cały

int catalan(int n)
{ 
   int x = 0;
   if(n <= 1) return 1;
   for(int i=0; i<=n-1; i++) 
   {
      x += catalan(i) * catalan(n-1-i);
   }
   return x;
}

Jeżeli chcesz zbierać w tablicy wyniki obliczeń pośrednich to program będzie wyglądał tak:

Kod: Zaznacz cały

#include <iostream>

using namespace std;

//Przy 32 bitowym typie dany i tak bedzie tylko 20 elementow  
int tablicaWynikow[50] = {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; 

int catalan(int n)
{ 
   int x = 0; //Inicjacja zmiennej tymczasowej
   if(n>=0 && n<50)  //Zabezpieczenie aby nie czytac pamieci poza tablica
   {
      if(tablicaWynikow[n] > 0) return tablicaWynikow[n]; //Wynik byl juz raz wyliczony, wiec go uzyj
      for(int i=0; i<=n-1; i++) 
      {
         x += catalan(i) * catalan(n-1-i);
      }
      //Jak nastapi przepelnienie zmiennej to wynik dodawania bedzie ujemny
      if(x < 1) throw "Przekroczono zakres wartosci jaki moze zawierac typ int!";
      tablicaWynikow[n] = x;  //Zapisz wynik dla aktualnej n-tej warosci Catalana
   }
   return x;
}

int main(int argc, char** argv)
{
   int n;
   cin>>n;
   try {
      cout<<catalan(n)<<endl;
   }
   catch(char * str) {
      cout << "Exception raised: " << str << '\n';
   }
   return 0;
}

Sama oceń jak bardzo tablicowanie wyników pośrednich przyspieszyło obliczenia.