Олимпиадные задачи
по информатике
Главная страница
Правила участия и регистрация
О тестировании
Архив задач
Полезные ссылки
Download
Отправить решение
Текущие результаты
Задать вопрос на форуме
О жюри
Длинная арифметика
Задачи на эту тему.
Статья С.М.Окулова взята на сервере газеты "Информатика"


Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например,

30!=265252859812191058636308480000000?

В таких случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними.

Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются "длинными". Реализация арифметических операций над такими "длинными" числами получила название "длинной арифметики".

Организация работы с "длинными" числами во многом зависит от того, как мы представим в компьютере эти числа. "Длинное" число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. Но если мы будем реализовывать арифметические операции над этим числом, то размер массива должен быть достаточным, чтобы разместить в нем и результат, например, умножения.

Существуют и другие представления "длинных" чисел. Рассмотрим одно из них.

Представим наше число 30!=265252859812191058636308480000000 в виде:

30!=2 *(104)8 + 6525 * (104)7 + 2859 * (104)6 + 8121 * (104)5 + 9105 * (104)4 + 8636 * (104)3 + 3084 * (104)2 + 8000 * (104)1 + 0000 * (104)0

Это представление наталкивает на мысль о массиве, представленном в табл.1
Таблица 1
Номер элемента в массиве А 0 1 2 3

4

5 6 7 8 9
Значение   9 

  0 

8000 3084 8636 9105 8121 2859 6525   2 

Мы можем считать, что наше "длинное" число представлено в 10000-10 системе счисления (десятитысячно-десятичная система счисления, приведите аналогию с восьмерично-десятичной системой счисления), а "цифрами" числа являются четырехзначные числа.

Возникают вопросы. Что за 9 в А [0], почему число хранится "задом наперед"? Ответы очевидны, но подождем с преждевременными объяснениями. Ответы на вопросы будут ясны из текста.

Примечание. Мы работаем с положительными числами!

Первая задача
Ввести "длинное" число из файла


Решение
Начнем с описания данных.

Const MaxDig=1000; {Максимальное количество цифр - четырехзначных!}
Osn=10000; {Основание нашей системы счисления, в элементах массива храним четырехзначные числа}
Type Tlong=Array[0..MaxDig] Of Integer;
{Максимальное количество десятичных цифр в нашем числе}

Алгоритм ввода "длинного" числа из файла рассмотрим на конкретном примере.

Пусть в файле записано число 23851674 и основанием (Osn) является 1000 (храним по три цифры в элементе массива А). Изменение значений элементов массива А в процессе ввода (посимвольного в переменную Ch) отражено в табл. 2.

Таблица 2.
A[0]A[1]A[2]A[3]ChПримечание
367485123-Конечное состояние
00002Начальное состояние
120031-й шаг
1230082-й шаг
12380053-й шаг
23852014-й шаг: старшая цифра элемента А [1] перешла в пока "пустой" элемент А[2]
285123065-й шаг
2516238076-й шаг
3167385247-й шаг
3674851238-й шаг


Проанализируем таблицу (и получим ответы на поставленные выше вопросы).

1. В А[0] храним количество задействованных (ненулевых) элементов массива А - это уже очевидно.

2.При обработке каждой очередной цифры входного числа старшая цифра элемента массива с номером i становится младшей цифрой числа в элементе i+1, а вводимая цифра будет младшей цифрой числа из А[1]. В результате работы нашего алгоритма мы получили число, записанное "задом наперед".

Примечание (методическое): Можно ограничиться этим объяснением и разработку процедуры вынести на самостоятельное задание. Можно продолжить объяснение. Например, выписать фрагмент текста процедуры перенос старшей цифры из A[i] в младшую цифру А[i+1], т.е. сдвиг уже введенной части числа на одну позицию вправо:

For i :=A[0] DownTo 1 Do
Begin
A[i+l] :=A[i+l] + (Longint(A[i]) * 10) Div Osn;
A[i] :=(LongInt(A[i]) * 10) Mod Osn;
End;


Пусть мы вводим число 23851674 и первые 6 цифр уже разместили "задом наперед" в массиве А. В символьную переменную считали очередную цифру "длинного" числа - это 7. По нашему алгоритму эта цифра 7 должна быть размещена младшей цифрой в А[1]. Выписанный фрагмент программы "освобождает" место для этой цифры. В таблице отражены результаты работы этого фрагмента.
iA[1]A[2]A[3]Ch
251623807
25163802
11603852

После этого остается только добавить текущую (считанную в ch) цифру "длинного" числа к А[1] и изменить значение А[0].

Procedure ReadLong(Var A : Tlong);
Var ch : char; i : Integer;
Begin
FillChar(A, SizeOf(A), 0)
Read(ch);
While Not(ch In ['0'..'9']) Do Read(ch);
{пропуск не цифр во входном файле}
While ch In ['0'..'9'] Do
Begin
For i :=A[0] DownTo 1 Do
Begin
{"протаскивание" старшей цифры в числе из A[i]в младшую цифру числа из A[i+l]}
A[i+l] :=A[i+l] + (LongInt(A[i]) * 10) Div Osn;
A[i] :=(LongInt(A[i]) * 10) Mod Osn
End;
A[1] :=A[l] + Ord(ch) - Ord('0');
{добавляем младшую цифру к числу из А[1]}
If A[A[0]+1] > 0 Then Inc(A[0]);
{изменяем длину, число задействованных элементов массива А}
Read(ch)
End
End;


Вторая задача
Вывод "длинного" числа в файл или на экран


Решение
Казалось бы, нет проблем - выводи число за числом. Однако в силу выбранного нами представления "длинного" числа мы должны всегда помнить, что в каждом элементе массива хранится не последовательность цифр "длинного" числа, а значение числа, записанного этими цифрами. Пусть в элементах массива хранятся четырехзначные числа. Тогда "длинное" число 128400583274 будет в массиве А представлено следующим образом:
A[0]A[1]A[2]A[3]
33274581284


При выводе "длинного" числа из массива нам необходимо вывести 0058, иначе будет потеря цифр. Итак, незначащие нули также необходимо выводить. Процедура вывода имеет вид:

Procedure WriteLong(Const A : Tlong);
Var ls, s : String; i : Integer;
Begin
Str(Osn Div 10, Is);
Write(A[A[0]]; {выводим старшие цифры числа}
For i :=A[0] - l DownTo 1 Do
Begin
Str(A[i], s);
While Length(s) < Length(Is) Do s :='0' + s;
{дополняем незначащими нулями}
Write(s)
End;
WriteLn
End;


Третья задача

Предварительная работа по описанию способа хранения, вводу и выводу "длинных" чисел выполнена. У нас есть все необходимые "кирпичики", например, для написания программы сложения двух "длинных" положительных чисел.

Исходные числа и результат храним в файлах. Назовем процедуру сложения SumLongTwo.
Тогда программа ввода двух "длинных" чисел и вывода результата их сложения будет иметь следующий вид:

Var A, B, C : Tlong;
Begin
Assign(Input, 'Input.txt'); Reset(Input);
ReadLong(A); ReadLong(B)
Close(Input);
SumLongTwo(A, B, C);
Assign(Output, 'Output.txt');
Rewrite(Output);
WriteLong(C);
Close(Output)
End.
Алгоритм процедуры сложения можно объяснить на простом примере. Пусть А=870613029451, В=3475912100517461.

ia[i]b[i]c[1]c[2]c[3]c[4]
1945274616912100
21302516912135400
3870691216912135478271
4034756912135478273476

Алгоритм имитирует привычное сложение столбиком, начиная с младших разрядов. И именно для простоты реализации арифметических операций над "длинными" числами используется машинное представление "задом наперед".

Результат: С=3476782713546912.

Ниже приведен текст процедуры сложения двух "длинных" чисел.

Procedure SumLongTwo(A, B : Nlong; Var C : Tlong);
Var i, k : Integer;
Begin
FillChar(C, SizeOf (C), 0)
If A[0] > B[0] Then k :=A[0] Else k :=B[0];
For i :=l To k Do
Begin С [i+1] :=(C[i] + A[i] + B[i]) Div Osn;
C[i] :=(C[i] + A[i] + B[i]) Mod Osn
{Есть ли в этих операторах ошибка?}
End;
If C[k+l]=0 Then C[0] :=k Else C[0] :=k + l
End;


Четвертая задача
Реализация операций сравнения для "длинных" чисел (А=В, А <В, А> В, А <=В, А>=В)


Function Eq(A, B : TLong) : Boolean;
Var i : Integer;
Begin
Eq :=False;
If A[0] <> B[0] Then Exit
Else Begin
i :=l;
While (i <=A[0]) And (A[i]=B[i]) Do Inc(i);
Eq :=i=A[0] + l
End
End;


Реализация функции А> В также прозрачна.

Function More(A, B : Tlong) : Boolean;
Var i : Integer;
Begin If A[0] < B[0] Then More :=False
Else If A[0] > B[0] Then More :=True
Else Begin
i :=A[0];
While (i > 0) And (A[i]=B[i]) Do Dec(i);
If i=0 Then More :=False
Else If A[i] > B[i] Then More :=True
Else More:=False
End
End;


Остальные функции реализуются через функции Eq и More.

Function Less(A, B : Tlong) : Boolean; {A < B}
Begin
Less :=Not(More(A, B) Or Eq(A, B))
End;
Function More_Eq(A, B : Tlong) : Boolean; {A >=B}
Begin
More_Eq :=More(A, B) Or Eq(A, B)
End;
Function Less_Eq(A, B : Tlong) : Boolean; {A <=B}
Begin
Less_Eq :=Not More(A, B)
End;


Для самостоятельного решения может быть предложена следующая, более сложная, задача
Требуется разработать функцию, которая выдает 0, если А больше В, 1, если А меньше В, и 2 при равенстве чисел. Но сравнение должно быть выполнено с учетом сдвига. О чем идет речь?


Поясним на примере.
Пусть А=56784, а В=634. При сдвиге числа В на 2 позиции влево функция должна сказать, что В больше А, без сдвига, что А больше В.

Другой пример.
При А=56700, а В=567 и сдвиге 2 функция должна "сказать", что числа равны.

Решение может иметь следующий вид:

Function More(Const А, В : Tlong; Const sdvig : Integer) : Byte;
Var i : Integer;
Begin
If A[0] > B[0] + sdvig Then More :=0
Else
If A[0] < B[0] + sdvig Then More :=l
Else Begin
i :=A[0];
While (i > sdvig) And
(A[i]=B[i-sdvig]) Do Dec(i);
If i=sdvig Then Begin
More:=0;
{совпадение чисел с учетом сдвига}
For i :=1 To sdvig Do
If A[i] > 0 Then Exit;
More :=2;
{числа равны, "хвост" числа А равен нулю}
End
Else More :=Byte(A[i] < B[i-sdvig])
End
End;


Пятая задача
Умножение длинного числа на короткое. Под коротким понимается целое число типа LongInt.


Процедура очень походит на процедуру сложения двух длинных чисел.

Procedure Mul(Const A : TLong; Const К : Longlnt; Var С : TLong);
Var i : Integer;
{результат - значение переменной С}
Begin
FillChar (С, SizeOf(С), 0);
If K=0 Then Inc(С[0]){умножение на ноль}
Else Begin
For i:=l To A[0] Do
Begin
C[i+l] :=(LongInt(A[i]) * K + C[i]) Div Osn;
C[i] :=(LongInt(A[i])* K + C[i]) Mod Osn
End;
If C[A[0]+1] > 0 Then C[0]:=A[0] + 1
Else C[0]:=A[0]
{определяем длину результата}
End
End;


Шестая задача
Вычитание двух длинных чисел с учетом сдвига


Если понятие сдвига пока не понятно, то оставьте его в покое, на самом деле вычитание с учетом сдвига потребуется при реализации операции деления. В начале выясните логику работы процедуры при нулевом сдвиге.

Введем ограничение: число, из которого вычитают, больше числа, которое вычитается. Работать с "длинными" отрицательными числами мы не умеем.

Процедура была бы похожа на процедуры сложения и умножения, если бы не одно "но" - заимствование единицы из старшего разряда вместо переноса единицы в старший разряд. Например, в обычной системе счисления мы вычитаем 9 из 11 - идет заимствование 1 из разряда десятков, а если из 10000 вычитаем 9 - процесс заимствования несколько сложнее.

Procedure Sub (Var A : TLong; Const B : TLong; Const sp : Integer);
Var i, j : Integer;
{из А вычитаем В с учетом сдвига sp, результат вычитания в А}
Begin
For i :=l To B[0] Do
Begin Dec(A[i+sp], B[i]);
j:=i;{*}
{реализация сложного заимствования}
while (A[j+sp] < 0) and (j <=A[0]) Do
Begin{*}
Inc(A[j+sp], Osn)
Dec(A[j+sp+l]); Inc(j); {*}
end; {*}
{Реализация простого заимствования.
Если операторы, отмеченные *, заменить
на нижеприведенные операторы в фигурных скобках, то,
по понятным причинам, логика не будет работать
при всех исходных данных. Можно сознательно сделать
ошибку и предложить найти ее - принцип "обучение через ошибку"}
{If A[i+sp]<0 Then Begin Inc(A[i+sp], Osn);
Dec (A[i+sp+l]);End;}
End;
i :=A[0];
While (i > l) And (A[i]=0) Do Dec(i);
A[0] :=i
{корректировка длины результата операции}
End;



Рекомендуется выполнить трассировку работы данной процедуры, например, для следующих исходных данных. Число А равно 100000001000000000000, число В - 2000073859998.

Седьмая задача


Деление двух длинных чисел, т.е. нахождение целой части частного и остатка.Написать исходную (без уточнений) часть логики не составляет труда. Это:

Procedure Long_Div_Long(Const A, B : TLong; Var Res, Ost : TLong);
Begin
FillChar(Res, SizeOf(Res), 0); Res[0] :=1;
FillChar(Ost, SizeOf(Ost), 0); 0st[0] :=1;
Case More(A, B, 0) Of
0: MakeDel(A, B, Res, Ost);
{А больше В, пока не знаем, как выполнять операцию - "выносим" в процедуру}
1: Ost:=A; {А меньше В}
2: Res[l] :=l; {А равно В}
End;
End;


А дальше? Дальше начинаются проблемы. Делить столбиком нас научили в школе. Например:


1000143123567 |73859998
- 73859998 |----------
--------- |13541 (Целая часть частного)
261543143
- 221579994
----------
399631495
- 369299990
---------
303315056
- 295439992
----------
78750647
- 73859998
--------
4890649 (Остаток)
Что мы делали? На каждом этапе в уме подбирали цифру (1, 3, 5 и т.д.), такую, что произведение этой цифры на делитель дает число меньшее, но наиболее близкое к числу... Какому? Это трудно сказать словами, но из примера ясно. Зачем нам это делать в уме, пусть делает компьютер. Однако упростим пример, оставим его для тестирования окончательной логики процедуры, тем более что и числа "длинные". Пусть число А будет меньше В • 10, тогда в результате (целой части деления) будет одна цифра. Например, А равно 564, а В — 63 и простая десятичная система счисления. Попробуем подобрать цифру результата, но не методом прямого перебора, а методом деления отрезка пополам. Пусть Down — верхняя граница интервала изменения подбираемой цифры, Up - нижняя граница интервала, Ost равен делимому

DownUpС=В * ( (Down + Up) Div 2)Ost=564
010315=63 * ( (0 + 10) Div 2)C
510441=63 * ( (5 + 10) Div 2)C
710504=63 * ( (7 + 10) Div 2)C
810567=63 * ( (8 + 10) Div 2)C> Ost
89504=63 * ( (8 + 9) Div 2C
Итак, результат — целая часть частного — равен (Up + Down) Div 2, остаток от деления - разность между значениями Ost и С. Нижнюю границу (Down) изменяем, если результат (С) меньше остатка, верхнюю (Up), если больше.

Усложним пример.
Пусть А равно 27856, а -В — 354. Основанием системы счисления является не 10, а 10000.

DownUpCost=27856
0100001770000C> Ost
05000885000C> Ost
02500442500C> Ost
01250221250C> Ost
0625110448C> Ost
031255224C> Ost
015627612C
7815641418C> Ost
7811734338C> Ost
789730798C> Ost
788729028C> Ost
788228320C> Ost
788027966C> Ost
787927612C


Целая часть частного равна 78, остаток от деления — 27856 минус 27612, т.е. 244.
Пора приводить процедуру.
Используемые "кирпичики":

  • функция сравнения чисел (More) с учетом сдвига;

  • функция умножения длинного числа на короткое (Mul) описаны выше


  • Function FindBin(Var Ost : Tlong; Const В: TLong; Const sp : Integer) : Longint;
    Var Down, Up : Word; C : TLong;
    Begin
    Down :=0;Up :=0sn;
    {основание системы счисления}
    While Up - l > Down Do
    Begin
    {Есть возможность преподавателю сделать
    сознательную ошибку. Изменить условие
    цикла на Up>Down. Результат - зацикливание
    программы}
    Mul(В, (Up + Down) Div 2, C);
    Case More(Ost, C, sp) Of
    0: Down :=(Down + Up) Div 2;
    1: Up :=(Up + Down) Div 2;
    2: Begin Up :=(Up + Down) Div 2; Down :=Up End;
    End;
    End;
    Mul(B, (Up + Down) Div 2, C);
    If More (Ost, C, 0)=0 Then Sub(Ost, C, sp)
    {находим остаток от деления}
    Else begin Sub (C, Ost, sp); Ost :=C end;
    FindBin :=(Up + Down) Div 2;
    {целая часть частного}
    End;


    Осталось разобраться со сдвигом, значением переменной sp в нашем изложении. Опять вернемся к обычной системе счисления и попытаемся разделить, например, 635 на 15. Что мы делаем? Вначале делим 63 на 15 и формируем, подбираем в уме первую цифру результата. Подбирать с помощью компьютера мы научились. Подобрали — это цифра 4, и это старшая цифра результата. Изменим остаток. Если вначале он был 635, то сейчас стал 35. Вычитать с учетом сдвига мы умеем. Опять подбираем цифру. Вторую цифру результата. Это цифра 2 и остаток 5. Итак, результат (целая часть) 42, остаток от деления 5. А что изменится, если основанием будет не 10, а 10000 ? Логика совпадает, только в уме считать несколько труднее, но ведь у нас же есть молоток под названием компьютер — пусть он вбивает гвозди.

    Procedure MakeDel(Const A, B : TLong; Var Res, Ost : TLong);
    Var sp : Integer;
    Begin
    Ost :=A; {первоначальное значение остатка}
    sp :=A[0] - B[0];
    If More(A, B, sp)=l Then Dec(sp);
    {B * Osn > A, в результате одна цифра}
    Res[0] :=sp + l;
    While sp >=0 Do
    Begin
    {находим очередную цифру результата}
    Res[sp + 1] :=FindBin(Ost, B, sp);
    Dec(sp)
    End
    End;