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

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

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

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

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

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

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

Например, $C_{3}^{0} = 1, C_{5}^{2} = 10, 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, C_{n}^{k} + C_{n}^{k + 1} = C_{n + 1}^{k + 1}, 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;
}

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

Шаблон:BookCat

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

Навигация

Поиск