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

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

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 Кб

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

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

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

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

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

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

Закон Республики Казахстан «О государственной статистике»

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

Сущность, структура политической власти

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

Основні жанри наукового стилю

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

Программа ГЭК Экономическая социология

Программа комплексного Государственного экзамена по специальности «Социология» специализации «Экономическая социология»

Кинематика механического движения

Практическое занятие Цель занятия: отработать навык решения задач по кинематике.

Сохранить?

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

Введите код

Ok