Автор: Пользователь скрыл имя, 11 Февраля 2013 в 20:14, лекция
В основном мы будем рассматривать работу с целыми числами. Для хранения длинного числа можно использовать целочисленный массив, где в качестве элемента массива будет одна цифра числа. В 1м элементе массива будем хранить последнюю цифру числа, во 2м - предпоследнюю и т.д. до последней цифры. В 0м элементе можно хранить общее количество цифр в числе.
Длинная арифметика - раздел олимпиадного программирования, в котором рассматривается реализация действий с большими числами, не умещающихся в стандартных типах данных. На сегодняшний день единственным языком, используемым для решения олимпиадных задач и поддерживающим длинную арифметику, является Java, где все необходимые функции для работы с длинными числами встроены и можно обойтись без трудоемких реализаций.
В основном мы будем рассматривать работу с целыми числами. Для хранения длинного числа можно использовать целочисленный массив, где в качестве элемента массива будет одна цифра числа. В 1м элементе массива будем хранить последнюю цифру числа, во 2м - предпоследнюю и т.д. до последней цифры. В 0м элементе можно хранить общее количество цифр в числе. В простейшем случае, для хранения числа 154 достаточно будет использовать следующую запись:
const maxsize=100;
int a[maxsize];
a[0]=3; a[1]=4; a[2]=5; a[3]=1;
Элементом массива может быть не одна цифра, возможно использовать один элемент для хранения 4х цифр, т.к. мы понимаем, что на современных ЭВМ все операции как минимум 32-разрядные, поэтому время на сложение двух цифр такое же как и на сложение чисел, состоящих из 4х цифр. Поэтому часто используют порядок системы счисления base=10000 и фактически длинные числа хранятся как бы в 10000-й системе счисления, это позволяет увеличить скорость выполнения операций над ними в 3-4 раза.
Идея реализации всех необходимых операций (сложение, вычитание, умножение, деление и т.д.) основана на тех принципах, которыми мы пользуемся при расчетах на бумаге. Даже когда мы реализуем деление "в столбик", фактически мы работаем с небольшими числами, сводя более сложную задачу к набору из более простых подзадач.
Задачи, которые рассматриваются в данном разделе представляют собой базовый набор, достаточный для формирования первоначальных навыков овладения принципами длинной арифметики. Практически все задачи на длинную арифметику требуют чтения из файла и запись в файл длинных чисел, поэтому приведем реализацию этих функций в данном разделе, а в разборе задач будем их использовать: