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;
}if(n==0 and n==1)if(n==0 or n==1) ?RaczejSer Cubus pisze:if(n==0 and n==1)
nie miało byćif(n==0 or n==1)?
Kod: Zaznacz cały
if(n==0 || n==1)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;
}Kod: Zaznacz cały
int catalan(int n)
{
if(n <= 1) return 1;
return catalan(n-1) * 2 * (2 * n - 1) / (n + 1);
}przecież obie formy są poprawne...bartek118 pisze:RaczejSer Cubus pisze:if(n==0 and n==1)
nie miało byćif(n==0 or n==1)?Kod: Zaznacz cały
if(n==0 || n==1)
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;
}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);
}Wszystko rozumiem oprocz polecenia output.Czy jest to jak tablica czy polecenie ?Pierwszy raz sie z nim spotykam w jezyku c++.zeus_156 pisze: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:Czas wykonania jest oczywiście obłędnie długi. Przydało by się zastosować zbieranie już wyliczonych danych w tablicy lub skorzystać z innego wzoruKod: 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; }
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); }
output w tym przypadku to po prostu nazwa zmiennej - przechowuje ona wynik sumowania w trakcie liczenia.Majka99 pisze:Wszystko rozumiem oprocz polecenia output.Czy jest to jak tablica czy polecenie ?Pierwszy raz sie z nim spotykam w jezyku c++.zeus_156 pisze: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:Czas wykonania jest oczywiście obłędnie długi. Przydało by się zastosować zbieranie już wyliczonych danych w tablicy lub skorzystać z innego wzoruKod: 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; }
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); }
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;
}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;
}