Шаг 182.
Рекурсия на Python. ... . К хвостовой и вложенной рекурсии через обобщённую функцию. Приведение десятичного числа к другому основанию

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

    Нам уже известны два способа создания алгоритма по преобразованию числа из одной системы счисления в другую. Примеры 4.10 и 11.6 содержат линейное и хвостовое рекурсивные решения соответственно. Теперь мы разработаем тот же хвостовой рекурсивный алгоритм, но с использованием обобщённой функции. Решение будет более сложным, поскольку нам потребуется два дополнительных параметра. Кроме того, гораздо сложнее будет и сама функция преобразования системы счисления, которую можно записать, например, следующим образом:

             m-1            
   f(n, b) =  di * 10i    ,
             i=0            
где n - приводимое к основанию b десятичное число. Кроме того, m - количество цифр по основанию b в новом представлении n, а di (i = 0, ..., m - 1) - цифры этого представления. К счастью, более точного определения этих цифр не требуется.

    Поскольку формула представляет собой сумму, мы можем начать с добавления к ней нового параметра s, что приводит к следующей обобщённой функции:

                    m-1            
   g(n, b, s) = s +  di * 10i    .
                    i=0            

    Для уменьшения размера задачи на 1 в декомпозиции используется целочисленное деление n на b, что приводит к следующей схеме:

    Из неё следует, что:

       m-1               m-1
   s +  di * 10i = q +  di * 10i-1    .
       i=0               i=0            

    При попытке найти q сразу видно, что решение получается сложным:

                m-1                                                    
   q = s + d0 +  di * (10i - 10i-1)   .      (11.6)
                i=0                                                     

    Но нетрудно заметить, что, умножив сумму подзадачи на 10, можно избавиться от суммы в формуле (11.6) и тем самым значительно упростить её. С этой целью можно добавить ещё один параметр - множитель суммы, - чтобы получить более общую функцию

                         m-1                                                    
   h(n, b, p, s) = s + p  di * 10i    .      (11.7)
                         i=0                                                     

Для этой новой функции можно создать следующую схему:

    В этом случае мы имеем:

         m-1                 m-1
   s + p  di * 10i = q + r  di * 10i-1    .
         i=0                 i=0            
где есть две фиктивные переменные r и q. Если задать r = 10p, то выражение сокращается до
         m-1                 m-1
   s + p  di * 10i = q + p  di * 10i      .
         i=0                 i=0            
откуда теперь можно легко найти q. А именно: q = s + p * d0 = s + p * (n % b).

    Наконец, с учётом того, что начальное условие выполняется при n < b, где f(n, b) = n, начальным условием для h(n, b, p, s) должно быть s + p * n (это следует из (11.7) при m = 1 и d0 = n). Таким образом, функцию h можно определить так:

                    s + p * n,                          если n < b
    h(n, b, p, s) = 
                    h(n // b, b, 10p, s + p * (n % b)), если n ≥ b,
где f(n, b) = h(n, b, 1, 0). Второе начальное условие выполняется при n = 0, что приводит к функции из примера 11.6.

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




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