Паскаль Треугольник в C

Question

Поэтому я реализовал эту программу Pascal Triangle в C, и она хорошо работает вплоть до 13-й строки, где значения больше не верны. Я полагаю, что комбинационная функция верна, a k комбинация из n элементов может быть написана факториалами, и об этом говорится на странице о комбинации в Википедии, хе-хе Вот код:

#include <stdio.h>

int factorial(int number);
int combination(int n, int k);

int main() {
    int lines;
    int i, j;

    printf("Number of Pascal Triangle lines: ");
    scanf("%d", &lines);

    for (i = 0; i <= lines; i++) {
        for (j = 0; j <= i; j++)
            printf("%d ", combination(i, j));

        printf("\n");
    }
}

int combination(int n, int k) {
    int comb;

    comb = (factorial(n)) / (factorial(k) * factorial(n - k));

    return comb;
}

int factorial(int number) {
    int factorial = 1;
    int i;

    for (i = 1; i <= number; i++)
        factorial = factorial * i;

    return factorial;
}

Answer 1

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

• вычисление факториала в числителе подвержено переполнению,

• каждое вычисление требует оценки около n товары (k + n - k) и разделение (плюс n! вычисляется один раз), всего n² за ряд

Гораздо более эффективным решением является правило Паскаля (каждый элемент является суммой двух элементов над ним). Если вы храните строку, следующая строка получается просто n дополнения. И это переполняется только тогда, когда значение элемента слишком велико, чтобы его можно было представить.

---

Если вам нужно только n-й ряд, вы можете использовать повторение

C(n,k) = C(n,k-1).(n-k+1)/k

Это включает в себя 2n дополнения, n умножения и n деления, и может переполниться даже для представимых значений. Из-за высокой стоимости подразделений, для умеренных n вероятно, лучше оценить весь треугольник! (Или просто зашифруйте это.)

Если вам нужен один элемент, это повторение привлекательно. Используйте симметрию для k выше n/2 (C(n,k) = C(n,n-k)).

Answer 2

Надеюсь, что следующий код может помочь:

/*elements of the pascal's trianlge for 10 rows*/

#include<stdio.h>
int main()
{
 int p[11][11];
 int i,j,k;

 for(i=1;i<=10;i++)
   {
     /*creating whitespaces*/
     for(k=i;k<=10;k++)
      {
         printf("  ");
      }
     for(j=1;j<=i;j++)
      {
        /*printing the boundary elements i.e. 1*/
        if(j==1 || i==j) 
          {
            p[i][j]=1;
            printf("%3d ",p[i][j]);
          }
        /*printing the rest elements*/
        else
          {
            p[i][j]=p[i-1][j-1]+p[i-1][j];
            printf("%3d ",p[i][j]);
          }   
       }
      printf("\n");
   }
}

Спасибо

Answer 3

Ваша реализация не может обрабатывать даже умеренно большие значения n потому что factorial(n) вызывает арифметическое переполнение для n >= 13,

Вот упрощенная рекурсивная реализация, которая может обрабатывать большие значения, хотя и очень медленно:

#include <stdio.h>

int combination(int n, int k) {
    if (n < 0 || k < 0 || k > n)
        return 0;
    if (k == 0 || k == n)
        return 1;
    return combination(n - 1, k - 1) + combination(n - 1, k);
}

int main() {
    int lines, i, j;

    printf("Number of Pascal Triangle lines: ");
    if (scanf("%d", &lines) != 1)
        return 1;

    for (i = 0; i <= lines; i++) {
        for (j = 0; j <= i; j++) {
            printf("%d ", combination(i, j));
        }
        printf("\n");
    }
    return 0;
}

Заметки:

• Эта реализация иллюстрирует, насколько сильно неэффективными могут быть рекурсивные реализации.
• Поскольку вы печатаете полный треугольник, вам следует сохранять промежуточные результаты и очень эффективно вычислять одну полную строку за раз из предыдущей строки, но все же ограниченную диапазоном значений. unsigned long long67 строк.

Вот более быстрая альтернатива:

#include <stdio.h>

int main() {
    int lines, i, j;

    printf("Number of Pascal Triangle lines: ");
    if (scanf("%d", &lines) != 1 || lines < 0 || lines > 67)
        return 1;

    unsigned long long comb[lines + 1];
    for (i = 0; i <= lines; i++) {
        comb[i] = 0;
    }
    comb[0] = 1;
    for (i = 0; i <= lines; i++) {
        for (j = i; j > 0; j--) {
            comb[j] += comb[j - 1];
        }
        for (j = 0; j <= i; j++) {
            printf("%llu ", comb[j]);
        }
        printf("\n");
    }
    return 0;
}