Алгоритмы и программы. Задачи из главы 3 “Рекурсия”

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

Задачи из главы 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.

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