Lange Zahlen. Abteilung

Question

Welt! Ich habe ein Problem. Heute habe ich versucht, einen Code zu erstellen, der die katalanische Nummer findet. Aber in meinem Programm können lange Zahlen sein. Ich habe Zähler und Nenner gefunden. Aber ich kann keine langen Zahlen teilen! Außerdem sollten nur Standardbibliotheken in diesem Programm verwendet werden. Hilf mir bitte. Dies ist mein Code

#include <vector> 
#include <iostream> 

using namespace std; 

int main(int argc, char *argv[]) 
{ 
    const int base = 1000*1000*1000; 
    vector <int> a, b; 
    int n, carry = 0; 
    cin>>n; 
    a.push_back(n);      
    for (int ii=n+2; ii!=(2*n)+1;++ii) { 
     carry = 0;      
     for (size_t i=0; i<a.size() || carry; ++i) { 
      if (i == a.size()) 
       a.push_back (0); 
      long long cur = carry + a[i] * 1ll * ii; 
      a[i] = int (cur % base); 
      carry = int (cur/base); 
     } 
    } 
    while (a.size() > 1 && a.back() == 0) a.pop_back(); 

    b.push_back(n);     
    for (int ii=1; ii!=n+1;++ii) { 
     carry = 0; 
     for (size_t i=0; i<b.size() || carry; ++i) { 
      if (i == b.size()) 
       b.push_back (0); 
      long long cur = carry + b[i] * 1ll * ii; 
      b[i] = int (cur % base); 
      carry = int (cur/base); 
     } 
    } 
    while (b.size() > 1 && b.back() == 0) b.pop_back(); 

    cout<<(a.empty() ? 0 : a.back()); 
    for (int i=(int)a.size()-2; i>=0; --i) cout<<(a[i]); 

    cout<<" "; 

    cout<<(b.empty() ? 0 : b.back()); 
    for (int i=(int)b.size()-2; i>=0; --i) cout<<(b[i]); 
    //system("PAUSE"); 
    cout<<endl; 
    return 0; 
} 

P. S. Sorry für mein schlechtes Englisch =)

Answer 1

Du musst nicht rechnen (2n)! um (2n) zu berechnen/(n (n + 1)!)), weil Sie die Rekursion in this link gegeben verwenden können:

C (0) = 1
C (n) = (4n-2) C (n-1)/(n + 1)

Dies gibt Ihnen die ersten 15 Begriffe mit nur 32-Bit-Arithmetik. Und Sie können bis zu 16384 Terme generieren, indem Sie Multiplikation und Division einer Ganzzahl mit beliebiger Länge mit einer 16-Bit-Ganzzahl verwenden. Dies ist viel einfacher als die allgemeine Arithmetik mit willkürlicher Genauigkeit und könnte durchaus als Hausaufgabe gelten.

Answer 2

Es wird sehr schwierig sein, Division in Ihrer Darstellung von langen Zahlen zu implementieren, aber es ist real. Meiner Meinung nach ist die einfachste Methode Long_division.