ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеМетоды и приемы программирования > Арифметика длинных целых чисел
Арифметика длинных целых чисел
Одним из широко распространенных типов задач, предлагаемых на олимпиадах школьников по информатике, является реализация так называемой арифметике длинных целых чисел. Проблема состоит в том, что максимальные (минимальные) значения целочисленных типов определяются разработчиками систем программирования и в некоторых случаях эти ограничения не позволяют решить поставленную задачу. Например, в Turbo Pascal 7.0 наибольшее значение данных типа integer ограничено значением предопределенной в системе константы MAXINT = 32767.  В случае если в результате каких-либо действий целочисленная переменная должна будет получить значение выходящее за диапазон -MAXINT..MAXINT, то система контроля значений ограниченных типов данных выдаст сообщение об ошибке. Таким образом, переменные целого типа являются максимум пятиразрядными, да и то из пятиразрядных чисел могут задавать примерно только третью часть. То есть произведение трехзначного и четырехзначного чисел уже невозможно вычислить, так как оно будет иметь не менее шести десятичных знаков. Увеличить число разрядов в целом числе можно в 2 раза, если использовать вместо типа integer тип longint, однако это поможет нормально обрабатывать только девятиразрядные десятичные целые числа, а в некоторых задачах этого тоже не достаточно. В этом случае программисту приходится самостоятельно реализовывать «длинную арифметику».
В наших предыдущих статьях мы рассматривали системы счисления. Главным фактом, необходимым для решения новых задач, является то, что в позиционной системе счисления число задается последовательной записью его цифр. Таким образом, моделью числа является заданный набор цифр этого числа, который можно записать в массив, а также целое число, которое имеет своим значением текущее количество разрядов числа.
Например, возьмем десятичное целое число 21239809231234. Это число можно представить в виде числа N=14 – количество разрядов и массива A из следующих 14 элементов:
 
2
1
2
3
9
8
0
9
2
3
1
2
3
4
 
Напомним, что подобное представление целых чисел мы использовали в теме «Задачи на перечисление». Кстати, там ты рассматривали K-разрядные целые числа в системе счисления по основанию D.
Рассмотрим две относительно простые задачи.
 
Задача 1. Ввести N-разрядное десятичное целое число A и найти его сумму с целым числом B, 0<=B<10.
 
Решение. Рассмотрим частный случай алгоритма сложения чисел «в столбик». Введем дополнительную переменную P — перенос, которая первоначально будет иметь значение В, а также переменную I — номер разряда.  Начиная с младшего разряда (I=1), число P прибавляется к I-тому разряду числа A, при этом результатом является число C. Младшая цифра числа С, равная остатку от деления С на 10 (C mod 10), заносится в соответствующий элемент массива A. Затем переменная P получает значение C div 10 – перенос в следующий разряд. До тех пор, пока перенос будет отличаться от 0, следует повторять действие с переходом к следующему разряду. При этом может случиться так, что в результирующем значении числа увеличится количество разрядов по сравнению с начальным (например, 999+2=1001), узнать об этом можно проверив чему равно значение переменной I после завершения цикла и при необходимости изменить значение N – числа разрядов. Программа, реализующая описанный алгоритм, приведена ниже.
 
program AplusB;
var
   A:array [1..30] of integer;
   b,c,p,i,n:integer;
begin
write('n=');
readln(n);
writeln('read A');
for i:=n downto 1 do
    readln(a[i]);
write('b=');
readln(b);
i:=1;
p:=b;
repeat
c:=a[i]+p;
a[i]:=c mod 10;
p:=c div 10;
i:=i+1
until p=0;
if i+1>n then n:=i-1;
for i:=n downto 1 do
write(a[i]);
writeln
end.
 
Отметим, что наша программа даст корректный результат и в том случае, если число B будет двух или более значным.
 
Задача 2. Пусть теперь два массива A и B, состоящие из N и K элементов соответственно содержат цифры двух десятичных чисел. Найти массив C, состоящий из L элементов являющихся цифрами числа C – суммы A и B (c=a+b).
 
Решение. Для решения этой задачи реализуем алгоритм сложения «в столбик». В нем, как известно очередная цифра результата получается после суммирования соответствующих цифр слагаемых и переноса из предыдущего разряда. При этом если полученная сумма больше 10, то в результат записывается младшая ее цифра, а старшая переносится в следующий разряд. Программа решения этой задачи приведена ниже.
 
program AplusB;
var
   A,B,C:array [1..30] of integer;
   p,i,n,k,l:integer;
begin
write('n=');
readln(n);
writeln('read A');
for i:=n downto 1 do
    readln(a[i]);
write('k=');
readln(k);
writeln('read B');
for i:=k downto 1 do
    readln(b[i]);
i:=1;
p:=0;
repeat
c[i]:=a[i]+b[i]+p;
p:=c[i] div 10;
c[i]:=c[i] mod 10;
i:=i+1
until (i>n)and(i>k)and(p=0);
l:=i-1;
for i:=l downto 1 do
write(c[i]);
writeln
end.
 
 
Задача 3. Пусть массивы A и B, состоящие из N и K элементов соответственно содержат цифры двух десятичных чисел, причем a>b. Найти массив C, состоящий из L элементов являющихся цифрами числа C – разности A и B (c=a-b).
 
Решение. Эта задача также может быть решена алгоритмом известным из начальной школы «вычитание в столбик». В отличие от сложения здесь возникает не перенос в следующий разряд «лишних» цифр, а заем из старших разрядов «недостающих». После получения результата следует определить сколько разрядов фактически содержит вычисленная разность чисел. Программа, реализующая алгоритм вычитания «в столбик», приведена ниже.
 
program AminusB;
var
   A,B,C:array [1..30] of integer;
   p,i,n,k,l:integer;
begin
write('n=');
readln(n);
writeln('read A');
for i:=n downto 1 do
    readln(a[i]);
write('k=');
readln(k);
writeln('read B');
for i:=k downto 1 do
    readln(b[i]);
for i:=k+1 to n do
    b[i]:=0;
p:=0;
for i:=1 to n do
begin
c[i]:=a[i]-b[i]-p;
p:=0;
while c[i]<0 do
      begin
      c[i]:=c[i] + 10;
      p:=p+1
      end;
end;
l:=n;
while c[l]=0 do
      l:=l-1;
for i:=l downto 1 do
    write(c[i]);
writeln
end.
 
Отметим, что важным является то условие, что число a-уменьшаемое, больше чем число b-вычитаемое.
 
Задача 4. Пусть массивы A и B, состоящие из N и K элементов соответственно содержат цифры двух десятичных чисел. Найти массив C, состоящий из L элементов являющихся цифрами числа C – произведения A и B (c=a*b).
 
Решение. Рассмотрим алгоритм умножения «в столбик» на примере 123*322:
 
 
a=
 
 
 
1
2
3
b=
 
 
*
3
2
2
 
 
 
 
2
4
6
 
 
+
2
4
6
 
  
+
3
6
1
 
 
c=
 
3
8
8
0
6
 
Из примера видно, что сначала вычисляются произведения первого сомножителя на цифры второго сомножителя и записываются с последовательным смещением. Это смещение определяется тем, что мы умножаем первый сомножитель не просто на цифры числа, а на количество единиц, десятков, сотен и т.д., то есть фактически мы ищем сумму 123*2+123*20+123*300, а завершающие нули промежуточных произведений не записываются для экономии времени, сил, чернил и т.п. Реализовывать такой алгоритм нам было бы не совсем удобно, так как нужно сначала вычислять эти промежуточные произведения и хранить их во вспомогательных массивах, а затем складывать. Удобнее для реализации на компьютере рассматривать умножение сумм следующего вида (100+20+3)*(300+20+2)=(1*102+2*101+3*100)*(3*102+2*101+2*100), перемножим выражения в скобках, получим:
 
(2*102+4*101+6*100)+(2*103+4*102+6*101)+(3*104+6*103+1*102)
 
После группировки подобных при одинаковых степенях 10, получим:
 
(3)*104+(2+6)*103+(2+4+1)*102+(4+6)*101+(6)*100
 
А после суммирования сгруппированных элементов в результате получим:
 
(*)           3*104+8*103+7*102+10*101+6*100
 
Элемент 10*101=1*102+0*101, с учетом этого получим окончательный результат:
 
(**)           3*104+8*103+8*102+0*101+6*100
 
Из этого примера можно предложить следующий алгоритм решения задачи: сначала найти сумму произведений множителей при одинаковых степенях 10 (*), а затем откорректировать результат, выполнив перенос переполненных разрядов в старшие (**). Для решения задачи возьмем массивы, в которых индексы начинаются с нуля, и запишем цифры исходных чисел в ячейки с индексами, соответствующими степеням их десятичных множителей (разрядов). Тогда суммы произведений множителей можно вычислять по правилу ,где индексы i и j пробегают все значения от 0 до степени наивысшего десятичного множителя.
Приведем фрагмент программы для решения этой задачи соответствующий вычислению сумм произведений. Здесь a, b, c – массивы, l и n – количество цифр в числах a и b соответственно.
 
for i:=0 to l-1 do
for j:=0 to n-1 do
          c[i+j]:= c[i+j]+a[i]*b[j];
 
К сформированному в результате этой операции массиву c, состоящему из l+n элементов, следует применить операцию переноса переполненных разрядов, а затем вывести результат на печать.
В задачах к этой теме, будет предложено реализовать программу в полном объеме самостоятельно.
 
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске
валберис http://wiki-buy.ru/валберис/ . Современные издания предлагают дизайн штор для кухни, просто потрясающий воображение.