Указание: Правильная скобочная структура минимальной длины «()». Структуры большей длины получаются из структур меньшей длины, двумя способами:
(а) если меньшую структуру взять в скобки,
(б) если две меньших структуры записать последовательно.
5. Создайте процедуру, печатающую все возможные перестановки для целых чисел от 1 до N.
6. Создайте процедуру, печатающую все подмножества множества {1, 2, …, N}.
7. Создайте процедуру, печатающую все возможные представления натурального числа N в виде суммы других натуральных чисел.
8. Создайте функцию, подсчитывающую сумму элементов массива по следующему алгоритму: массив делится пополам, подсчитываются и складываются суммы элементов в каждой половине. Сумма элементов в половине массива подсчитывается по тому же алгоритму, то есть снова путем деления пополам. Деления происходят, пока в получившихся кусках массива не окажется по одному элементу и вычисление суммы, соответственно, не станет тривиальным.
Замечание: Данный алгоритм является альтернативой приему накопления суммы. В случае вещественнозначных массивов он, обычно, позволяет получать меньшие погрешности округления.
9. Запрограммируйте быстрые методы сортировки массивов, описанные в разделе 6.4.
10. Создайте процедуру, рисующую кривую Коха (рис. 12).
11. Воспроизведите рис. 16. На рисунке на каждой следующей итерации окружности в 2.5 раза меньше (этот коэффициент можно сделать параметром).
Рис. 16.
Литература
1. Д. Кнут. Искусство программирования на ЭВМ. т. 1. (раздел 2.3. «Деревья»).
2. Н. Вирт. Алгоритмы и структуры данных.
Другие материалы на этом сайте
Близкие разделы учебника по программированию:
Рекуррентные соотношения
Рекурсивные структуры данных
Вычисление полиномов от нескольких переменных - еще один пример рекурсивного алгоритма.
|
