Книга "Алгоритмы и программы"

Задачи из главы 3 "Рекурсия"

содержание задачника

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

содержание задачника