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

Содержимое удалено Содержимое добавлено
мНет описания правки
мНет описания правки
Строка 6:
 
То, что нарисовано справа, называется ''треугольником Паскаля'' — в n-ой строчке
этого треугольника находятся коэффициенты для разложения <math>(a+b)^n\,\!</math>.
 
Число номер k+1 в n-ой строчке называется биномиальным коэффициентом <math>C''n^k\,\!</math>.
Например,
<math>C''3^0 = 1, \quad C''5^2 = 10, \quad C''4^2 = 6.\,\!</math>
 
Эти числа возникают в задаче о числе сочетаний: <math>C''n^k\,\!</math> &mdash; это
число способов быбрать ''k'' элементов из ''n'' различных. Например,
чиcло байт, в которых ровно 3 единицы &mdash; это число <math>C''8^3\,\!</math> &mdash;
число способов выбрать три бита, в которых будут стоять единицы,
из возьми бит байта.
Строка 23:
 
Докажите, что
<math>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!)}.\,\!</math>
 
 
Рассмотрим две программы, которыерешают следующие задачи:
#Запрограммировать функцию <math>C(n,k) = C''n^k\,\!</math>.
#Вывести на экран n строчек треугольника Паскаля.
 
Строка 51:
 
*Сколько раз вызовется функция 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> для n=2, 4, ... , 40 и нарисуте график <math>\log C''n^{n/2}\,\!</math> от n.
 
 
Строка 77:
 
*Докажите, что указанный алгоритм вычисления ''n'' -ой строчки треугольника Паскаля
работает быстрее, чем алгоритм вычисления <math>C''n^k\,\!</math> из предыдущей программы, а именно
время работы пропорционально <math>n^2\,\!</math>.
*Начиная с какого ''n'' самое большой число из ''n'' -ой строчки не умещается в тип <tt>long</tt>?