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

[[ИзображениеФайл:pascal.png]]

То, что нарисовано справа, называется ''треугольником Паскаля'' &mdash; — в ''n''-й строчке этого треугольника находятся коэффициенты для разложения <imath>(a+b)^n\,\!</imath>-й строчке.

Число номер <math>k+1</math> в <i>''n</i>''-й строчке называется биномиальным коэффициентом <math>C_n^k\,\!</math>.

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

Эти числа возникают в задаче о числе сочетаний: <math>C_n^k\,\!</math> — &mdash;это число способов выбрать ''k'' элементов из ''n'' различных. Например, число байт, в которых ровно 3 единицы — это число <math>C_8^3\,\!</math> — число способов выбрать три бита, в которых будут стоять единицы, из восьми бит байта.

# Запрограммировать функцию <math>C(n,k) = C_n^k\,\!</math>.

# Вывести на экран <i>''n</i>'' строчек треугольника Паскаля.

* Сколько раз вызовется функция C(., .) при вычислении С(n, k)?

* Оцените ассимптотику <math>C_n^{n/2}\,\!</math>, а именно, напишите программу, которая вычисляет <math>\log C_n^{n/2}\,\!</math> для <math>n = 2, 4, ... , 40</math> и нарисутенарисуйте график

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

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