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

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

             _m-1            
   f(n, b) = ∑ d_i * 10ⁱ    ,
             ⁱ⁼⁰

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

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

                    _m-1            
   g(n, b, s) = s + ∑ d_i * 10ⁱ    .
                    ⁱ⁼⁰

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

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

       _m-1               _m-1
   s + ∑ d_i * 10ⁱ = q + ∑ d_i * 10^i-1    .
       ⁱ⁼⁰               ⁱ⁼⁰

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

                _m-1                                                    
   q = s + d₀ + ∑ d_i * (10ⁱ - 10^i-1)   .      (11.6)
                ⁱ⁼⁰

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

                         _m-1                                                    
   h(n, b, p, s) = s + p ∑ d_i * 10ⁱ    .      (11.7)
                         ⁱ⁼⁰

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

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

         _m-1                 _m-1
   s + p ∑ d_i * 10ⁱ = q + r ∑ d_i * 10^i-1    .
         ⁱ⁼⁰                 ⁱ⁼⁰

где есть две фиктивные переменные r и q. Если задать r = 10p, то выражение сокращается до

         _m-1                 _m-1
   s + p ∑ d_i * 10ⁱ = q + p ∑ d_i * 10ⁱ      .
         ⁱ⁼⁰                 ⁱ⁼⁰

откуда теперь можно легко найти q. А именно: q = s + p * d₀ = s + p * (n % b).

Наконец, с учётом того, что начальное условие выполняется при n < b, где f(n, b) = n, начальным условием для h(n, b, p, s) должно быть s + p * n (это следует из (11.7) при m = 1 и d₀ = 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.

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

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