Содержательная постановка задачи
Многозначное число a представляется в виде последовательности (массива) целых чисел a1, a2, …, an путем разбиения его цифр на группы по t цифр. Каждая группа цифр, обозначенная ai, является целым числом, не превосходящим по величине некоторого фиксированного целого числа m. Например, число 3 1415 9265 3509 7932 3846 при t = 4 и m = 32767 может быть представлено в виде массива:
0003
1415
9265
3509
7932
3846
Реализовать следующие операции над многозначными числами:
Целые числа. Операции: сравнение, -, /, %.
Анализ и пример решения задачи
Для наглядности изобразим представление двух длинных чисел.
5 | 4 | 3 | 2 | 1 | 0 - номера разрядов
-------------------------------------------
' 3 ' 1415 ' 9265 ' 3509 ' 7932 ' 3846 ' - число A
' 4389 ' 9209 ' 0049 ' 2033 ' - число B
Также следует помнить о том, что числа могут быть как положительными, так и отрицательными. Приведенное выше представление будем называть модулем длинного числа. В данном случае мы видим шести- и четырехразрядное число. Такое представление позволяет также определить базу системы счисления. Она равна 10000, т.к. максимальная цифра, которую может содержать разряд длинного числа, равна 9999.
Сравнение: очевидно, что для того, чтобы сравнить два числа нужно сначала сравнить их знаки. Затем, если потребуется, количество разрядов чисел. И затем, если опять же потребуется, сравнивать числа в разрядах, начиная со старших.
Вычитание: вначале нужно посмотреть на знаки чисел, возможно потребуется не вычитать, а складывать. Пример: 4 - (-3) = 4 + 3 = 7. Из этого следует, что необходимо также реализовать операцию сложения. Вряд ли стоит пояснять как происходит сложение и вычитание "в столбик", лучше привести пример:
_' 2 ' 0001 ' 0000 ' 0123 '
' ' ' ' 4567 '
* // заем из старшего ненулевого разряда
_' 2 ' 0000 ' 9999 '10123 '
' ' ' ' 4567 '
' 2 ' 0000 ' 9999 ' 5556 '
Деление: имеется в виду целочисленное деление. Здесь тоже лучше привести пример:
_' 302 ' 5643 ' 2000 ' 3234 ' 1126 ' 9347 | 1234 ' 3452 ' 9943
' 302 ' 5380 ' 3289 ' 0293 | 2451 ' 2129 ' 6401
_' 262 ' 8711 ' 2941 ' 1126 ' 9347
' 262 ' 7921 ' 1424 ' 8647
_' 790 ' 1516 ' 2479 ' 9347
' 790 ' 1044 ' 2616 ' 5143
' 471 ' 9863 ' 4204
Остаток от деления: в предыдущем примере остаток от деления выделен курсивом.
Формальная постановка задачи
Исходные данные: два длинных числа записанные в "нормальном" виде. Могут предваряться знаком "минус". Примеры:
12345678990000000000000000000000000000000000003
-987654321
0
Ограничения на исходные данные: число должно состоять только из цифр от 0 до 9. Если старший разряд числа меньше 1000, ведущие нули не требуются. Вот примеры неверных исходных данных:
0000000000000000345
-000000
90234234-234234
9234vhidufh-349
--123
Результирующие данные: длинное число, записанное в "нормальном" виде.
Спецификация программы
Для хранения и работы с длинными числами создадим класс LongNumber. Данные о числе будем хранить в трех полях класса: знак числа, количество разрядов числа, указатель на целочисленный массив.
class LongNumber
{
...
private:
// Знак числа, может быть 1 или -1
char sign_;
// Текущее количество разрядов числа
int length_;
// Указатель на массив
int* array_;
...
}
Далее следует описать конструкторы, с помощью которых создаются объекты LongNumber.
// Конструктор по умолчанию
LongNumber::LongNumber()
{
array_ = new int[1];
array_[0] = 0;
length_ = 1;
sign_ = 1;
}
// Конструктор, основанный на строке
LongNumber::LongNumber(const char* string)
{
// Инициализируем знак числа
sign_ = 1;
// Индекс, с которого начнется распознавание числа.
int startIndex = 0;
// Смотрим есть ли знак "-" перед числом. Если есть, меняем знак числа
// и начинаем распознавание с индекса 1.
if (string[0] == '-') {
sign_ = -1;
startIndex = 1;
}
// Посчитаем сколько памяти нужно выделить под число
// Сначала берем полную длину строки, представляющей число
float tempLength = stringLength(string);
// Если числу предшествовал знак минус, отнимаем от длины единицу
tempLength -= (sign_ < 0) ? 1 : 0;
// Количество символов в старшем разряде
int charsInHighOrderDigit;
int supposedCharsInHighOrderDigit = int(tempLength) % NUMERALS_IN_DIGIT;
// Далее делим количество байт строки на максимальное количество
// цифр в разряде числа
tempLength /= float(NUMERALS_IN_DIGIT);
// Теперь сохраняем в length_ целую часть tempLength
length_ = int(tempLength);
// И если у tempLength была еще и дробная часть, это означает,
// что необходимо выделить еще один разряд.
if (tempLength - int(tempLength)) {
length_ += 1;
charsInHighOrderDigit = supposedCharsInHighOrderDigit;
}
else {
charsInHighOrderDigit = NUMERALS_IN_DIGIT;
}
// Выделяем необходимую память
array_ = new int[length_];
// Длина строки, представляющей число
int len = stringLength(string);
// Начинаем заполнять массив с начала
for (int i = 0; i < length_; i++) {
array_[i] = stringToNumber(string + (len - 1) -
(i * NUMERALS_IN_DIGIT),
((i == length_ - 1) ? charsInHighOrderDigit : NUMERALS_IN_DIGIT));
}
// Проверка на минус ноль. Не должно быть минус нуля.
if (length_ == 1 && array_[0] == 0)
sign_ = 1;
}
// Максимальное количество цифр в разряде числа
const int LongNumber::NUMERALS_IN_DIGIT = 4;
// Основание системы счисления
const int LongNumber::BASE = 10000;
// Функция-аналог strlen() из <cstring>
int
LongNumber::stringLength(const char* string)
{
int i = 0;
for (; string[i]; i++)
;
return i;
}
// Функция преобразует десятичную запись числа в целочисленное представление
int
LongNumber::stringToNumber(const char* string, unsigned int length)
{
int result = 0;
char zeroChar = '0';
for (int i = length - 1; i >= 0; i--) {
result += int(*(string - i) - zeroChar) * power(10, i);
}
return result;
}
// Функция-аналог pow() из <cmath>, возводит число в степень.
int
LongNumber::power(int base, int power)
{
int result = 1;
for (int i = 0; i < power; i++)
result *= base;
return result;
}
// Конструктор, основанный на числе типа int
LongNumber::LongNumber(int number)
{
// Определяем знак числа и сохраняем его в поле sign_
sign_ = ( (number >= 0) ? 1 : -1 );
// Делаем исходное число положительным, чтобы сохранить
// его модуль.
number *= ((number < 0) ? -1 : 1 );
// Определяем требуемую длину массива.
int len = 0, lenNum = number;
while (lenNum > 0) {
lenNum /= BASE;
len++;
}
// Сохраняем длину массива в поле length_
length_ = len;
// Создаем массив нужной длины. Если в конструктор был
// передан ноль, создаем создаем массив состоящий из одного элемента.
array_ = new int[((length_ == 0) ? 1 : length_)];
// Записываем разряды числа.
for (int i = 0; i < length_; i++) {
array_[i] = number % BASE;
number /= BASE;
}
// Проверка на минус ноль. Не должно быть минус нуля.
if (length_ == 1 && array_[0] == 0)
sign_ = 1;
}
Также существует конструктор, основанный на другом длинном числе, однако, представить его код не сложно, поэтому не будем его здесь приводить.
Приведем также деструктор:
LongNumber::~LongNumber()
{
// Освобождаем выделенную память
delete [] array_;
}
Сравнение: реализуется пятью операторами:
bool operator> (const LongNumber& number);
bool operator>= (const LongNumber& number);
bool operator< (const LongNumber& number);
bool operator<= (const LongNumber& number);
bool operator== (const LongNumber& number);
По сути, можно описать принцип работы одного из них.
bool
LongNumber::operator>= (const LongNumber& number)
{
if (compare(*this, number) <= 0) return true;
else return false;
}
// Функция сравнивает два длинных числа:
// Если первое больше второго, возвращает -1
// Если второе больше первого, возвращает 1
// Если числа равны, возвращает 0
int
LongNumber::compare (const LongNumber& a, const LongNumber& b)
{
if (a.sign_ > b.sign_) return -1;
else if (a.sign_ < b.sign_) return 1;
else {
int compareResult = compareModules(a, b);
if (compareResult < 0) {
if (a.sign_ > 0) return -1;
else return 1;
}
else if (compareResult > 0) {
if (a.sign_ > 0) return 1;
else return -1;
}
else return 0;
}
}
// Функция сравнивает модули чисел.
// Возвращаемые значения аналогичны значениям
// функции compare().
int
LongNumber::compareModules (const LongNumber& a, const LongNumber& b)
{
if (a.length_ > b.length_) return -1;
else if (a.length_ < b.length_) return 1;
else {
for (int i = a.length_ - 1; i >= 0; i--) {
if (a.array_[i] > b.array_[i]) return -1;
else if (a.array_[i] < b.array_[i]) return 1;
}
}
return 0;
}
Вычитание: первым делом нужно посмотреть на знаки чисел, существует четыре возможных варианта:
1) 5 - 3 = 2
2) -5 - 3 = -(5 + 3) = -8
3) 5 - (-3) = 5 + 3 = 8
4) -5 - (-3) = -(5 - 3) = -2
Вначале опишем операцию вычитания. Необходимым условием является то, что уменьшаемое должно быть по модулю больше вычитаемого. Это реализуется в приватной функции класса:
LongNumber
LongNumber::difference (const LongNumber& a, const LongNumber& b)
{
LongNumber result;
// Флаг переноса
bool overFlag = false;
int compareNumbers = compareModules(a, b);
// Указатели на большее и меньшее из чисел.
const LongNumber* biggerNumber;
const LongNumber* lesserNumber;
if (compareNumbers < 0) {
biggerNumber = &a;
lesserNumber = &b;
}
else {
biggerNumber = &b;
lesserNumber = &a;
}
// Длина результирующего массива окажется равной или меньшей на
// единицу длины большего из начальных массивов.
result.setLength(maximum(a.length_, b.length_));
// Теперь берем меньшую из двух длин массивов.
int minLength = minimum(a.length_, b.length_);
// И складываем разряды чисел начиная с младших
for (int i = 0; i < minLength; i++)
{
// Считаем пока просто разность разрядов.
// Если на предыдущем шаге был установлен флаг переполнения
// overFlag, отнимаем от разницы.
int digitDiff;
if (overFlag) {
if (biggerNumber->array_[i] == 0) {
digitDiff = BASE - 1 - lesserNumber->array_[i];
}
else {
digitDiff = biggerNumber->array_[i] - lesserNumber->array_[i] - 1;
overFlag = false;
}
}
else {
digitDiff = biggerNumber->array_[i] - lesserNumber->array_[i];
}
// Если разница оказалась отрицательной, запишем в разряд
// BASE + bigger.digit - lesser.digit
// и установим флаг переноса. Иначе, если разница
// положительна, записываем ее прямиком в разряд и
// сбрасываем флаг переноса.
if (digitDiff < 0) {
overFlag = true;
result.setDigit(i, biggerNumber->array_[i] - lesserNumber->array_[i] + BASE);
}
else {
result.setDigit(i, digitDiff);
}
}
// Если длина большего числа на самом деле была больше, чем у меньшего
// (они ведь могли быть и равны), дописываем в результирующее число
// старшие разряды большего числа. Только не забываем про флаг
// переполнения, который мог остаться в положении true с предыдущего
// этапа вычисления разности.
if (biggerNumber->length_ > minLength) {
// Берем теперь уже длину большего числа, она же равна длине
// результирующего.
int biggerLength = biggerNumber->length_;
for (int i = minLength; i < biggerLength; i++) {
// Будем записывать результирующие разряды через временную
// переменную, т.к. это даст возможность отнимать от разряда
// единицу в случае переполнения младших разрядов.
// Если результат вычитания отрицательный (а значит в разряде
// был 0), записываем в результирующий разряд BASE - 1.
int digit = biggerNumber->array_[i] - ((overFlag) ? 1 : 0);
if (digit >= 0) {
overFlag = false;
result.setDigit(i, digit);
}
else {
overFlag = true;
result.setDigit(i, BASE - 1);
}
}
}
// И под конец проверяем, если в старшем разряде результирующего числа
// оказался ноль, удаляем этот разряд.
if (result.array_[result.length_ - 1] == 0 && result.length_ > 1) {
LongNumber resultNoFirstDigit;
resultNoFirstDigit.setLength(result.length_ - 1);
for (int i = 0; i < resultNoFirstDigit.length_; i++)
resultNoFirstDigit.setDigit(i, result.getDigit(i));
return resultNoFirstDigit;
}
else {
return result;
}
}
Сложение: сложение двух длинных чисел реализовано через оператор, который, также как и в случае с вычитанием, различает четыре комбинации знаков чисел. Здесь же приведем приватную функцию, реализующую сложение модулей чисел.