Содержание
Задача
Вводятся два очень длинных целых числа. Найти их сумму.
Решение
- s1, s2, s3 — строковые представления первого, второго числа и их суммы;
- n1, n2, n3 — текущие разряды первого и второго чисел и перенос из предыдущего разряда;
- l1, l2 — длины введенных строк из чисел;
- c — строковое представление суммы текущих разрядов.
Алгоритм решения задачи:
Под "очень длинными целыми числами" здесь подразумеваются такие, которые не помещаются даже в тип данных longint.
Вводятся два числа, которые записываются в программу как строки. Измеряется длина строк. В случае, если первая строка длиннее второй, переменные обмениваются значениями. Это делается для избежания сложностей в дальнейшем.
В цикле символы строки s1 перебираются с конца до первого (счетчик i). Каждый символ преобразуется в целое число. Также с конца берутся символы s2 (счетчиком служит l2) и преобразуются в целое. Числа складываются. Сумма записывается в начало строки s3 без старшего разряда, который сохраняется в отдельной переменной n3 и добавляется к сумме при следующем сложении разрядов.
Когда строка s1 заканчивается, надо проверить есть ли перенос из младшего разряда. Если есть, то надо продолжать складывать, пока перенос не станет равным нулю.
После того, как складывать уже нечего, надо дописать впереди s3 оставшуюся часть s2.
Что ты хочешь узнать?
Ответ
var a := ‘123456789123456789’;//ReadString();
var b := ‘123456789123456789123’;//.
var l := Abs(a.Length — b.Length);
if a.Length > b.Length then
insert(source, b, 1)
insert(source, a, 1);
for var i:=a.Length downto 1 do
var c := a[i].ToDigit + b[i].ToDigit + mem;
Этот блог посвящен вопросам подготовки к олимпиадам по программированию и самой технологии программирования. Используемый язык программирования предпочитаю Паскаль. С некоторых пор стала подробнее изучать Си, так что теперь могу поделиться примерами и на Си. Не все мне известно, но то, что знаю — делюсь с Вами.
Страницы
Поиск по этому блогу
пятница, 16 марта 2012 г.
Длинная арифметика
Немного о переводе символа в число: известно, что в кодовой таблице числа как символы идут подряд от 0 до 9. Таким образом, зная только код числа 0 ord(‘0’) и код нужного числа ord(a[i]), можно вычислить саму цифру:
y:=ord(a[i])-ord(‘0’);
И наоборот, зная код цифры p и нуля, можно получить символ:
chr(p+ord(‘0’)).
Можно воспользоваться и стандартными функциями перевода:
val(a[i],y,code); — перевод символа в число,
str(p,cp); — перевод числа в строку символов.
Но при этом нужно вводить лишние переменные:
var code:integer; cp:string;
И кроме этого с процедурой нельзя работать внутри выражений, т.е. использовать ее как функцию. В Delphi и Lazarus такая проблема снята — там есть функции:
strtoint(a[i]) и inttostr(p).
По аналогии запишем алгоритм умножения больших чисел. Здесь выравнивать числа не обящательно, а результат вычислений лучше сразу хранить в массиве чисел.
program multiplay;
Загрузка...
