Найти каждое число в треугольнике Паскаля в 1500-м ряду?

Я только что задал еще один вопрос о треугольнике Паскаля о нахождении суммы 1500-й строки. Я так рад, что люди так быстро ответили, но, к сожалению, позже я понял, что мне нужен каждый отдельный номер в 1500-й строке.

Здесь я нашел простой способ вычислить любое число на треугольнике Паскаля, но когда я пытаюсь использовать формулу в своем коде, программа вылетает при запуске.

#include"stdio.h"
int factorial(int);

int main()
{
    int i=0;
    for(i=0; i<1501; i++)
    {
       printf("%d \n" , (factorial(1500)/factorial(1500-i))/factorial(i) );
    }
}
int factorial(int x)
{
    if(x<2)
    return 1;
    else
    {
        return x*factorial(x-1);
    }
}

c++ math pascals-triangle
person Ahmet Yildirim    schedule 29.09.2012    source источник
comment
Вы достигли пределов рекурсии (переключитесь на цикл for или while) и целочисленного типа со знаком. Вам придется найти другой способ.   -  person user7116    schedule 29.09.2012
comment
factorial(1500) слишком велик для int. Или long. Или unsigned long long. 1500! это большое, большое число; его расширение по основанию 10 состоит из 4115 десятичных цифр. Вам придется найти другой способ.   -  person David Hammen    schedule 29.09.2012
comment
Он помечен как c++, но для меня он больше похож на C. С алгоритмической точки зрения это не имеет большого значения, но существует ряд хороших библиотек больших целочисленных значений C ++ (или оберток библиотек C bigint), которые делают арифметику произвольной точности очень естественной.   -  person DSM    schedule 29.09.2012
comment
возможно, нам следует сделать некоторые упрощения на (factorial (1500) / factorial (1500-i)) / factorial (i), но я не знаю как :(   -  person Ahmet Yildirim    schedule 29.09.2012
comment
Может быть, вам сначала стоит попробовать меньший ряд.   -  person Beta    schedule 29.09.2012
comment
Поскольку оба этих огромных факториала делятся на 2 ^ 31, в конечном итоге они равны нулю, а затем вы делите на них. Вероятно, это причина того, что ваша программа вылетает.   -  person Ivan Vergiliev    schedule 29.09.2012

Ответы (2)


arrow_upward
3
arrow_downward

Для результатов вам понадобится библиотека biginteger, так как

binom(1500,750) = 722462892448930217028116073228485295944376343040546523665632913653613596406381727723198055046187955623124069093412562720869577867557610868874271130828359513282184417776042792372322074253393127328396528996120053749558122610911178218582669317535346728464707661495135518682519172221470420360910320792434869988224466647627642393919250205687942318888922893189087379790541907686956429837978631252775258630376332505697937034877619012586751274240109457111424

превышает даже обычный double диапазон.

Но при наличии такого типа отношение

binom(n,k+1) = binom(n,k)*(n-k)/(k+1)

позволяет простую и относительно эффективную реализацию:

bigint value = 1;
int numerator = 1500 + 1, denominator = 0;
for(; denominator <= 1500; --numerator, ++denominator, value = value*numerator/denominator)
{
    output(value);
}

где output - любой метод вывода, предоставляемый библиотекой.

Часть value = value*numerator/denominator необходимо адаптировать, если библиотека не предлагает перегрузки для умножения / деления больших целых чисел и обычных int.

person Daniel Fischer    schedule 29.09.2012
comment
я пробовал ваш код с этой библиотекой acme.com/software/bigint, произошла следующая ошибка: недопустимые операнды для двоичный * (имеют 'bigint' и 'int') на значении = значение * числитель / знаменатель - person Ahmet Yildirim; 29.09.2012
comment
Так что у него нет упомянутых мной перегрузок. Вероятно, он предлагает либо специальную функцию для этой комбинации, либо способ создания bigints из ints, так что value = value*new bigint(numerator) / new bigint(denominator) может работать, но нет настоящей связанной документации, поэтому я просто предполагаю. - person Daniel Fischer; 29.09.2012

arrow_upward
3
arrow_downward

Вместо этого используйте линейный алгоритм для факториала, чтобы не переполнять стек из-за рекурсии:

int factorial(int x) {
    if (x < 2) return 1;

    int result = x;

    while (--x) {
        result *= x;
    }

    return result;
}
person orlp    schedule 29.09.2012