На этом шаге мы приведем рекурсивную функцию, реалищующую такое представление.

Цель этого примера - разработка рекурсивной функции, которая для заданного неотрицательного целого числа n по основанию 10 возвращает новое целое число - его двоичное представление, состоящее из последовательности двоичных цифр (или битов). Результатом будет также десятичное число, но его цифры будут либо нулями, либо единицами. Таким образом, можно считать, что его цифры фактически соответствуют битам.

Поскольку мы должны создать последовательность "битов", размер задачи - это число битов в двоичном представлении n, или математически ⌊log₂ n⌋ + 1 (для n > 0). При этом формула для разработки рекурсивного алгоритма нам не нужна. Всё, что нам нужно, - чётко определить размер задачи, что позволит нам определить начальные условия и разбить задачу на подзадачи. В частности, наименьшие экземпляры задачи соответствуют числам, которые содержат один-единственный бит, которым могут быть 0 или 1. Таким образом, начальное условие с результатом n возникает при n < 2.

Для вывода рекурсивного условия нужно решить, как уменьшать размер задачи. Самый простой способ заключается в уменьшении количества битов на 1, что достигается целочисленным делением n на 2 (оно сдвигает биты на одну позицию вправо, причём наименьший значащий бит отбрасывается). Начнём разбор с конкретных экземпляров задачи. Например:

Отметим, что результат f(18) = 10010 выражен по основанию 10. На схемах показано, что желаемый результат можно получить, умножая результат подзадачи на 10 и затем добавляя к нему 1, если n - нечётное. Поэтому рекурсивное условие видится таким: f(n) = 10f(n // 2) + n % 2.

Более строго схему рекурсивного процесса осмысления задачи можно обобщить следующим образом:

где b_i представляет бит. В частности, f(n // 2) - десятичное число, которое представляет последовательность "битов" n, за исключением самого младшего (b₀), чьё значение - n%2 (или n&1, где & обозначает поразрядную операцию AND). Чтобы добавить отброшенный бит, нужно умножить f(n//2) на 10 (то есть сдвинуть цифры на одну позицию влево, добавив 0) и добавить его к результату. Таким образом, на самом деле рекурсивным условием действительно будет f(n) = 10f(n // 2) + n % 2, полученное путём на основании анализа конкретных экземпляров задачи. Окончательная функция:

            n,                   если n < 2,
    f(n) = 
            10f(n // 2) + n % 2, если n ≥ 2.

В примере 4.9 приведён код для решения задачи. В итоге двоичное представление 142 = 142₁₀ - это 10001110₂ = 128 + 8 + 4 + 2.

Пример 4.9. Двоичное представление неотрицательного целого числа

1
2
3
4
5

def decimal_binary(n):
    if n < 2:
        return n
    else:
        return 10 * decimal_binary(n // 2) + (n % 2)

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

На следующем шаге мы рассмотрим приведение десятичного числа к другому основанию.

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