Современные информационные технологии/2. Вычислительная техника и программирование

Балгабаева Р.Н., Мурадилова Г.С.

Кокшетауский государственный университет им.Ш.Уалиханова, Казахстан

СРАВНЕНИЕ ДЛИННЫХ ЦЕЛЫХ ПРИ РЕАЛИЗАЦИИ АЛГОРИТМОВ НЕСТАНДАРТНОЙ ОБРАБОТКИ ЧИСЕЛ

В языках программирования диапазоны значений базовых числовых типов данных обычно ограничены, и при решении многих задач их оказывается недостаточно. Для повышения точности вычислений, увеличения диапазона или для улучшения какой-нибудь характеристики, разработчики программ сами разрабатывают типы данных для хранения чисел и подпрограммы для арифметических действий с ними.

Рассмотрим некоторые алгоритмы, которые позволяют обрабатывать точные значения неотрицательных целых чисел с большим количеством знаков. Количество знаков зависит от решаемой задачи, ограничений по времени работы программы и ограничений по памяти. Это может быть, например, и сотни десятичных знаков, и тысячи, и более. Обработка этих чисел также зависит от постановки конкретной задачи. В одних задачах к числам нужно применять только аддитивные арифметические операции, в других – только мультипликативные, и т.д.

Для работы с многоразрядными числами часто разумным оказывается использование массива элементов типа byte, представляющих числа от 0 до 99 (цифры по основанию 100), или типа word (цифры по основанию 10000). По сравнению с хранением одной десятичной цифры в byte, удается приблизительно вдвое сэкономить память, почти не усложнив ввод-вывод. При этом еще и ускоряются некоторые арифметические действия - за счет того, что у числа, записанного в 10000-ричной системе, вчетверо меньше цифр, чем у записанного в десятичной.

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

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

const n = 1000; const m = 100; const m1=1;

type t1 = 0..n; t2 = 0..m-1;

…

…

type BzLong = record

us: t1;

mas: array [1..n] of t2;

end;

Количество реально занятых цифр при желании можно разместить не в отдельном поле записи, а в нулевом элементе самого массива (аналогично длине строки в типе string языка Turbo Pascal). Однако это не лучшее решение, поскольку в одном массиве смешиваются величины разной природы. К тому же, записи с несколькими полями позволяют легко менять тип (и, следовательно, диапазон) величин одной природы, не трогая величины другой.

Cравним длинные числа, представленных в типе BzLong. Подпрограмме передаются два длинных числа (обозначим их l1 и l2). В качестве результата будем возвращать отрицательное число (знак <), положительное (знак >) или нуль (знак =) соответственно ситуациям: первый аргумент меньше, больше или равен второму. Такое решение возвращает больше информации, чем просто "да/нет". Так, в случае, если в некотором алгоритме для каждой из трех ситуаций ll<l2, l1=l2, l1>l2 нужно выполнять свои действия, то достаточно вызвать подпрограмму сравнения один раз и запомнить результат в целой переменной, которая различает эти три ситуации.

Таким образом, если l1.us<>l2.us, то большее число то, у которого больше цифр. Если же количество цифр обоих чисел равны, то будем сравнивать значения цифр, начиная со старших [больших индексов], пока не наступит одно из двух событий - цифры разные [большее число то, у которого больше цифра] или цифры закончились [числа равны].

Фрагмент программы сравнения длинных целых чисел представлен в листинге:

function fun(const l1,l2:Bzlong): integer;

var i:t2;

begin

if l1.us>l2.us then

begin

fun:=m1; writeln('>') end

else if l1.us < l2.us then

begin fun:=-m1 ; writeln('<');end

else begin

i:=l1.us;

while (i>=1) and (l1.mas[i]=l2.mas[i]) do

dec(i);

if i=0 then

begin fun:=0;writeln('=') ;end

else fun:=integer(l1.mas[i])-integer(l2.mas[i]) ;

end;

end;