Книга “Алгоритмы и программы”
Задачи из главы 3 “Рекурсия”
- Строка состоит из клеток, пронумерованных от 1 до \(n\). Состояние клетки можно изменить – если она пуста, поставить в нее шашку (занять ее), иначе убрать из нее шашку (освободить ее). Вначале строка пуста. Нужно занять все клетки, соблюдая следующее правило. Изменение клетки допустимо, если она имеет номер 1 или расположена непосредственно после занятой клетки, имеющей минимальный номер среди занятых клеток. Решение
Вход. Целое \(n, 1\le n\le 15\).
Выход. Последовательность элементов вида \(+i\) или \(-i\), обозначающих соответственно занять клетку \(i\) и освободить клетку \(i\).
Пример. При \(n=3\) выход имеет вид \(+1+2-1+3+1\). - Даны \(a\) и \(N\). Вычислите \(a^N\) без использования логарифма и экспоненты. Решение
- Написать программу, рисующую снежинку Коха порядка \(n\).
- Написать программу, рисующую треугольник Серпинского порядка \(n\).
- Напишите программу построения драконовой ломаной порядка \(n\).
- С помощью рекурсии найдите сумму цифр данного натурального числа.
- Напишите рекурсивную функцию, печатающую цифра натурального числа в а) прямом; б) обратном порядке.
- Известно, что \(F(n)=n-10\) при \(n>100\) и \(F(n)=F(F(n+11))\) при \(n\le 100\). Найдите \(F(n)\) при \(n<200\).
- Заданы две строки \(a\) и \(b\) с длинами \(m\) и \(n\). Найдите максимальную длину их общей подпоследовательности символов. Например, для “орел” и “осел” это “оел” длины 3.