Язык Си в примерах/Треугольник Паскаля: различия между версиями
Содержимое удалено Содержимое добавлено
Greck (обсуждение | вклад) мНет описания правки |
Greck (обсуждение | вклад) мНет описания правки |
||
Строка 59:
* Сколько раз вызовется функция 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>. Строка 82 ⟶ 83 :
* Докажите, что указанный алгоритм вычисления <i>n</i>-й строчки треугольника Паскаля
работает быстрее, чем алгоритм вычисления <math>C_n^k\,\!</math> из предыдущей программы, а именно
время работы пропорционально <math>n^2\,\!</math>.
* Начиная с какого
|