Длинные номера. разделение - PullRequest
Новая
       16

Длинные номера. разделение

1 голос
/ 16 января 2011

мир!У меня проблема.Сегодня я попытался создать код, который находит каталонский номер.Но в моей программе могут быть длинные номера.Я нашел числитель и знаменатель.Но я не могу разделить длинные числа!Также в этой программе должны использоваться только стандартные библиотеки.Помоги мне, пожалуйста.Это мой код 

#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;
}

PS Извините за мой плохой английский =)

Ответы [ 2 ]

4 голосов
/ 16 января 2011

Вам не нужно рассчитывать (2n)!чтобы вычислить (2n)! / (n! (n + 1)!)), потому что вы можете использовать рекуррентное соотношение, указанное в этой ссылке :

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

Это дает вам первые 15 слагаемых, используя только 32-битную арифметику.И вы можете генерировать до 16384 слагаемых, просто используя умножение и деление целого числа произвольной длины на 16-битное целое число.Это намного проще, чем обычная арифметика с произвольной точностью, и вполне может быть задано как домашнее задание.

1 голос
/ 16 января 2011

Будет очень сложно реализовать деление в вашем представлении длинных чисел, но это реально.На мой взгляд, самый простой метод это Long_division .

...