80.2 Восходящий метод проектирования алгоритмов и программ. Спроектировать схему универсального алгоритма перевода чисел из любой системы счисления в любую другую.
Восходящий метод проектирования
При восходящем проектировании разработка идет снизу вверх. На первом этапе разрабатываются модули самого низкого уровня. На следующем этапе к ним подключаются модули более высокого уровня и проверяется их работоспособность. На завершающем этапе проектирования разрабатывается головной модуль, отвечающий за логику работы всего программного комплекса. Методы нисходящего и восходящего программирования имеют свои преимущества и недостатки.
Преимущество восходящего программирования – не нужно писать заглушки.
Недостаток восходящего программирования – головной модуль разрабатывается на завершающем этапе проектирования, что порой приводит к необходимости дорабатывать модули более низких уровней.
Перевод чисел из одной позиционной системы счисления в другую
Перевод чисел из одной позиционной системы счисления в другую выполняется по разным алгоритмам для целых и дробных частей числа [12].
Алгоритм 1. Для перевода целого числа из системы счисления с основанием p в систему счисления с основанием q нужно делить число и его частные на q. Последовательное деление производится до тех пор, пока не получится частное, равное нулю. Деление выполняется в исходной системе счисления. При этом в виде остатков от деления получаются q-ичные цифры (начиная с младшей) числа.
Алгоритм 2. Для перевода правильной дроби (дробной части числа) из p-ичной в q-ичную систему счисления нужно умножать эту дробь и дробные части полученных произведений на q. Целые части этих произведений образуют q-ичные цифры (начиная со старшей) представления правильной дроби в q-ичной системе счисления. Умножение выполняется в исходной системе счисления.
Алгоритм 3. Если результирующей системой счисления (p) - десятичная, то наиболее простой способ перевода - это перевод по весовым коэффициентам:
Xq = xn-1*qn-1 + xn-2*qn-2 + … + x1*q1 + x0*q0 + x-1*q-1 + x-2*qm-2 + … + xk*qk
или при алгоритмической реализации нужно вычислить сумму следующего вида:
n-1
Xq = xi*qi ,
i=-t
где n – количество разрядов в целой части числа, t – количество разрядов в дробной части числа.
Алгоритм 4. Частным случаем перевода чисел из одной системы счисления в другую служит ситуация, когда основание одной системы счисления является целой степенью другой (p=qk). В этом случае для перевода произвольного числа из q-ичной системы счисления в p-ичную нужно цифры числа влево и вправо от запятой разбить на группы по k разрядов в каждой. При этом если необходимо, крайнюю левую и крайнюю правую группы дополняют нулями до k цифр в группе. Затем надо заменить каждую выделенную k-значную группу цифрой в p-ичной системе счисления.
Схема универсального алгоритма перевода чисел из любой системы счисления в любую представлена на рис. 4.1, где частные алгоритмы оформлены подпрограммами. Число X в исходной системе счисления с основанием p в ней переводится в q-ичную систему счисления. Если p=10, то число разделяют на целую и дробную части, для перевода которых применяют алгоритмы 1 и 2 соответственно. Если результирующая система счисления является десятичной, то используют третий алгоритм. Если ни исходная, ни результирующая системы не являются десятичными, но p=qk, то пользуются четвертым алгоритмом. В случае, когда не выполняется ни одно из перечисленных условий, приходится сначала переводить число в десятичную систему счисления, после чего – в искомую. Это обусловлено сложностью выполнения операций в непривычных для человека системах счисления.
