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

Нет описания правки
м (Категоризация по запросу на w:ВП:РДБ)
Рассмотрим следующую таблицу:
 
[[ИзображениеФайл:pascal.png]]
 
То, что нарисовано справа, называется ''треугольником Паскаля'' &mdash; — в ''n''-й строчке этого треугольника находятся коэффициенты для разложения <imath>(a+b)^n\,\!</imath>-й строчке.
этого треугольника находятся коэффициенты для разложения <math>(a+b)^n\,\!</math>.
 
Число номер <math>k+1</math> в <i>''n</i>''-й строчке называется биномиальным коэффициентом <math>C_n^k\,\!</math>.
 
Например,
<math>C_3^0 = 1, \quad C_5^2 = 10, \quad C_4^2 = 6.\,\!</math>
 
Стороны треугольника Паскаля состоят из единичек. Каждое число внутри треугольника Паскаля равно сумме двух чисел, стоящих над ним справа и слева в предыдущей строчке:
 
<math>C^{k+1}_{n+1} = C^{k+1}_{n}+C^k_{n}.</math>
 
Эти числа возникают в задаче о числе сочетаний: <math>C_n^k\,\!</math> — &mdash;это число способов выбрать ''k'' элементов из ''n'' различных. Например, число байт, в которых ровно 3 единицы — это число <math>C_8^3\,\!</math> — число способов выбрать три бита, в которых будут стоять единицы, из восьми бит байта.
число способов выбрать ''k'' элементов из ''n'' различных. Например,
чиcло байт, в которых ровно 3 единицы &mdash; это число <math>C_8^3\,\!</math> &mdash;
число способов выбрать три бита, в которых будут стоять единицы,
из воcьми бит байта.
 
 
 
Рассмотрим две программы, которые решают следующие задачи:
# Запрограммировать функцию <math>C(n,k) = C_n^k\,\!</math>.
# Вывести на экран <i>''n</i>'' строчек треугольника Паскаля.
 
 
</source>
 
* Сколько раз вызовется функция C(., .) при вычислении С(n, k)?
* Докажите, что время вычисления <math>C_n^k\,\!</math> по приведенному алгоритму пропорционально <math>C_n^k\,\!</math>.
* Оцените ассимптотику <math>C_n^{n/2}\,\!</math>, а именно, напишите программу, которая вычисляет <math>\log C_n^{n/2}\,\!</math> для <math>n = 2, 4, ... , 40</math> и нарисутенарисуйте график
<math>\log C_n^{n/2}\,\!</math> от <math>n</math>.
 
</source>
 
* Докажите, что указанный алгоритм вычисления <i>''n</i>''-й строчки треугольника Паскаля
работает быстрее, чем алгоритм вычисления <math>C_n^k\,\!</math> из предыдущей программы, а именно
время работы пропорционально <math>n^2\,\!</math>.
* Начиная с какого <i>''n</i>'' самое большое число из <i>''n</i>''-й строчки треугольника Паскаля не умещается в тип <tt>long</tt>?
[[Категория:Язык Си в примерах|Треугольник Паскаля]]
Анонимный участник