Advertisement
nicuvlad76

Untitled

Dec 9th, 2020
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.24 KB | None | 0 0
  1. #include<iostream>
  2. #define NMax 1000
  3. using namespace std;
  4. typedef short Huge[NMax+3];
  5.  
  6. void AtribValue(Huge H,short X) {
  7. H[0] = 0;
  8. while (X) {
  9. ++H[0];
  10. H[H[0]] = X % 10;
  11. X /= 10;
  12. }
  13. }
  14.  
  15. void Mult(Huge H,short X)
  16. /* H <- H*X */
  17. {short i,T=0;
  18.  
  19. for (i=1;i<=H[0];i++)
  20. { H[i]=H[i]*X+T;
  21. T=H[i]/10;
  22. H[i]=H[i]%10;
  23. }
  24. while (T) /* Cat timp exista transport */
  25. { H[++H[0]]=T%10;
  26. T/=10;
  27. }
  28. }
  29.  
  30. void Divide(Huge A,short X)
  31. /* A <- A/X si intoarce A%X */
  32. { short i,R=0;
  33. for (i=A[0];i;i--)
  34. { A[i]=(R=10*R+A[i])/X;
  35. R%=X;
  36. }
  37. while (!A[A[0]] && A[0]>1) A[0]--;
  38. }
  39.  
  40. void Afisez(Huge H)
  41. {
  42. for(short i=H[0];i>0;--i)
  43. cout<<H[i];
  44. cout<<'\n';
  45. }
  46.  
  47. void catalan(unsigned int n,unsigned int k) /// Folosesc coeficientii binomiali
  48. {
  49. Huge res;
  50. AtribValue(res,1);
  51. if(k>n-k) /// C(n, k) = C(n, n-k)
  52. k=n-k;
  53. for(unsigned int i=0;i<k;++i) /// Calculez valoarea [n*(n-1)*---*(n-k+1)]/[k*(k-1)*---*1]
  54. {
  55. Mult(res,n-i); /// res*=n-i
  56. Divide(res,i+1); /// res/=(i+1)
  57. }
  58. Divide(res,n/2+1); /// res/(n/2+1)
  59. Afisez(res);
  60. }
  61.  
  62. int main()
  63. {
  64. int n;
  65. cin>>n;
  66. catalan(2*n,n);
  67. return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement