На этом шаге мы рассмотрим реализацию этой задачи с использованием обобщенной функции.
Нам уже известны два способа создания алгоритма по преобразованию числа из одной системы счисления в другую. Примеры 4.10 и 11.6 содержат линейное и хвостовое рекурсивные решения соответственно. Теперь мы разработаем тот же хвостовой рекурсивный алгоритм, но с использованием обобщённой функции. Решение будет более сложным, поскольку нам потребуется два дополнительных параметра. Кроме того, гораздо сложнее будет и сама функция преобразования системы счисления, которую можно записать, например, следующим образом:
m-1 f(n, b) = ∑ di * 10i , i=0
Поскольку формула представляет собой сумму, мы можем начать с добавления к ней нового параметра 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
m-1 m-1 s + p ∑ di * 10i = q + p ∑ di * 10i . i=0 i=0
Наконец, с учётом того, что начальное условие выполняется при 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,
На следующем шаге мы приведем решения нескольких задач.