адача 37. Последовательность из латинских букв строится следующим образом. На нулевом шаге она пуста. На каждом последующем шаге последовательность удваивается, то есть приписывается сама к себе, и к ней слева добавляется очередная буква алфавита (a, b, c, …). По заданному числу n определить символ, который стоит на n-м месте последовательности, получившейся после шага 26.

Решение. Эта задача предлагалась участникам областных туров Всероссийской олимпиады школьников по информатике в 1998 году. Приведем первые шаги формирования последовательности: 0 - пустая последовательность, 1 - a, 2 - baa, 3 - cbaabaa, 4 - dcbaabaacbaabaa, … . Мы имеем явно рекурсивный процесс.

Построим более общую программу-функцию, чем это требуется по условиям задачи. Пусть abra(k,n) - n-я буква в последовательности, полученной на шаге k (k=1..26). Тогда ясно, что abra(k,1) равно k-й букве латинского алфавита. Этот факт можно взять в качестве базы рекурсии, а функцию для определения этой буквы записать так:

letter(k) := substr("abcdefghijklmnopqrstuvwxyz", k - 1,1).

Декомпозицию удобно организовать по k, проводя “раскрутку” последовательности по шагам в обратном направлении. Это приводит к следующей функции:

Контрольные примеры:

abra(4, 6) = "b",    abra(26, 4) = "w",    abra(26, 2²⁶ - 127) = "g".

адача 38. Написать программу вычисления функции fo(n), определенной для целых неотрицательных n следующим образом:

fo(0) = fo(1) = 1,   fo(2×n) = fo(n),   fo(2×n + 1) = fo(n) + fo(n + 1).

Решение. Эта задача предлагалась участникам Московской олимпиады школьников по программированию в 1981 году. Поскольку функция fo(n) определена рекуррентными формулами, то написание соответствующей рекурсивной программы для её вычисления труда не составляет. Сделать это можно, например, так:

Контрольные примеры:

fo(0) = 1,      fo(1) = 1,      fo(7777777) = 9343.

Заметим, что вычисление fo(7777777777) занимает уже достаточно много времени (более одной минуты на компьютере Pentium-166). Происходит это по причине “двойного” рекурсивного обращения в последней строке программы. Улучшение быстродействия может быть достигнуто или введением динамической базы, при которой будут исключены повторные вычисления уже найденных значений функции, или переходом к более общей задаче. Остановимся на втором варианте. Рассмотрим вспомогательную функцию трех переменных:

 gg(n, i, j) = i×fo(n) + j×fo(n + 1).

Ясно, что   fo(n) = gg(n, 1, 0).

 Кроме того, для gg(n, i, j) легко проверяется справедливость следующих рекуррентных формул:

Далее

gg(0, i, j) = i×fo(0) + j×fo(1) = i + j,           gg(1, i, j) = i×fo(1) + j×fo(2) = i + j.

Все эти соотношения вместе с определением функции gg(n, i, j) позволяют предложить для её вычисления такую рекурсивную функцию:

Контрольные примеры:

 fo(7777777777, 1, 0) = 263117,     fo(77777777777777, 1, 0) = 130868233.

Стоит отметить, что вычисления по предложенной программе-функции gg(n, i, j) проводятся весьма эффективно и реализуются не более чем за [log₂(n)] операций деления и 2×[log₂(n)] операций сложения и вычитания.