Курсовая работа: Реализация класса больших чисел
Пожалуй, самой сложной для реализации, является операция деления и нахождение остатка от деления двух больших чисел. Методы соответствующие данным операциям были названы delenie (BigInteger, BigInteger) и ostasok_delenie (BigInteger, BigInteger) соответсвенно. В основе лежит принцип деления «столбиком». Пример работы алгоритма приведен на рисунке 8.
Рис. 8. Операция деления и нахождение остатка от деления
Ход алгоритма следующий: сравниваем делитель с делимым, прибавляя поразрядно по одной цифре к делителю в случае, если получившийся делитель меньше делимого, при этом в частное записываем 0. На рисунке 8 видно этот этап: 2<7985, в частное записываем 0, затем 21<7985, в частное записываем 0, и так далее пока не поменяется знак неравенства 21367>7985. После этого запускается цикл по нахождению следующей цифры частного. На каждом шаге делитель прибавляется на величину равную самому делителю, пока он не станет больше либо равен нашему промежуточному делимому, т.е. 21367. Шаг цикла, на котором выполнится данное условие, и будет искомой цифрой для частного. Затем вычитаем из промежуточного делимого полученное в ходе цикла число и получаем промежуточный остаток. Так как он точно меньше делителя (в связи с предыдущими условиями), добавляем к нему следующую не задействованную цифру делимого и переходим к первому шагу алгоритма. Алгоритм считается выполненным, если получается остаток, меньший делителя и не осталось ни одной незадействованной цифры делимого. В зависимости от задачи, метод возвращает либо частное, либо остаток от деления.
Для удобства пользователей был введен еще один метод vishislenie(), который предоставляет возможность выполнять вышеперечисленные арифметические операции с двумя или одним большим числом путем простого ввода необходимого для вычисления выражения. Пример работы данного метода приведен на рисунке 9.
факториал большой число перемножение
Рис. 9. Режим вычисления выражений
Выводы
Таким образом, в ходе написания программы,
поставленные задачи были полностью выполнены: сделаны механизмы чтения и печати
в консоль больших чисел, реализованы арифметические операции.
Производительность программы, на мой взгляд, достаточно высокая, что было
достигнуто за счет некоторой оптимизации кода (в основном в результате
переработки операции произведения). Небольшое замедление программы возможно
вследствии того, что использован контейнер стандартной библиотеки шаблонов.
Этот недостаток компенсируется простотой использования стандартного контейнера
и множеством поставляемых с ним методов отладки, проверкой ошибок на этапе
компиляции программы и механизмом исключений. Немаловажным является реализация
метода предоставляющего пользователям в удобной форме производить вычисления с
большими целыми числами.
Список используемой литературы
Список используемой литературы
1. Лаптев В.В., Морозов А.В. «Объектно-ориентированное программирование. Задачи и упражнения». Издательство: «Питер» 2007 г.
2. Лафоре Р. «Объектно-ориентированное программирование в С++». Издательство: «Питер», 2004 г.
Приложение
Листинг 1. Файл BigInteger.h класс BigInteger.
#include <iostream>
#include <deque> // очередь (из библиотеки STL)
#include <string>
using namespace std;
// Класс больших целых чисел
class BigInteger {
deque<int> vect; // «содержит» число
char znak; // знак числа
public: BigInteger()
{
vect = deque<int>();
znak = ' ';
}
// ___________________ Сравнение модулей больших чисел____________
int sravnenie (BigInteger big1, BigInteger big2)
{
if (big1.vect.size() > big2.vect.size()) return 1; // 1, если первое число > второго
if (big1.vect.size() < big2.vect.size()) return -1; // -1, если первое число < второго
if (big1.vect.size() == big2.vect.size())
{
for (int i = 0; i < (int) big1.vect.size(); i++)
{
if (big1.vect.at(i) > big2.vect.at(i)) return 1;
if (big1.vect.at(i) < big2.vect.at(i)) return -1;
}
return 0; // 0, если числа равны
}
}
// ___________________ Чтение числа из консоли ___________________
BigInteger chtenie()
{
BigInteger big;
string temp = «0123456789»; // вспомогательная строка
string minus = «–»;
string str;
cin >> str;
if (str.at(0) == minus.at(0)) big.znak = '-'; // определение знака числа
for (int i = 0; i < (int) str.length(); i++) // цикл считывающий цифры из строки
for (int j = 0; j < 10; j++)
if (str.at(i) == temp.at(j)) big.vect.push_back(j);
return dell_null(big);
}
// ___________________ Функция удаления нулей из начала числа ____
BigInteger dell_null (BigInteger big)
{
while (big.vect.size() > 1)
{
if (big.vect.at(0)!= 0) break;
else {big.vect.pop_front();}
}
return big;
}
// ___________________ Печать числа в консоль ____________________
void vector_print (BigInteger big)
{
big = dell_null(big); // убираем нули из начала числа
if (big.vect.size() == 1 && big.vect.at(0) == 0) big.znak = ' '; // если число равно 0, то не ставим знак
if (big.znak == '-') // если число отрицательное, сначала печатаем знак –
cout << big.znak;
for (int i = 0; i < (int) big.vect.size(); i++)
cout << big.vect.at(i);
}
// ___________________ Сумма больших чисел _______________________
BigInteger summa (BigInteger big1, BigInteger big2)
{
if (big1.znak!= big2.znak) // если разные знаки, то отправляем на метод разность
{
if (big1.znak == '-') // заменяем – x+y на y-x
{
big1.znak = ' ';
return rasnost (big2, big1);
}
else // заменяем x+-y на x-y
{
big2.znak = ' ';
return rasnost (big1, big2);
}
}
deque<int> summa = deque<int>(); // сюда записывается результат
int temp = 0; // 1 для добавления к старшему разряду
int metka = 0; // для вычисления позиции, с которой остаются разряды только одного числа
if (big1.vect.size() >= big2.vect.size()) // ставим большее число на первое место
{
for (int i = big1.vect.size() – 1, j = big2.vect.size() – 1; j >=0; i–, j–) // начиная с первых разрядов складываем числа
{
summa.push_front((big1.vect.at(i) + big2.vect.at(j) + temp)%10);
if ((big1.vect.at(i) + big2.vect.at(j) + temp) >= 10) temp = 1; else temp = 0; // прибавляем 1 на следующем шаге, если сумма больше 10
metka = i;
}
for (int i = metka-1; i >= 0; i–) // начиная с позиции метки добиваем цифрами из большего числа, учитывая возможное прибавление 1
{
summa.push_front((big1.vect.at(i)+temp)%10);
if ((big1.vect.at(i) + temp) == 10) temp = 1; else temp = 0;
}
if (temp == 1) summa.push_front(1); // срабатывает в случае когда увеличивается разряд, например 99+1=100
}
else
{
for (int i = big2.vect.size() – 1, j = big1.vect.size() – 1; j >=0; i–, j–)
{
summa.push_front((big2.vect.at(i) + big1.vect.at(j) + temp)%10);
if ((big2.vect.at(i) + big1.vect.at(j) + temp) >= 10) temp = 1; else temp = 0;
metka = i;
}
for (int i = metka-1; i >= 0; i–)
{
summa.push_front((big2.vect.at(i)+temp)%10);
if ((big2.vect.at(i) + temp) == 10) temp = 1; else temp = 0;
}
if (temp == 1) summa.push_front(1);
}
big1.vect = summa;
return big1;
}
// ________________________ Разность больших чисел ________________
BigInteger rasnost (BigInteger big1, BigInteger big2)
{
if (big2.znak == '-') big2.znak = ' '; // x–y преобразуем в x+y и передаем в метод суммы
else big2.znak = '-';
if (big1.znak == big2.znak) return summa (big1, big2); // – x-y преобразуем в – (x+y) передаем методу суммы
deque<int> rasn = deque<int>(); // сюда записывается разность
int temp = 0; // 1 для вычитания из старшего разряда
int metka = 0; // для вычисления позиции, с которой остаются разряды только одного числа
big1 = dell_null(big1); // предварительно удаляем незначащие нули из начала числа
big2 = dell_null(big2);
if (sravnenie (big1, big2)!= -1) // ставим большее число сверху в столбике
{
for (int i = big1.vect.size() – 1, j = big2.vect.size() – 1; j >=0; i–, j–)
{
if ((big1.vect.at(i) – big2.vect.at(j) + temp) >= 0) // поразрядно вычитаем
{
rasn.push_front (big1.vect.at(i) – big2.vect.at(j) + temp);
temp = 0;
}
else
{
rasn.push_front (big1.vect.at(i) – big2.vect.at(j) + 10 + temp); // заимствуем 1 из старшего разряда
temp = -1;
}
metka = i;
}
for (int i = metka-1; i >= 0; i–) // добиваем числами оставшихся разрядов, учитывая -1
{
rasn.push_front (abs((big1.vect.at(i)+temp+10)%10));
if ((temp == -1) && (big1.vect.at(i) + temp) < 0) temp = -1; else temp = 0;
