Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Сложение двух «длинных» чиселНапишем подпрограмму сложения двух «длинных» положительных чисел, представленных в виде массивов а и b типа TLong, описанного выше. Будем считать, что каждый элемент такого массива содержит всего одну десятичную цифру. Первый элемент массива содержит младшую цифру. Результат будем помещать в массив c того же типа. Сложение двух "длинных" чисел очень похоже на обычное школьное сложение столбиком. Числа складываются поразрядно. Сложение производится с помощью стандартного алгоритма сложения столбиком от младшего разряда к старшему с переносом единицы в старший разряд, если в результате сложения двух цифр и значения переноса из младшего разряда получается число, большее девяти. Алгоритм процедуры сложения объясним на простом примере. Пусть А = 870613029451, В = 3475912100517461. Тогда при использовании уже известного представления "длинных" чисел получаем: I A[i] B[i] C[1] C[2] C[3] C[4] 1 451 7461 6912 1 0 0 2 1302 51 6912 1354 0 0 3 8706 9121 6912 1354 7827 1 4 0 3475 6912 1354 7827 3476
Алгоритм имитирует привычное сложение столбиком, начиная с младших разрядов. И именно для простоты реализации арифметических операций над “длинными” числами используется машинное представление в обратном порядке. Результат: С = 3476782713546912. Тогда программа ввода двух “длинных” чисел и вывода результата их сложения будет иметь следующий вид:
Var A, B, C: Tlong; 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:=1 to k do begin C[i+1]:= (C[i]+A[i]+B[i]) Div Osn; C[i]:= (C[i]+A[i]+B[i]) Mod Osn; end; {производится сложение двух "длинных" чисел, причем целая часть от основания записывается в i+1 позицию, потому что в одном элементе массива хранится только четыре цифры} if C[k+1]=0 then C[0]:=k {проверяется результат, выходит ли} else C[0]:=k+1; {он за рамки разряда или нет} end; Begin Assign (Input, ‘Input.txt'); {связывание файловой переменной с именем физического файла, Input- имя файловой переменной, Input.txt- строковое выражение, определяющее имя физического файла} Reset (Input); {открыть для ввода данных} ReadLong (A); {обращение к процедурам ввода "длинных"} ReadLong (B); {чисел А и В } Close (Input); {закрыть файл} SumLongTwo (A,B,C); {обращение к процедуре сложения двух "длинных" чисел} Assign (Output, ‘Output. txt’); {связывание файловой переменной с именем физического файла; Output - имя файловой переменной, Output.txt- строковое выражение, определяющее имя физического файла} Rewrite (Output); {открыть для вывода на экран} WriteLong (C); {обращение к процедурам вывода результата} Close (Output); {закрыть файл} end.
После изложения материала, слушателям предлагаются следующие вопросы для закрепления материала: 1. Что произойдет, если сумма A[i]+B[i] окажется больше максимально допустимого значения типа Tlong? Как можно этого избежать? 2. Напишите алгоритм сложения двух "длинных" чисел?
4. Умножение «длинного» числа на «короткое» В подпрограмме для выполнения такого умножения будем использовать массив s, в качестве, как входного параметра, так и результата умножения. Массив имеет тип TLONG. В первом элементе этого массива расположены четыре младшие цифры «длинного» числа. Переменная L будет содержать значение текущей длины этого массива. «Короткое» число находится в целочисленной переменной п. Несмотря на то, что и число п и элементы массива s можно представить в целом типе с максимальным числом разрядов (longint в Turbo-Pascal и long в С), максимального значения этого типа они достигать не могут, так как результат умножения любого ненулевого элемента массива s на п также не должен превышать максимальное значение того нее типа. В приведенном ниже примере реализации подобной подпрограммы каждый элемент входного и выходного массива s должен быть меньше 10000, т.е. состоять не более чем из одной цифры 10000-ичной системы счисления (четырех десятичных цифр). Значение п нри этом может достигать 231:10000 = 200000. При уменьшении количества цифр у элементов s, значение п может быть увеличено, и наоборот. Умножение производится последовательно от младшего разряда к старшему в 10000-ичной системе счисления, каждая цифра которой записывается как число в десятичной системе, смешанной с ней. procedure Mult (var s: along; var L: longint; n: longint); {умножаем массив s длины L на число n} Var pr,i:longint; Begin pr:=0; {перенос в старший 10000-ичный разряд} for i:= 1 to L do begin s[i]:= s[i]*n; s[i]:= s[i]+pr; pr:= s[i] div 10000; s[i]:= s[i] mod 10000; end; while pr>0 do begin inc (L); s[L]:= pr mod 10000; pr:= pr div 10000 end End;
Заметим, что результат мы получили в 10000-ичной системе счисления и при его выводе следует дополнять каждый элемент результирующего массива до четырех десятичных цифр ведущими нулями. Пример такого вывода содержится, например, в решении задачи параграфа 7, использующей подпрограмму Mult.
Существует и другая возможность умножения “длинного” числа на “короткое”. Эта процедура очень похожа на процедуру сложения - точно так же моделируется вычислением в столбик, точно так же на каждом шаге определяется перенос в следующий разряд. Поэтому реализацию решения задачи можно вынести на самостоятельную работу учащимся. Под “коротким” числом понимается целое число типа LongInt. "Длинное" чило располагается в массиве А типа TLong. В первом элементе этого массива расположены четыре младшие цифры "длинного" числа. Процедура будем иметь следующий вид:
Procedure Mul (Const A:TLong; Const K:LongInt; Var C:TLong); Var i:Integer; {результат - значение переменной С} Begin FillChar (C, SizeOf (C), 0); {заполнение массива С нулями} If K=0 Then Inc (C[0]) {умножение на ноль} Else Begin For i:=1 To A[0] Do Begin {умножение длины массива А на чило K и "протаскивание" старшей цифры из C[i] в младшую цифру числа из C[i+1]} C[i+1]:= (LongInt (A[i]*K+C[i]) Div Osn; C[i]:= (LongInt (A[i]*K+C[i]) Div Osn; End; If C[A[0]+1] > 0 Then C[0]:=A[0]+1 Else C[0]:=A[0] {определяем длину результат} End; End;
5. Умножение «длинного» числа на «длинное» Для умножения двух «длинных» чисел существует несколько различных алгоритмов. Один из них заключается в умножении каждой цифры первого множителя на каждую цифру второго и размещении каждого из таких произведений в соответствующем разряде результата. Если в каком-то разряде результата оказывается число, большее, чем максимальная цифра соответствующей системы счисления (9 в десятичной системе), то производится перенос в старший разряд. Такой алгоритм соответствует умножению двух чисел столбиком. Приведем тексты программ, реализующих подобный алгоритм. Считывание «длинных» чисел производится из файла input.txt, а результат умножения помещается в файл output.txt. Входные данные в подобных задачах удобнее представлять в файле во избежание ошибки при вводе длинного числа с клавиатуры. Результат же по текстовому файлу проще анализировать. Подпрограмма ReadData является примером ввода из файла «длинного» числа в случае, когда заранее неизвестна его длина. Применение в языке Turbo-Pascal логической функции SeekEoln вместо Eoln позволяет игнорировать пробелы в конце строки при вводе «длинного» числа. В языке С такую ситуацию требуется отслеживать самостоятельно. После считывания числа из файла в первом элементе массива оказывается старшая цифра «длинного» числа. Результат же мы будем получать в массиве, первый элемент которого соответствует младшей цифре, а в нулевом элементе хранится текущая длина массива.
Туре Abyte = array [1..10000] of byte; Tdest = array [0..20000] of word; Var aLen, hLen: word; a, b: AByte; с: ТDest;
Procedure ReadData; var с:char; begin Assign(input,'input.txt'); Reset(input); aLen:=0; bLen:=0; while not SeekEoln do {пока не достигнут конец строки} begin read(с); inc(aLen); a [aLen]:=ord(c)-ord ('0') {перевод символа в цифру} end; readln; while not SeekEoln do begin read(c); inc(bLen); b[bLen]:= ord(c)-ord(' 0') {перевод символа в цифру} end; Close(input) end;
Procedure LongXLong; var i, j, p, q: word; begin p:=aLen+bLen; FillChar (c, 2*(p+1), 0); {заполнение массива С нулями} for i:= aLen downto 1 do for j:=bLen downto 1 do begin {q — место в результате для произведения q:= p-i-j+1; c[q]:= c[q]+a[i]+b[i]; if с[q]>9 then begin {перенос в следующий разряд} c[q+1]:= c[q+l]+c[q] div 10; c[q]:= c[q] mod 10 end end; {в с[0] поместим длину результата умножения} if с[p]<>0 then c[0]:= p else c[0]:= p-l end;
Procedure WriteResult; var i: word; begin Assign(Output,'Output.txt'); Rewrite(Output); for i:= c[0] downto i do write(c[i]); Close(Output) end;
{Основная программа} Begin ReadData; LongXLong; WriteResult End.
|