Данный листочек посвящен проблеме представления в памяти компьютера длинных целых чисел и операциям над ними.
Длинные числа удобно хранить в виде последовательностей цифр в системе счисления с основанием 10 или 10000. С основанием 10 удобнее работать, в то время как основание 10000 позволяет экономнее расходовать память и в несколько раз быстрее выполнять операции.
Для хранения длинного целого числа создадим соответствующую структуру:
struct Longint { int sign; // Знак числа, например, 1, 0, -1 int size; // Количество цифр в числе short * digits; // Массив с цифрами int allocated; // Размер памяти, выделенной под хранение цифр };
Удобно, когда цифры хранятся в обратном порядке: digits[0]
– самая
младшая (правая) цифра, digits[size-1]
– самая старшая цифра.
В поле allocated
будем хранить размер массива digits
,
то есть максимально возможное количество цифр в числе. При этом всегда должно быть
выполнено условие allocated>=size
. Если же возникает необходимость
увеличить величину массива, то необходимо вызвать специальный метод, который будет увеличивать
размер массива digits
.
Первоначальная память для массива digits
выделяется в специальном методе, называемом
конструктором, который автоматически вызывается при создании объекта. Имя метода-конструктора
совпадает с именем структуры. Конструктор не возвращает никакого значения (даже void
)!
Пример конструктора, который создает длинное число и присваивает ему значение 1
:
Longint() { allocated=10; // По умолчанию выделяем память на 10 разрядов sign=1; digits=new short[allocated]; size=1; digits[0]=1; }
В свою очередь выделенная память в конструкторе должна быть освобождена в деструкторе: методе, который вызывается при удалении объекта. Имя деструктора начинается со знака тильды, за которым идет имя класса. Деструктор не принимает параметров и не возвращает значение:
~Longint() { delete digits; }
Разработайте самостоятельно структуру для работы с длинными целыми числами. Используйте основание системы счисления 10000 для внутреннего представления. Реализуйте операции ввода-вывода:
istream & operator >> (istream &, Longint &); ostream & operator << (ostream &, const Longint &);
Реализуйте копи-конструктор
Longint(const Longint &);
Реализуйте конструктор построения длинного числа из короткого:
Longint(int);
Реализуйте оператор присваивания:
Longint & operator=(const Longint &);
Реализуйте арифметические операторы сложения и вычитания:
Longint operator+ (const Longint &, const Longint &); Longint& operator+= ( Longint &, const Longint &); Longint operator- (const Longint &, const Longint &); Longint& operator-= ( Longint &, const Longint &);
Реализуйте операторы сравнения, умножения, деления и т.д.
Во всех задачах этого листка подразумевается, что все входные числа являются неотрицательными целыми не превосходящими 10100, если особо не оговорено иное.
Входные данные хранятся в файле input.txt
, выходные данные в файле output.txt
.
<
, если первое число
меньше второго, знак >
, если первое больше второго или
знак =
, если числа совпадают.