Язык Си в примерах/Треугольник Паскаля

Всем известны простые формулы

• ${\displaystyle (a+b)^{2}=a^{2}+2ab+b^{2}}$
• ${\displaystyle (a+b)^{3}=a^{3}+3a^{2}b+3ab^{2}+b^{3}}$

А как находить коэффициенты в разложении ${\displaystyle (a+b)^{n}}$?

Рассмотрим следующую таблицу:

То, что нарисовано справа, называется треугольником Паскаля — в n-й строчке этого треугольника находятся коэффициенты для разложения ${\displaystyle (a+b)^{n}\,\!}$.

Число номер ${\displaystyle k+1}$ в n-й строчке называется биномиальным коэффициентом ${\displaystyle C_{n}^{k}\,\!}$.

Например, ${\displaystyle C_{3}^{0}=1,\quad C_{5}^{2}=10,\quad C_{4}^{2}=6.\,\!}$

Стороны треугольника Паскаля состоят из единичек. Каждое число внутри треугольника Паскаля равно сумме двух чисел, стоящих над ним справа и слева в предыдущей строчке:

${\displaystyle C_{n+1}^{k+1}=C_{n}^{k+1}+C_{n}^{k}.}$

Эти числа возникают в задаче о числе сочетаний: ${\displaystyle C_{n}^{k}\,\!}$ — это число способов выбрать k элементов из n различных. Например, число байт, в которых ровно 3 единицы — это число ${\displaystyle C_{8}^{3}\,\!}$ — число способов выбрать три бита, в которых будут стоять единицы, из восьми бит байта.

Докажите, что
${\displaystyle C_{n}^{1}=n,\quad C_{n}^{k}+C_{n}^{k+1}=C_{n+1}^{k+1},\quad C_{n}^{k}={\frac {n!}{k!(n-k)!}}.\,\!}$

Рассмотрим две программы, которые решают следующие задачи:

1. Запрограммировать функцию ${\displaystyle C(n,k)=C_{n}^{k}\,\!}$.
2. Вывести на экран n строчек треугольника Паскаля.

/*
   Вычисление биномиальных коэффициентов.
 */
#include <stdio.h>

long
C (long n, long k)
{
  if (k == 0 || n == k)
    return 1;
  return C (n - 1, k - 1) + C (n - 1, k);
}

int
main ()
{
  long n, k;
  scanf ("%ld%ld", &n, &k);
  printf ("%ld ", C (n, k));
  return 0;
}

• Сколько раз вызовется функция C(., .) при вычислении С(n, k)?
• Докажите, что время вычисления ${\displaystyle C_{n}^{k}\,\!}$ по приведенному алгоритму пропорционально ${\displaystyle C_{n}^{k}\,\!}$.
• Оцените ассимптотику ${\displaystyle C_{n}^{n/2}\,\!}$, а именно, напишите программу, которая вычисляет ${\displaystyle \log C_{n}^{n/2}\,\!}$ для ${\displaystyle n=2,4,...,40}$ и нарисуйте график

${\displaystyle \log C_{n}^{n/2}\,\!}$ от ${\displaystyle n}$.

/*
    Вычисление n-й строки треугольника Паскаля.
*/
#include <stdio.h>
#define N 1000

int
main ()
{
  long c[N];
  long n, i, j;
  scanf ("%ld", &n);
  for (i = 1; i <= n; i++)
    c[i] = 0;
  c[0] = 1;
  for (j = 1; j <= n; j++)
    for (i = j; i >= 1; i--)
      c[i] = c[i - 1] + c[i];
  for (i = 0; i <= n; i++)
    printf ("%ld ", c[i]);
  return 0;
}

• Докажите, что указанный алгоритм вычисления n-й строчки треугольника Паскаля

работает быстрее, чем алгоритм вычисления ${\displaystyle C_{n}^{k}\,\!}$ из предыдущей программы, а именно время работы пропорционально ${\displaystyle n^{2}\,\!}$.

• Начиная с какого n самое большое число из n-й строчки треугольника Паскаля не умещается в тип long?

Еще один вариант реализации вычисления Биномиального коэффициента из общей формулы ${\displaystyle C_{n}^{k}\,\!}$ (без рекурсии):

/*
  Вычисление биномиальных коэффициентов
*/
#include <assert.h>
#include <stdio.h>

int
binomial (int row, int pos)
{
  int koef = 1;
  int i;
  for (i = pos + 1; i <= row; i++)
    koef = koef * i;
  for (i = 1; i < (row - pos + 1); i++)
    koef = koef / i;
  return koef;
}

int
main (void)
{
  int row, pos;
  int r = scanf ("%i%i", &row, &pos);
  assert (r == 2);
  printf ("%i", binomial (row, pos));
  return 0;
}

Если посмотреть на Треугольник Паскаля, то можно заметить симметрию. Если исходить из нее и общей формулы ${\displaystyle C_{n}^{k}\,\!}$, то можно еще немного улучшить алгоритм (уменьшив число проходов) из кода выше сокращая числитель на больший элемент знаменателя:

/*
  Вычисление биномиальных коэффициентов
*/
#include <assert.h>
#include <stdio.h>

int
binomial (int row, int pos)
{
  int koef = 1;
  int i;
  if (row - pos > pos)
    pos = row - pos;
  for (i = pos + 1; i <= row; i++)
    koef = koef * i;
  for (i = 1; i < (row - pos + 1); i++)
    koef = koef / i;
  return koef;
}

int
main (void)
{
  int row, pos;
  int r = scanf ("%i%i", &row, &pos);
  assert (r == 2);
  printf ("%i", binomial (row, pos));
  return 0;
}

Стоит учитывать, что в реализованных примерах нет защиты от дурака (переполнение значения переменной).