2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Деление длинных
Сообщение31.01.2011, 15:48 
Необходимо вычислить энное число Каталана. Посчитал числитель и знаменатель, а поделить не могу. прошу помощи. Или хоть на яве с BigInteger решение...
Сам код
Код:
#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);                      //числитель считаем от n+2 до 2*n
    for (int ii=n+2; ii!=(2*n)+1;++ii) { //т.о. мы сразу поделили на n+1 (первый множитель чисел каталана)
        carry = 0;                       //и на n (из знаменателя)
        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);                //знаменатель считаем от 1 до n
    for (int ii=1; ii!=n+1;++ii) { //т.к. один из n! сократился со знаменателем
        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;
}

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 16:05 
А почему понадобились именно длинные? Не тот случай, когда промежуточные результаты не умещаются, но умещается конечный?

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 16:14 
Нет. Число Каталана может быть до 10000. В то время как 24е число = 1289904147324

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 16:37 
Тогда можно использовать распространённые и уже отлаженные библиотеки длинной арифметики. Например, здесь небольшой список есть: http://en.wikipedia.org/wiki/Arbitrary- ... #Libraries (в следующем разделе описаны языки, которые имеют встроенную).

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 16:41 
Нельзя использовать доп. библиотеки.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 16:51 
Ага, так это задание!

Обычно, вроде бы, реализуют сначала деление длинного на короткое, а потом на основе него — длинного на длинное. Так что лучше выделить процедуры функции умножения и сложения, т. к. будут ещё две для деления. Ещё вроде иногда делят столбиком. Алгоритм переносится прямо «с бумаги». Но, конечно, вроде было и что-то поэффективнее.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 16:54 
Воспользуйтесь рекуррентной формулой:
$$C_0=1, C_{n+1}=\dfrac{2(2n+1)}{n+2}C_n$$
Умножать и делить надо будет только на короткое число.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 16:56 
На яве никто не напишет со стандартным BigInteger? Ибо деление 2х длинных это ад какой то...

-- Пн янв 31, 2011 16:57:04 --

venco в сообщении #407167 писал(а):
Воспользуйтесь рекуррентной формулой:
$$C_0=1, C_{n+1}=\dfrac{2(2n+1)}{n+2}C_n$$
Умножать и делить надо будет только на короткое число.

Для 10000 тл не будет? Время 2 секунды

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 17:07 
boomeer в сообщении #407168 писал(а):
На яве никто не напишет со стандартным BigInteger?
Вообще-то поиском пользоваться по таким справочным вопросам раз плюнуть: http://www.google.ru/search?hl=ru&safe= ... 0&aql=&oq=
Первые же три ссылки ведут на страницы с подробным описанием всех полей, методов, конструкторов.

Кстати, думаю, раз нельзя библиотеки, то и BigInteger нельзя. :?

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 17:10 
boomeer в сообщении #407168 писал(а):
venco в сообщении #407167 писал(а):
Воспользуйтесь рекуррентной формулой:
$$C_0=1, C_{n+1}=\dfrac{2(2n+1)}{n+2}C_n$$
Умножать и делить надо будет только на короткое число.

Для 10000 тл не будет? Время 2 секунды
Всяко быстрее, чем делить два длинных числа.

-- Пн янв 31, 2011 09:14:34 --

А если скорости не будет хватать, то считайте по той-же рекуррентной формуле, но разложив все числа на простые множители, и перемножьте получившийся набор в самом конце.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 17:20 
Реализовал по такой схеме
Код:
#include <vector>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    int n,k;
    cin>>k;
    int res = 1;
   for (int i=2*k-k+1; i<=2*k; ++i)
      res *= i;
   for (int i=2; i<=k; ++i)
      res /= i;


    res=res/(k+1);
    cout<<res;
return 0;
}

Спасибо =)

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 17:26 
Это же неправильно у вас.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 17:33 
Zealint в сообщении #407202 писал(а):
Это же неправильно у вас.

Эм, что не так?

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 18:02 
boomeer в сообщении #407206 писал(а):
Эм, что не так?
Как-то слишком… коротко. :wink:

boomeer в сообщении #407195 писал(а):
Код:
2*k-k+1
Кстати, это ведь просто $k + 1$.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 20:39 
boomeer в сообщении #407206 писал(а):
Эм, что не так?

Да все "не так". Это не будет работать для тех ограничений, которые вы назвали вначале. Сами-то проверьте.

 
 
 [ Сообщений: 25 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group