Программирование
<<  Тип, имя и значение переменной Алгоритмизация и программирование  >>
«Длинная» арифметика
«Длинная» арифметика
Тип в Borland Pascal
Тип в Borland Pascal
Переполнение
Переполнение
Сложение «длинных» чисел
Сложение «длинных» чисел
Текст программы сложения «длинных» чисел
Текст программы сложения «длинных» чисел
Реализация вычитания на языке Pascal
Реализация вычитания на языке Pascal
Сравнение чисел
Сравнение чисел
Function compare
Function compare
Ввод и вывод длинного числа
Ввод и вывод длинного числа
Вывод
Вывод
Ввод
Ввод
Функция sizeof(w)
Функция sizeof(w)
Процедура Fillchar
Процедура Fillchar
Пример
Пример
Procedure readhuge
Procedure readhuge
Умножение длинного числа на короткое
Умножение длинного числа на короткое
Деление длинного числа на короткое
Деление длинного числа на короткое
Function divide
Function divide
Умножение двух длинных чисел
Умножение двух длинных чисел
Procedure multiplyHuge
Procedure multiplyHuge
Презентация «Длинная арифметика». Размер 63 КБ. Автор: Учитель.

Загрузка...

Длинная арифметика

содержание презентации «Длинная арифметика.ppt»
СлайдТекст
1 «Длинная» арифметика

«Длинная» арифметика

«Длинная» арифметика.

2 Тип в Borland Pascal

Тип в Borland Pascal

Тип в Borland Pascal. Тип в Delphi. Тип в C++. Диапазон значений. Размер одной переменой этого типа. Shortint. Shortint. Char. -128..127. 1 байт. Byte. Byte. unsigned char. 0..255. 1 байт. Integer. Smallint. Short. -32768..32767. 2 байта. Word. Word. unsigned short. 0..65535. 2 байта. Longint. Longint (или integer). Int. -2147483648..2147483647. 4 байта. Отсутствует. Longword. unsigned int. 0..4294967295. 4 байта. Отсутствует. Int64. long long. -263..263-1. 8 байт. Отсутствует. Отсутствует. unsigned long long. 0..264-1. 8 байт.

3 Переполнение

Переполнение

Если работать с переменной типа integer (int) и число, которое хранится в переменной становится больше 2147483647 или меньше -2147483648, то произойдет переполнение. В C++ и на Pascal (при выключенном ключе компиляции {$Q-}) программа продолжит свое выполнение, но число в переменной будет записано неверное. Если в начале программы на Pascal написать {$Q+}, то при возникновении такой ошибки программа аварийно прекратит свое выполнение. Эта возможность помогает искать ошибки, связанные с переполнением. В C++ такая возможность не предусмотрена. Стандартных типов для хранения чисел, состоящих из 20 и более цифр, в языках программирования нет, поэтому удобно хранить цифры числа в массиве. Одна цифра — это число от 0 до 9, а значит, ее можно хранить в переменной любого размера. При таком способе хранения можно работать с числами произвольного размера. В ячейке номер 0 можно хранить количество цифр данного числа.

4 Сложение «длинных» чисел

Сложение «длинных» чисел

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

5 Текст программы сложения «длинных» чисел

Текст программы сложения «длинных» чисел

Текст программы сложения «длинных» чисел. Const DMAX = 100; type thuge = array [0..Dmax] of integer; procedure add(var a, b : thuge); {функция прибавляет к числу a число b} var i, r : integer;{r - обозначает сколько у нас "в уме"} begin if a[0] < b[0] then a[0] := b[0]; {складывать нужно до размера большего числа} r := 0; {при сложение младших цифр в уме у нас 0} for i := 1 to a[0] do begin a[i] := a[i] + b[i] + r; {сумма очередных цифр и переноса} if a[i] >= 10 then {случай, когда происходит перенос в следующий разряд} begin r := 1; dec(a[i], 10); end else begin {случай, когда переноса не происходит} r := 0; end; end; {если после сложения остался еще перенос, то нужно добавить еще одну цифру} if r > 0 then begin inc(a[0]); a[a[0]] := r; end; end;

6 Реализация вычитания на языке Pascal

Реализация вычитания на языке Pascal

Реализация вычитания на языке Pascal. procedure subtract(var a, b : thuge); {функция вычитает из числа a число b} var i, r : integer; {r - обозначает, был ли заем единицы из текущего разряда} begin r := 0; {заем из младшего разряда отсутствует} for i := 1 to a[0] do begin a[i] := a[i] - b[i] - r; {разность очередных цифр с учетом заема} if a[i] < 0 then {случай, когда происходит заем из следующего разряда} begin r := 1; inc(a[i], base); end else begin {случай, когда заем не происходит} r := 0; end; end; {Разность может содержать меньше цифр, поэтому нужно при необходимости уменьшить количество цифр} while (a[0] > 1) and (a[a[0]] = 0) do begin dec(a[0]); end; end;

7 Сравнение чисел

Сравнение чисел

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

8 Function compare

Function compare

Сравнение чисел. Function compare(var a, b : thuge) : integer; {a < b => -1 a > b => 1 a = b => 0} var i : integer; begin {сравнение по количеству цифр} if a[0] < b[0] then begin compare := -1; exit; end; if a[0] > b[0] then begin compare := 1; exit; end; {сравнение в случае одинакового количества цифр} for i:= a[0] downto 1 do begin if a[i] < b[i] then begin compare := -1; exit; end; if a[i] > b[i] then begin compare := 1; exit; end; end; compare := 0; end;

9 Ввод и вывод длинного числа

Ввод и вывод длинного числа

Ввод и вывод длинного числа. Так как тип thuge не является стандартным, то его нельзя прочитать, используя просто функцию read и выводить с помощью функции write. Для того, чтобы вывести число, записанное в десятичной системе счисления достаточно последовательно вывести цифры, начиная со старшей. Если число записано в системе счисления 10K, то это не совсем верно. Число 109 в 100-ричной системе счисления состоит из двух цифр: 1 и 9. Поэтому нужно быть внимательным при выводе чисел, состоящих из маленького количества цифр, так как к таким цифрам при выводе необходимо дописать лидирующие нули. Однако к самой первой цифре приписывать лидирующие нули не нужно. Например, число 128400583274 в с\с 104, где в одном элементе массива хранится 4 цифры. При выводе необходимо вывести не 58, а 0058.

10 Вывод

Вывод

Вывод. procedure writeHuge(var a : thuge); var i : integer; begin for i:= a[0] downto 1 do begin write(a[i]); end; writeln; end;

11 Ввод

Ввод

Ввод. При чтении длинного числа нужно помнить, что цифры записываются в обратном порядке. Но в случае системы счисления большей 10, «десятичные цифры» внутри цифры большей системы счисления идут в прямом порядке. Например, число 12345678 в 100-ричной системе счисления будет записано как: 78, 56, 34, 122.

12 Функция sizeof(w)

Функция sizeof(w)

Функция sizeof(w). Функция sizeof(w) возвращает количество байт (мощность типа), занимаемых переменной данного типа. В результате можно, например, узнать, что переменные типа word занимают 2 байта. Var w : word; BEGIN write(' w='); readln(w); writeln('size of byte=', sizeof(w),' w=', w); readln; END.

13 Процедура Fillchar

Процедура Fillchar

Процедура Fillchar. Процедура заполняет произвольную переменную х побайтно, начиная с первого байта. Процедура Fillchar(var x; c:word; ch:value); Где x – заполняемая переменная, может иметь любой тип; С –количество заполняемых байт в переменной х; Ch – выражение любого порядкового типа, задающее образец заполнения. При заполнении переменной х процедура не контролирует длину этой переменной – контроль за правильным значением счетчика с возлагается на программиста. Если х – строка, то при заполнении будет изменен ее нулевой байт, содержащий текущую длину строки.

14 Пример

Пример

Пример. var i:integer; s: string; begin write('i='); readln(i); fillchar(s,10,49); writeln(ord(s[0]),' ',s); fillchar(i,1,1); writeln('i=',i); readln end. Результат работы программы при i=32000: 49 111111111 i=32001.

15 Procedure readhuge

Procedure readhuge

Ввод. Procedure readhuge(var a : thuge); var i : integer; s : string; begin read(s); {чтение строки} fillchar(a, sizeof(a), 0); a[0] := length(s); {вычисление количества цифр} for i:= 1 to a[0] do a[i] := ord(s[a[0]-i+1]) - ord('0'); end;

16 Умножение длинного числа на короткое

Умножение длинного числа на короткое

Умножение длинного числа на короткое. Последовательно умножаем короткое число на каждую цифру длинного числа, начиная с младшей цифры. Записываем результат и некоторую часть произведения переносим в следующий разряд. procedure multiply(var a : thuge; b : integer); {функция умножает число a на короткое число b} var i, r : integer; {r - обозначает перенос в текущий разряд} begin r := 0; {перенос в младший разряд отсутствует} for i := 1 to a[0] do begin a[i] := a[i] * b + r; {произведение очередной цифры и короткого числа с учетом переноса в текущий разряд} r := a[i] div base; {вычисление переноса в следующий разряд} dec(a[i], r * base); {оставляем только часть произведения меньшую base} end; {Если после умножения остался еще перенос, то нужно добавить еще цифру. Может потребоваться добавить несколько цифр, если число b больше base} while r > 0 do begin inc(a[0]); a[a[0]] := r mod base; r := r div base; end; end;

17 Деление длинного числа на короткое

Деление длинного числа на короткое

Деление длинного числа на короткое. В школе мы изучали деление столбиком. Будем рассматривать деление на короткое число b. При делении столбиком сначала выписывается старшая цифра, эту цифру делят на b. Частное дописывают к результату, а остаток пишут ниже. После этого к остатку приписывают следующую цифру, полученное значение делят на b. Аналогично, частное дописывают к ответу, а остаток пишут ниже. Процесс продолжается пока все цифры не будут использованы. 4531 | 7 42 ------ ---- | 647 33 28 ---- 51 49 --- 2 Остаток, к которому уже нельзя приписать цифру, будет остатком от деления.

18 Function divide

Function divide

Деление длинного числа на короткое. function divide(var a : thuge; b : integer) : integer; {функция делит число a на короткое число b и возвращает остаток от деления} var i, r : integer; {r - обозначает текущий остаток, к которому будет приписана очередная цифра} begin r := 0; {изначально остаток 0} for i := a[0] downto 1 do {цикл от старших цифр к младшим} begin r := r * base + a[i]; {приписывание очередной цифры} a[i] := r div b; {запись частного в результат} r := r mod b; {пересчет остатка} end; {Частное может содержать меньше цифр, поэтому нужно при необходимости уменьшить количество цифр} while (a[0] > 1) and (a[a[0]] = 0) do begin dec(a[0]); end; divide := r; end;

19 Умножение двух длинных чисел

Умножение двух длинных чисел

Умножение двух длинных чисел. При умножении двух длинных чисел в столбик, первое число последовательно умножается на каждую цифру. Результат умножения на i-тую цифру прибавляется к общему результату со сдвигом на i – 1.

20 Procedure multiplyHuge

Procedure multiplyHuge

Умножение двух длинных чисел. procedure multiplyHuge(var a, b : thuge); {функция умножает число a на число b} var c : thuge; {c - результат умножения. В данном случае нельзя записывать результат в тот же массив.} i, j, r : integer; begin fillchar(c, sizeof(c), 0); {заполнение массива 0} for i:= 1 to a[0] do begin r := 0; j:= 1; while (j <= b[0]) or (r > 0) do {пока есть перенос или в b есть еще цифры} begin inc(c[i + j - 1], a[i] * b[j] + r); {при умножении на предыдущие цифры в c уже записано некоторое значение, поэтому нужно прибавлять, а не присваивать} r := c[i + j - 1] div base; dec(c[i + j - 1], r * base); inc(j); end; end; c[0] := a[0] + b[0]; {максимально возможное количество цифр в ответе} move(c, a, sizeof(c)); {переместим ответ в массив a} {но цифр может оказаться меньше} while (a[0] > 1) and (a[a[0]] = 0) do begin dec(a[0]); end; end;

«Длинная арифметика»
Сайт

5informatika.net

115 тем
5informatika.net > Программирование > Длинная арифметика.ppt