Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #define NMax 1000
- using namespace std;
- typedef short Huge[NMax+3];
- void AtribValue(Huge H,short X) {
- H[0] = 0;
- while (X) {
- ++H[0];
- H[H[0]] = X % 10;
- X /= 10;
- }
- }
- void Mult(Huge H,short X)
- /* H <- H*X */
- {short i,T=0;
- for (i=1;i<=H[0];i++)
- { H[i]=H[i]*X+T;
- T=H[i]/10;
- H[i]=H[i]%10;
- }
- while (T) /* Cat timp exista transport */
- { H[++H[0]]=T%10;
- T/=10;
- }
- }
- void Divide(Huge A,short X)
- /* A <- A/X si intoarce A%X */
- { short i,R=0;
- for (i=A[0];i;i--)
- { A[i]=(R=10*R+A[i])/X;
- R%=X;
- }
- while (!A[A[0]] && A[0]>1) A[0]--;
- }
- void Afisez(Huge H)
- {
- for(short i=H[0];i>0;--i)
- cout<<H[i];
- cout<<'\n';
- }
- void catalan(unsigned int n,unsigned int k) /// Folosesc coeficientii binomiali
- {
- Huge res;
- AtribValue(res,1);
- if(k>n-k) /// C(n, k) = C(n, n-k)
- k=n-k;
- for(unsigned int i=0;i<k;++i) /// Calculez valoarea [n*(n-1)*---*(n-k+1)]/[k*(k-1)*---*1]
- {
- Mult(res,n-i); /// res*=n-i
- Divide(res,i+1); /// res/=(i+1)
- }
- Divide(res,n/2+1); /// res/(n/2+1)
- Afisez(res);
- }
- int main()
- {
- int n;
- cin>>n;
- catalan(2*n,n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement