Длинная арифметика: сложение
Итак, сегодня мы напишем длинное сложение. Так что же это такое и для чего это нужно?
Довольно часто нужно работать с очень большими числами (до 10000 знаков). Ни один стандртный тип Delphi не может "вместить" в себя такое огромное число, что уж говорить про Turbo Pascal. В таких случаях на помощь приходит длинная арифметика.
Если Delphi не может сложить два больших числа, то это ещё не значит, что это не может сделать человек. Например, нужно посчитать сумму: 9223372036854775817 + 14685537510068352681. Эти числа не помещаются ни в int64, ни в extended. Точнее, extended может хранить только 19-20 значащих знаков, всё остальное округляется - потеря точности. Тем не менее, мы можем взять бумажку и сложить эти два числа в столбик:
| + |
9223372036854775817 14685537510068352681 |
|
23908909546923128498 |
Ничего сложного! А почему бы не научить компьютер делать то же самое? Научим!
Первый вопрос, который приходит в голову: "А где же хранить такие огромные числа?" А хранить их можно либо в массиве, либо в строке. И там и там есть свои плюсы и минусы: строки удобно использовать, т.к. все элементы ввода возвращают строки (Edit1.Text, Memo1.Lines[0] и т.д.), но скорость работы со строками очень мала и длина типа string ограничена - 255 символов; в массивах не очень удобно учитывать длину числа, нужно постоянно при получении строки конвертировать в массив, но с массивом можно работать намного быстрее и длина массива может быть больше. Вариант с массивом всё-таки предпочтительнее: длинная арифметика нужна там, где числа действительно большие, чем больше числа, тем дольше считать результат. Да и писать код работы с массивом намного проще.
Теперь перейдём непосредственно к алгоритму. Как мы считаем столбик: начинаем с конца и складываем по одному знаку. Если получившаяся сумма меньше 10 - то записываем её в соответствующую клетку ответа. Если же сумма больше либо равна 10, то разряд единиц пишем в соответствующую клетку ответа, а разряд десятков (заметьте, он может быть равен только 1) прибавляем к следующему ответу (т.е. переносим эту единицу левее). Также может получиться такая ситуация, когда при сложении двух чисел длиной n мы получаем число длиной n+1 (например 80+41=121). При сложении на бумажке мы этого не замечаем, однако этот аспект есть.
Ну вот мы и рассмотрели всем с детства знакомый алгоритм 
. Хранить числа в массивах прям так, как мы их видим на бумажке не очень удобно - длина чисел может быть разной, проще всего просто напросто развернуть наши числа и делать всё наоборот: начинать с первого символа и при получении результата больше 10 переносить 1 вправо :
|
7185774586302733229 18625386001573558641 |
+ |
|
89482132964590980932 |
Заметьте, если перевернуть наш ответ, то он будет равен ответу из 1 примера. Хоть и этот метод и кажется немного сложнее, но запрограммировать его намного проще...
Теперь обратимся непосредственно к реализации: \code}
a и b - массивы, которые мы будем складывать, а na и nb - их длины. с - результирующий массив, nc - его длина. Нулевой элемент в массивах предназначен для хранения знака числа. Пускай там стоит 0, если число положительное, и 1 - если число отрицательное. Теперь нам нужно научить нашу программу считывать такие массивы с экрана и разворачивать их:
\code}
Ну вот и всё. Теперь можно приступать к написанию самой процедуры сложения.
Правильнее всего для хранения единички, переходящей в следующий разряд, завести отдельную переменную - смещение. Так мы и сделаем:
\code}
Ну вот мы и рассмотрели целочисленное длинное сложение. Пока наше сложение умеет работать только с положительными числами, однако позже (после изучения длинного вычитания) мы модифицируем его. Процедуру чтения мы сразу сделали полнофункциональной - для целочисленной арифметики большего не нужно и изменять мы её не будем.
Надеюсь, эта статья хоть каплю помогла Вам разобраться в огромном океане алгоритмов...