На этом шаге мы рассмотрим рекурсивное решение этой задачи.

Цель следующей задачи - выяснить, является ли строка палиндромом, то есть цепочкой символов, которая одинаково читается в прямом и обратном направлениях (например, 'радар'). Её размер - длина строки, так как ею определяется количество операций, необходимых для получения результата. У этой задачи два начальных условия:

(a) когда строка пуста и
(b) когда она состоит из одного символа.

В обоих случаях результатом будет True (Истина). Как и для функции из примера 2.6, здесь необходимо второе начальное условие, поскольку при декомпозиции задачи мы будем уменьшать её размер на две единицы. В данном случае подзадача исключает первый и последний символы исходной строки длиной n ≥ 2. Результатом функции для некоторой строки s = s₀ s₁ ... s_n-2 s_n-1 длиной n будет выражение:

    (s₀ = s_n-1) ∧ (s₁ = s_n-2) ∧  ... ∧ (s_{⌊ n/2 ⌋-1} = s_{n-⌊ n/2 ⌋}),

где ∧ - логическая операция И (конъюнкция), а s_i - символ строки s в позиции i (первый символ - в позиции 0). Заметим, что сумма индексов сопоставляемых символов равна n - 1. Кроме того, необходимо сравнить только ⌊ n/2 ⌋ пар символов. Приведённое выражение можно записать короче, подобно сумме:

  _{⌊ n/2 ⌋-1}
    ∧ (s_i = s_n-i-1)
    ⁱ⁼⁰

Соответствующая рекурсивная схема:

Таким образом, логическая функция может быть определена как:

            True,                     если n < 2,
    f(s) = 
            (s₀ = s_n-1) ∧ f(s_1...n-2), если n ≥ 2,

где s_1...n-2 обозначает подстроку s₁ ... s_n-2.

Наконец, пример 4.12 представляет код с временной сложностью Θ(n).

Пример 4.12. Функция проверки строки на палиндром

1
2
3
4
5
6

def is_palindrome(s):
    n = len(s)
    if n <= 1:
        return True
    else:
        return (s[0] == s[n - 1]) and is_palindrome(s[1:n - 1])

Архив с файлом можно взять здесь.

Со следующего шага мы рассмотрим еще несколько других задач.

Предыдущий шаг Содержание Следующий шаг