Язык Си в примерах/Треугольник Паскаля: различия между версиями
Содержимое удалено Содержимое добавлено
Karagota (обсуждение | вклад) мНет описания правки |
Karagota (обсуждение | вклад) мНет описания правки |
||
Строка 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> — это
число способов быбрать ''k'' элементов из ''n'' различных. Например,
чиcло байт, в которых ровно 3 единицы — это число <math>C''8^3\,\!</math> —
число способов выбрать три бита, в которых будут стоять единицы,
из возьми бит байта.
Строка 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>?
|