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

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

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

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

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

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

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

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

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

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

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

Докажите, что
 $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)!}}.\,\!$

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

Запрограммировать функцию $C(n,k)=C_{n}^{k}\,\!$ .
Вывести на экран 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)?
Докажите, что время вычисления $C_{n}^{k}\,\!$ по приведенному алгоритму пропорционально $C_{n}^{k}\,\!$ .
Оцените ассимптотику $C_{n}^{n/2}\,\!$ , а именно, напишите программу, которая вычисляет $\log C_{n}^{n/2}\,\!$ для $n=2,4,...,40$ и нарисуйте график

$\log C_{n}^{n/2}\,\!$ от $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-й строчки треугольника Паскаля

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

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

Еще один вариант реализации вычисления Биномиального коэффициента из общей формулы $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;
}

Если посмотреть на Треугольник Паскаля, то можно заметить симметрию. Если исходить из нее и общей формулы $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;
}

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