XVII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Создание C++ библиотеки для поддержки "длинной" арифметики
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Порой нам приходится работать с очень большими числами, но обычный калькулятор не может дать нам такую возможность. При работе с разными калькуляторами мы имеем ограничение по вводимому числу (количество цифр вводимого числа). На разных калькуляторах количество цифр в числе разное, но все калькуляторы, при превышении длины числа, представляют число в экспоненциальной форме (рис.1).
Экспоненциальная запись в информатике и вычислительной математике — представление действительных чисел в виде мантиссы и порядка. Она удобна для представления очень больших и очень малых чисел, а также для унификации их написания.
, где
N — записываемое число;
M — мантисса;
n — основание показательной функции;
p (целое) — порядок;
— характеристика числа.
Рис.1
Но порой такая запись числа неудобна для дальнейших работ с числом, так как простые калькуляторы сильно округляют конечный ответ. Для тех, кому просто нужно посчитать длинное число, в интернете есть «продвинутые калькуляторы», в которых можно проделать нужную нам арифметику с длинным числом, однако, результат работы и в этом калькуляторе представляется в экспоненциальном виде.
Так возникла идея создания библиотеки в языке программирования С++ позволяющая работать с длинной арифметикой.
Проанализировав существующие программные решения, были определены следующие функциональные требования к разрабатываемой программе:
соблюдение правильности вычислений;
программа не должна перегружать ресурсы компьютера;
программа должна иметь возможность сброса полученного результата;
пользователь должен иметь возможность видеть выполняемые им действия и полученный результат;
программа не должна занимать большой объем памяти.
Среда разработки:
Microsoft Visual Studio
Язык программирования:
С++
Задачи и цели:
Создать библиотеку для языка программирования с++, позволяющую пользователю работать с очень большими целыми числами без преобразования формы отображения, и приложения, которое предоставляет пользователю возможность производить арифметические действия с этими числами и получать результат в «естественном» виде.
Задачи:
Изучить теорию о длинной арифметике
Изучить объектно-ориентированное программирование
Изучить раздел перегрузки операторов
Разработать иерархию классов
Написать реализацию класса UnlimitedInt
Перегрузить необходимые операции
Написать приложение, которое позволяет производить арифметические действия с «длинными» числами и получать результат в «естественном» виде.
Процесс создания библиотеки UnlimitedInt
Важный вопрос, который пришлось решить при создании библиотеки, как будут храниться «длинные» числа. Было определено, что число будет реализовано в виде класса под названием UnlimitedInt, который будет содержать в себе сведения о длине числа, о знаке и о самом числе. Само число хранится как массив, состоящий из символов типа char, записанных в обратном порядке.
Сам процесс записи представляет собой систему «остаток от деления на 10 – деление на 10» (Приложение 1).
Также реализована часть кода, которая исключает попадание буквенных значений и прочих символов при попытке записи их в UnlimitedInt (Приложение 2).
Создание библиотеки
Вся система работы с «длинными» числами строится по принципу сложение/вычитание/умножение/деление столбиком.
Реализация алгоритма «Сложение» (+):
Проверяются знаки у чисел, если оба числа положительные, то к большему числу прибавляется меньшее. Если по длине числа равны, то они складываются путем поразрядного сложения (приложение 3). В случае, когда предполагается сложение чисел с разными знаками, то реализуется процедура «Вычитание».
Реализация алгоритма «Вычитание» (–):
Эта операция тоже реализуется через поразрядные операции. Если уменьшаемая цифра меньше вычитаемой, то «занимаем» в следующем разряде, соответственно, и цифра в этом разряде уменьшается на занятую единицу (Приложение 4).
Реализация алгоритма «Умножение» (*):
При реализации процедуры учитывается случай, когда число заканчивается последовательностью нулей, тогда реализуется алгоритм, который сохраняя эти нулевые значения, добавляет их к получаемому числу (Приложение 5).
Сам алгоритм умножения повторяет умножение «столбиком» (Приложение 6).
Реализация алгоритма «Деление» (/):
В данном алгоритме присутствует защита от деления на ноль.
Метод, с помощью которого ищем само число, называется бинарным поиском.
(Приложение 7).
Реализация других процедур:
В данной программе над «длинными» числами предусмотрено выполнение сравнения чисел (<, >, =), перевод в int (при возможности), перевод в string, извлечение модуля (abs), ввод и вывод числа.
Заключение
В результате выполнения данного проекта было разработано приложение выполняющее вычисления с «длинными» числами и предоставляющее результат в виде «длинного числа», для реализации этого приложения создана библиотека UnlimitedInt, которая позволяет осуществлять работу с такими числами в языке программирования С++. При помощи этой программы можно выполнять определенные арифметические операции над не стандартными числами. Программа не занимает много места, не требовательна к установленному программному обеспечению. Также было проведено исследование полученного программного продукта. В целом, поставленная в начале работы цель была достигнута. В программе выполняются все необходимые функциональные требования.
Литература
Кнут, Д.Э. Искусство программирования: учеб. пособие: в 3 т.: пер. с англ. Т.1: Основные алгоритмы. - 3-е изд. - М. и др.: Вильямс, 2000. - 720 с.
Гловацкая А.П. Методы и алгоритмы вычислительной математики: учеб. пособие для вузов / А.П. Головыцкая. - М.: Радио и связь, 1999. - 408с.
Бежанова, М.М. Практическое программирование: структуры данных и алгоритмы: учеб. для вузов / М.М. Бежанова, Л.А. Москвина, И.В. Поттосин. - М.: Логос, 2001. - 223с.
Приложения
Приложение 1
UnlimitedInt::UnlimitedInt(intsource)
{
isPositive = (source >= 0);
source = std::abs(source);
do
{
digits.push_back(source % 10);
source /= 10;
}while (source != 0);
compressDigits();
}
UnlimitedInt::UnlimitedInt(const std::string& source)
{
if (source.empty())
{
isPositive = true;
return;
}
if (!isDigit(source[0]) && source[0] != '-')
{
throw"Non-numeric character found!";
}
isPositive = (source[0] != '-');
auto it = source.begin();
if (!isPositive)
{
it++;
}
while (it !=source.end())
{
if (!isDigit(*it))
{
throw"Non-numeric character found!";
}
digits.push_back(toDigit(*it));
it++;
}
std::reverse(digits.begin(), digits.end());
compressDigits();
}
Приложение 2
UnlimitedIntUnlimitedInt::operator+(constUnlimitedInt& source) const
{
UnlimitedInt newInt;
if (isPositive == source.isPositive)
{
if (digits.size() > source.digits.size())
{
newInt.digits = calcSumm(digits, source.digits);
}
else
{
newInt.digits = calcSumm(source.digits, digits);
}
newInt.isPositive = isPositive;
}
else
{
if (abs() >source.abs() || abs() ==source.abs()) {
newInt.digits = calcDiff(digits, source.digits);
newInt.isPositive = isPositive;
}
else
{
newInt.digits = calcDiff(source.digits, digits);
newInt.isPositive = source.isPositive;
}
newInt.compressDigits();
}
return newInt;
}
UnlimitedIntUnlimitedInt::operator+(intsource) const
{
returnoperator+(UnlimitedInt(source));
}
UnlimitedIntUnlimitedInt::operator+(const std::string& source) const
{
returnoperator+(UnlimitedInt(source));
}
Приложение 3
std::vector<Digit> UnlimitedInt::calcSumm(const std::vector<Digit>& summand1, const std::vector<Digit>& summand2)
{
std::vector<Digit> res;
Digit over = 0;
size_t i;
for (i = 0; i < summand2.size(); i++)
{
Digit sum = summand1[i] + summand2[i] + over;
if (sum >= 10)
{
res.push_back(sum % 10);
over = 1;
}
else
{
res.push_back(sum);
over = 0;
}
}
for (; i < summand1.size(); i++)
{
Digit sum = summand1[i] + over;
if (sum >= 10)
{
res.push_back(sum % 10);
over = 1;
}
else
{
res.push_back(sum);
over = 0;
}
}
if (over == 1)
{
res.push_back(1);
}
return res;
}
Приложение 4
std::vector<Digit> UnlimitedInt::calcDiff(const std::vector<Digit>& reduced, const std::vector<Digit>& subtractible)
{
std::vector<Digit> res;
Digit deposit = 0;
size_t i;
for (i = 0; i < subtractible.size(); i++)
{
if (reduced[i] - deposit >= subtractible[i])
{
res.push_back(reduced[i] - deposit - subtractible[i]);
deposit = 0;
}
else
{
res.push_back(reduced[i] - deposit + 10 - subtractible[i]);
deposit = 1;
}
}
for (; i < reduced.size(); i++)
{
if (reduced[i] - deposit < 0)
{
res.push_back(reduced[i] - deposit + 10);
deposit = 1;
}
else
{
res.push_back(reduced[i] - deposit);
deposit = 0;
}
}
return res;
}
Приложение 5
UnlimitedIntUnlimitedInt::operator*(constUnlimitedInt& source) const
{
UnlimitedInt newInt;
newInt = 0;
std::vector<Digit> zeroes;
for (size_t i = 0; i < source.digits.size(); i++)
{
UnlimitedInt tmp;
tmp.digits = calcMult(digits, source.digits[i]);
tmp.digits.insert(tmp.digits.begin(), zeroes.begin(), zeroes.end());
newInt = newInt + tmp;
zeroes.push_back(0);
}
newInt.isPositive = isPositive == source.isPositive;
newInt.compressDigits();
return newInt;
}
UnlimitedIntUnlimitedInt::operator*(intsource) const
{
returnoperator*(UnlimitedInt(source));
}
UnlimitedIntUnlimitedInt::operator*(const std::string& source) const
{
returnoperator*(UnlimitedInt(source));
}
Приложение 6
std::vector<Digit> UnlimitedInt::calcMult(const std::vector<Digit>& digits, Digitmultiplier)
{
Digit over = 0;
std::vector<Digit> res;
for (size_t i = 0; i < digits.size(); i++)
{
Digit mult = digits[i] * multiplier + over;
if (mult >= 10)
{
res.push_back(mult % 10);
over = mult / 10;
}
else
{
res.push_back(mult);
over = 0;
}
}
if (over != 0)
{
res.push_back(over);
}
return res;
}
Приложение 7
UnlimitedIntUnlimitedInt::operator/(constUnlimitedInt& source) const
{
if (source== 0)
{
throw"Division by zero";
}
else
{
UnlimitedInt temp = source;
temp.isPositive = true;
UnlimitedInt result, current;
result.digits.resize(digits.size());
for (int i = digits.size() - 1; i >= 0; --i) {
current = current * 10;
current.digits[0] = digits[i];
current.compressDigits();
int x = 9;
while (true) {
UnlimitedInt mult = temp * x;
if (mult < current || mult == current) {
result.digits[i] = x;
current = current - mult;
break;
}
x--;
}
}
result.isPositive = isPositive == source.isPositive;
result.compressDigits();
return result;
}
}