Реализация класса больших чисел (стр. 2 из 3)

Для удобства пользователей был введен еще один метод 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;

}

big1.vect = rasn;

return big1;

}

else

{

for (int i = big2.vect.size() – 1, j = big1.vect.size() – 1; j >=0; i–, j–)

{

if ((big2.vect.at(i) – big1.vect.at(j) + temp) >= 0)

{

rasn.push_front (big2.vect.at(i) – big1.vect.at(j) + temp);

temp = 0;

}

else

{

rasn.push_front (big2.vect.at(i) – big1.vect.at(j) + 10 + temp);

temp = -1;

}

metka = i;

}

for (int i = metka-1; i >= 0; i–)

{

rasn.push_front (abs((big2.vect.at(i)+temp+10)%10));

if ((temp == -1) && (big2.vect.at(i) + temp) < 0) temp = -1; else temp = 0;

}

big2.vect = rasn;

return big2;

}

}

// _______________________ Произведениебольшихчисел _____________

BigInteger proisvedenie (BigInteger big1, BigInteger big2)

{

BigInteger proisv;

proisv.vect.push_back(0);

BigInteger reserv;

BigInteger reserv2;

for (int i = big1.vect.size() – 1, count = 0; i >= 0; i –, count++)

{

if (big1.vect.at(i) == 0) {} // умножениена 0

else

if (big1.vect.at(i) == 1) // умножение на 1, просто прибавляем число с «добитыми» нулями

{

reserv2.vect = big2.vect;

for (int k = 0; k < count; k++) // добиваем нулями в зависимости от разряда умножения

reserv2.vect.push_back(0);

proisv = summa (reserv2, proisv);

}

else

{

int temp = 0;

for (int k = 0; k < count; k++) // добиваемнулями

reserv.vect.push_front(0);

for (int j = big2.vect.size() – 1; j >=0; j–) // умножаемпервоечислона«цифру» изразрядаучитывая temp

{

reserv.vect.push_front((big1.vect.at(i)*big2.vect.at(j) + temp)%10);

if ((big1.vect.at(i)*big2.vect.at(j) + temp) >=10) temp = (big1.vect.at(i)*big2.vect.at(j) + temp)/10; else temp = 0;

}

if (temp!=0) reserv.vect.push_front(temp); // приувеличенииразрядовчисла

proisv = summa (reserv, proisv); // складываем предыдущие результаты

reserv.vect.clear();

}

}

if (big1.znak!= big2.znak)

proisv.znak = '-';

return proisv;

}

// __________________ Возведение в степень большого числа _________

BigInteger stepen (BigInteger big, int steps)

{

BigInteger step;

//deque<int> step = deque<int>();

step.vect = big.vect; // постоянный множитель

for (int i = 1; i < steps; i++) // числошаговравноестепени

big = proisvedenie (big, step);

if (steps% 2 == 0)

big.znak = ' ';

return big;

}

// __________________ Факториал большого числа ____________________

BigInteger faktorial (BigInteger big)

{

big.znak = ' ';

BigInteger fak;

fak.vect.push_back(1);

BigInteger edinica;

edinica.vect.push_back(1); // дляуменьшенияна 1

{

while (big.vect.size()!= 0 && big.vect.at(0)!= 0) // пока число не стало равным 0

{

fak = proisvedenie (big, fak);

big = rasnost (big, edinica);

big = dell_null(big);

fak = dell_null(fak);

}

}

return fak;

}

// __________________ Деление больших чисел _______________________

BigInteger delenie (BigInteger delimoe, BigInteger delitel)

{

BigInteger chastnoe;

BigInteger ostatok;

BigInteger reserv2;

BigInteger reserv3;

reserv2.vect = delitel.vect;

for (int i = 0; i < (int) delimoe.vect.size(); i++)

{

ostatok = dell_null(ostatok);

ostatok.vect.push_back (delimoe.vect.at(i)); // промежуточныйостаток

if (sravnenie (ostatok, delitel) == -1) {chastnoe.vect.push_back(0);} // покапромежуточныйостатокбольшеделителяпишемвчастное 0

else

{

for (int j = 0; j < 10; j++) // цикл, формирующий цифры частного

{

if (sravnenie (ostatok, reserv2) == -1) // промежуточный остаток меньше делителя*j

{

chastnoe.vect.push_back(j);

ostatok = rasnost (ostatok, reserv3);

reserv2.vect = delitel.vect;

break;

}

if (sravnenie (ostatok, reserv2) == 0) // промежуточныйостатоккратныйделителю

{

chastnoe.vect.push_back (j+1);

ostatok.vect.clear();

reserv2.vect = delitel.vect;

break;

}

reserv3 = reserv2;

reserv2 = summa (reserv2, delitel); // прибавляем сам делитель, пока не станет больше остатка

}

}

} // цифры делимого заканчиваются и остаток меньше делимого, цикл завершается

if (delimoe.znak!= delitel.znak) chastnoe.znak = '-';

return chastnoe;

}

// __________________ Остаток от деления больших чисел ____________

BigInteger ostatok_delenie (BigInteger delimoe, BigInteger delitel)

{ // все как в методе delenie(), только возвращаем не частное, а остаток

BigInteger chastnoe;

BigInteger ostatok;

BigInteger reserv2;

BigInteger reserv3;

reserv2.vect = delitel.vect;

for (int i = 0; i < (int) delimoe.vect.size(); i++)

{

ostatok = dell_null(ostatok);

ostatok.vect.push_back (delimoe.vect.at(i));

if (sravnenie (ostatok, delitel) == -1) {chastnoe.vect.push_back(0);}

else

{

for (int j = 0; j < 10; j++)

{

if (sravnenie (ostatok, reserv2) == -1)

{

chastnoe.vect.push_back(j);

ostatok = rasnost (ostatok, reserv3);

reserv2.vect = delitel.vect;

break;

}

if (sravnenie (ostatok, reserv2) == 0)

{

chastnoe.vect.push_back (j+1);

ostatok.vect.clear();

reserv2.vect = delitel.vect;

break;

}

reserv3 = reserv2;

reserv2 = summa (reserv2, delitel);

}

}

}

if (ostatok.vect.size() == 0) ostatok.vect.push_back(0);

return ostatok;

}

// _________ Метод для использования выражений для вычисления _____

BigInteger vichislenie()