Длинная арифметика. Способы представления длин.чисел. Операции над длин.числами. Примеры программ

Территория рекламы

27. Длинная арифметика. Способы представления длин.чисел.Операции над длин.числами. Примеры программ.

Известно, что арифметич. действия, выполняемые компом в ограниченном числе разрядов, не всегда позволяют получить точный рез-тат. Более того, мы ограничены диапазоном встроенных типов данных системы, с кот. работам. Напр., необходимо выполнить арифметические действия над очень большим числом – 30! = 265252859812191058636308480000000 ? В таких случаях необходимо позаботится о точном представлении этих чисел в памяти компа и о точном выполнении арифметич.операций над ними.

Числа, для представления которых в стандартных компьютерных типах данных не хватает кол-ва двоичных разрядов, наз-ся «длинными». . Реализация арифм.операций над такими «длинными» числами получила название «длинной арифметики». Организация работы с «длинными» числами во многом зависит от того, как мы представим в компе эти числа.

Существует несколько способов представления длинных чисел в памяти компа. Первый способ представления «длинных» чисел – «длинное» число можно записать, напр, с помощью массива десятичных цифр, кол-во элементов в таком массиве равно количеству значащих цифр в «длинном» числе. Если же, впоследствии, мы будем реализовывать над таким числом арифметические операции, то размер массива должен быть достаточным, чтобы разместить в нём результат. Так, при выполнении умножения длина результирующего массива может быть в два раза больше, чем длина массивов для множителей. При этом в первом элементе массива может располагаться как старшая (самая левая), так и младшая (правая) значащая цифра. Способ записи «длинных» чисел, когда младшая цифра располагается в первом элементе массива, предпочтительнее для организации тех арифметических действий, в кот.обрабатываются цифры от младшей к старшей, напр, при сложении и вычитании столбиком, а сами числа имеют различную длину. Для описания конкретного «длинного» числа требуется еще один параметрдлина текущего числа, расположенного в массиве. Этот параметр можно хранить как в отдельной целочисленной переменной, так и в нулевом эл-те массива.

Пример описания массива для записи «длинных» чисел в языке программирования Турбо-Паскаль:

Пример

Type

Аtype=array[l..1000] of byte;

При орг-ции арифм.операций над длинными числами, с исп-ем первого способа представления, процессор будет непосредственно складывать, вычитать, умножать или делить лишь однозначные числа, след-но, кол-во самих действий при этом будет достаточно большим. Второй способ представления «длинных» чисел и повышения эффективности «длинной» арифметики — это хранение в каждом эл-те массива двух цифр (размещение в каждом элементе массива двузначного числа). Это соотв-ет записи чисел в 100-ичной системе счисления. При этом следует следить за тем, чтобы промежуточный рез-тат умножения двух двузначных чисел не был четырехзначным, так как он не может быть записан в однобайтном типе. Третий способ представления «длинных» чисел и повышения эффективности «длинной» арифметики — это хранение в каждом эл-те массива четырёх цифр. Рассм. третий способ представления. Представим число 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:

Номер элемента в массиве А

0

1

2

3

4

5

6

7

8

9

Значение

9

0

8000

3084

8636

9105

8121

2859

6525

2

Мы можем считать, что наше "длинное" число представлено в  системе счисления с основанием 10000, смешанной с десятичной, а «цифрами» числа являются четырёхзначные числа. Описание такого массива на Turbo-Pascal дополнено нулевым эл-том, в кот. будет храниться текущая длина числа (количество 10000-ичных цифр)

Пример. Описание массива для записи «длинных» чисел третьим способом:

Туре

Btype = array [0. .250] of longint;

Четвёртый способ представления «длинных» чисел – представление их с использ-ем строковых типов данных (string в Turbo-Pascal).

Пятый способ представления «длинных» чисел – представление их с использ-ем динамических структур данных, таких как списки из чисел, являющихся цифрами в записи «длинных» чисел (,напр, 10000-ичных).

При операциях с конечными дробными числами, все значащие цифры записываются выбранным способом представления, место для запятой запоминается, например, в отдельной переменной и учитывается при печати результата. Такой способ соотв-ует операциям над веществен.числами, записанными в формате с фиксированной запятой. 1

end;

Close(h);

end;

{процедура переиндексирования элементов массивов}

procedure Perevorot (l:byte;var t:tmass);

var

i,r:byte;

begin

for i:=1 to (l div 2) do

begin

r:=t[i]; t[i]:=t[l-i+1]; t[l-i+1]:=r;

end;

end;

{процедура дополнения нулями}

procedure Dop ( l3,l4:byte; var t1:tmass);

var

i:byte;

begin

for i:=(l3+1) to l4 do

t1[i]:=0; writeln; l3:=l4;

end;

{процедура сложения}

procedure Mainadd (t,s:tmass;l:byte; var z1:tmass);

var

i:byte;

begin

pr:=0; z1[0]:=0;

for i:=1 to L do

begin

z1[i]:=t[i]+s[i]+pr; pr:=z1[i] div 10;

z1[i]:=z1[i] mod 10; inc(z1[0]);

end;

if pr>0 then

begin

inc(l); z1[l]:=pr; inc(z1[0]);

end;

end;

{основной блок процедуры сложения}

begin

write('******');

ReadData ( f, x);

l1:=x[0];

ReadData ( g,y);

l2:=y[0];

WriteResult1 ( l1, x);

WriteResult1 ( l2, y);

readline;

{первый элемент массива X - младшая цифра 1 слагаемого}

Perevorot (l1,x);

{первый элемент массива Y - младшая цифра 2 слагаемого}

Perevorot (l2,y);

{блок дополнения меньшего слагаемого нулями слева до

длины большего слагаемого}

if l1>l2 then

Dop(l2,l1,y)

else

Dop (l1,l2,x);

{сложение}

WriteResult1 ( l1, x);

WriteResult1 ( l2, y);

readline;

Mainadd (x,y,l1,z);

{вывод результата на экран}

{вывод результата в файл} 3

WriteResult1 ( l1, x);

WriteResult1 ( l2, y);

MultLong;

WriteResult(z);

end;

Ядро подпрограммы сравнения двух длинных целых чиселдлинных чисел

procedure sravnenie;

Type

tmass=array [0..255] of byte;

var

x,y:tmass;

l1,l2,Eq,i:byte;

fl:boolean;

f,g,h:text;

name:string[30];

……………………

{процедура печати результата в файл}

procedure WriteResult;

var

i:word;

begin

write('введите имя файла - результата ');

readLn(name);

assign(h,name);

rewrite(h);

case Eq of

0:begin

write('числа равны');

write(h,'числа равны');

end;

1:begin

write('первое число больше второго');

write(h,'первое число больше второго');

end;

2:begin

write('второе число больше первого');

write(h,'второе число больше первого');

end;

end;

Close(h);

end;

……………………………………………………..

begin

ReadData ( f, x);

l1:=x[0];

ReadData ( g,y);

l2:=y[0];

if x[0]>y[0] then

Eq:=1;

if x[0]<y[0] then

Eq:=2;

if x[0]=y[0] then

begin

i:=1;

fl:=false;

while (i<=x[0]) and (x[i]=y[i]) do

inc(i);

fl:=(i=x[0]+1);

if fl then

Eq:=0

else

if x[i]>y[i] then 5

Eq:=1

В пр-мах, оперирующих с оч большими числами, удобно иметь набор подпрограмм, выполняющих арифм.операции (+, -, * ,div, mod) и операции сравнения (<, <= , >, >=, =, <>), то есть иметь модуль, в котором эти операции реализованы. Реализацию подпрограмм, выполняющих действия над целыми длинными числами см. ниже

Подпрограмма сложения длинных чисел

Type

tmass=array [0..255] of byte;

Var

k,i,j:byte;

cod:char;

procedure AddLong;

var

x,y,z: tmass;i,j: word; l1,l2: byte;

f,g,h:text;ch1:char; name:string[30];

pr:byte;

{процедура чтения слагаемых из файла}

procedure ReadData (Var f1:text;Var x1:tmass);

var

ch:char;

begin

x1[0]:=0;

write('введите имя файла для чтения длинного числа');

Readln(name);

{ $I-}

assign(f1,name); reset(f1);

{$I-}

if ioresult<>0 then

begin

write('ошибка'); exit

end

else

begin

while not eof (f1) do

begin

while not eoln (f1) do

begin

read(f1,ch); inc(x1[0]); x1[x1[0]]:=ord(ch)-ord('0');

end;

readln(f1);

end;

Close(f1); writeln;

end;

end;

{Процедура печати прочитанных слагаемых}

procedure WriteResult1 ( l3: byte; x1:tmass);

var

i:word;

begin

for i:=l3 downto 1 do

begin

write(x1[i]);

end;

writeln;

end;

{процедура печати результата сложения}

procedure WriteResult (Var h:text);;

var

i:word;

begin

write('введите имя файла - результата ');

readLn(name); assign(h,name); rewrite(h);

for i:=z[0] downto 1 do

begin

write(z[i]); write(h,z[i]); 2

WriteResult(z);

end;

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

{основная процедура}

begin

clrscr; write('******');

ReadData ( f, x);

l1:=x[0];

ReadData ( g,y);

l2:=y[0];

WriteResult1 ( l1, x);

WriteResult1 ( l2, y);

readline;

{первый элемент массива X - младшая цифра 1 слагаемого}

Perevorot (l1,x);

{первый элемент массива Y - младшая цифра 2 слагаемого}

Perevorot (l2,y);

z[0]:=0;

for i:=1 to l2 do

begin

if x[i]>=y[i] then

begin

z[i]:=x[i]-y[i];

end

else

begin

z[i]:=x[i]+10-y[i]; x[i+1]:=x[i+1]-1;

end;

inc(z[0]);

end;

for j:=l2+1 to l1 do

begin

z[j]:=x[j]; inc(z[0]);

end;

readline; WriteResult (z);

end;

Ядро подпрограммы умножения длинных чисел

procedure MultLong;

var

i,j,p,q:word;

begin

p:=l1+l2;

Fillchar(z,p+1,0);

for i:=l1 downto 1 do

for j:=l2 downto 1 do

begin

q:=p-i-j+1; z[q]:=z[q]+x[i]*y[j];

if z[q]>9 then

begin

z[q+1]:=z[q+1]+z[q] div 10;

z[q]:=z[q] mod 10;

end;

end;

if z[p]<>0 then z[0]:=p

else z[0]:=p-1;

end;

_________________

Begin

clrscr;

ReadData ( f, x);

l1:=x[0];

ReadData ( g,y);

l2:=y[0]; 4

else

Eq:=2;

end;

WriteResult;

end;

6

28.

← Предыдущая
Страница 1
Следующая →

Скачать

шпора 27.docx

шпора 27.docx
Размер: 27.5 Кб

Бесплатно Скачать

Пожаловаться на материал

Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называется «длинными»

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

История Казахстана, 6 класс, тесты по экзамену

Конституційне право України. Конституціоналізм

Конституційне право України - юридична наука и навчальна дисципліна. Методологія конституційної науки і практики. Конституційно-правові норми і інститути конституційного права України. Джерела конституційного права України. Конституція – Основний Закон держави і суспільства.

Паротурбинная установка ОК-12А (ОК-12А-1)

Лекция по дисциплине «Паротурбинные установки АЭС». Состав, назначение и размещение элементов ПТНА. Тепловая схема питательного турбонасосного агрегата. Устройство паровой турбины ОК-12А, редуктора Р-2 и соединительных муфт.

Что такое гипокауст?

Гипокауст (лат. hypocaustum, от греч. hypó — под, внизу, нижний и kaustós — горячий, раскалѐнный, подогретый) — наиболее распространѐнный тип классической античной, в особенности древнеримской, отопительной системы, предназначенной для обогрева одноэтажных зданий. Тест.

Вопросы по дисциплине “ Управление информационными ресурсами”.

Сохранить?

Пропустить...

Введите код

Ok