|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Занятие 10. Длинная арифметика.
В задачах, рассмотренных на предыдущих занятиях, для хранения чисел мы использовали стандартные типы данных, такие как integer и longint. С помощью этих типов данных можно хранить только относительно небольшие числа. Тем не менее компьютер предназначен для проведения громоздких вычислений. Что же делать, если в задаче необходимо оперировать, к примеру, 100-значными числами?
Во-первых, "большие" числа нужно как-то хранить в памяти компьютера. Вспомним, как мы записываем числа на бумаге. Мы ведь не пишем специальный символ для каждого числа, а представляем его в виде последовательности цифр. Этот способ можно использовать и в программе: запишем число в виде массива его цифр. Так как в результате арифметических операций "длина" числа может измениться, удобно записать цифры в обратном порядке. Например, чтобы представить число 1024, первому элементу массива присвоим 4, второму - 2, третьему - 0, четвертому - 1, а остальным - ноль. Таким образом, мы получили число с некоторым количеством незначащих лидируюущих нулей, записанное в перевернутом виде .
Операции сложения, умножения, вычитания и деления тоже производятся как на бумаге: "в столбик".
Приведем несколько идей, как ускорить работу арифметических операций с длинными числами:
- нам совершенно не обязательно каждый раз просматривать массив целиком, ведь с некоторого момента там будут идти одни нули. Чтобы учесть это, для каждого числа будем хранить его "длину". Тогда, например, при сложении двух n-значных чисел, длина результата не может быть больше (n+1).
- однозначные и трехзначные числа компьютер складывает (умножает, делит) с одинаковой скоростью. Поэтому имеет смысл хранить в одном элементе массива не по одной цифре, а по 3-4 подряд идущих (как бы представить число в 1000-ричной системе счисления). Это уменьшит время выполнения операций с длинными числами в 3-4 раза соответственно.
| Задача 10-1. A+B |
| Задача 10-2. A-B |
| Задача 10-3. A*B |
| Задача 10-4. A/B |