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

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

$\begin{array}{rcc|c|ccccccccccccc} (a+b)^0&=& 1 & 0&&&&&&&1 \\[4pt] (a+b)^1 &=& a+b& 1&&&&&&1&&1 \\[4pt] (a+b)^2 &=& a^2+2ab+b^2 & 2&&&&&1&&2&&1 \\[4pt] (a+b)^3 &=& a^3+3a^2b+3ab^2+b^3 & 3&&&&1&&3&&3&&1 \\[4pt] (a+b)^4 &=& a^4 + 4a^3b + 6a^2b^2 + 4 ab^3+ b^4 & 4&&&1&&4&&6&&4&&1 \\[4pt] (a+b)^5 &=& \ldots & 5&&1&&5&&10&&10&&5&&1 \\[4pt] (a+b)^6 &=& \ldots & 6&1&&6&&15&&20&&15&&6&&1 \end{array}$

То, что нарисовано справо называется треугольником Паскаля — в 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^k — это число способов быбрать k элементов из n различных. Например, чиcло байт, в которых ровно 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!)}.$

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

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

/*
    Вычисление треугольника Паскаля.
*/
#include <stdio.h>
#define N 1000
long c[N];
int main ()
{
   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\n", c[i]);
   
   return 0;
}

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

работает быстрее, чем алгоритм вычисления C_n^k

из предыдущей программы, а именно время работы пропорционально n^2

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

Рекурсия с запоминанием

Сравните время вычисления C(20,10) с запоминанием и без.

/*
  Вычисление биномиальных коэффициентов.
*/
#include <stdio.h>
long Cd[100][100];
long C(long n,long k)
{
   if ( Cd[n][k] > 0 ) return  Cd[n][k];
   if (k == 0 || n == k) return 1;
   return Cd[n][k] = C(n - 1, k - 1) + C(n - 1, k);
}
int main()
{
   long n, k;
   for(n = 0; n < 100; n++) for( k = 0 ; k < 100; k++) Cd[n][k] = 0;
   scanf ("%ld%ld", &n, &k);
   printf ("%ld\n", C(n, k));
   return 0;
}

-- ArtemVoroztsov - 08 Sep 2004