//------------------------------------------------------------
// Klasa za rad sa velikim brojevima
// Autor: Nenad Bozidarevic
// E-mail: nbozidarevic@gmail.com
// Web sajt: http://www.bozidarevic.com/
//------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//------------------------------
// Klasa
//------------------------------
class VelikiBroj
{
private:
vector<char> _cifre;
bool _znak;
void postaviNaNulu(); // Resetovanje vrednosti broja na 0
void ukloniVodeceNule(); // Brisanje nula sa pocetka broja
public:
VelikiBroj(); // Default konstruktor koji broj postavlja na nulu
VelikiBroj(int x); // Konstruktor na osnovu broja
VelikiBroj(const string); // Konstruktor na osnovu stringa
void izIntegera(int); // Funkcija za formiranje broja iz integera
void izStringa(const string); // Funkcija za formiranje broja iz stringa
string uString() const; // Funkcija koja vraca broj kao string
VelikiBroj saberi(const VelikiBroj&) const;
VelikiBroj oduzmi(const VelikiBroj&) const;
VelikiBroj pomnozi(const VelikiBroj&) const;
VelikiBroj podeli(const VelikiBroj&) const;
int uporediApsolutne(const VelikiBroj&) const;
int uporedi(const VelikiBroj&) const;
};
//------------------------------
// Konstruktori
//------------------------------
VelikiBroj::VelikiBroj()
{
this->postaviNaNulu();
}
VelikiBroj::VelikiBroj(int broj)
{
this->izIntegera(broj);
}
VelikiBroj::VelikiBroj(const string broj)
{
this->izStringa(broj);
}
//------------------------------
// Pomocne funkcije
//------------------------------
void VelikiBroj::postaviNaNulu()
{
this->_cifre.clear(); // Brisemo sadrzaj vektora
this->_cifre.push_back(0); // Ubacujemo samo jednu cifru - nulu
this->_znak = true;
}
void VelikiBroj::izIntegera(int broj)
{
char cifra;
// Odredjujemo znak broja
if (broj < 0)
{
this->_znak = false;
broj = -broj;
}
else
{
this->_znak = true;
}
this->_cifre.clear(); // Brisemo sve cifre
while (broj != 0)
{
cifra = broj % 10; // Uzimamo krajnu desnu cifru broja
this->_cifre.push_back(cifra); // Ubacujemo je u nas vektor
broj /= 10;
}
}
void VelikiBroj::izStringa(string broj)
{
this->_cifre.clear();
this->_znak = true;
int pocetakBroja = 0;
int krajBroja = broj.length() - 1;
if (krajBroja < 0) // Ako je string prazan
{
this->postaviNaNulu();
return;
}
if (broj[0] == '+') // Ako je pozitivan broj
pocetakBroja++;
if (broj[0] == '-')
{
this->_znak = false;
pocetakBroja++;
}
if (krajBroja < pocetakBroja) // Ako nema nijedne cifre
{
this->postaviNaNulu();
return;
}
// Ubacujemo cifre pocevsi od krajnje desne
for (int i = krajBroja; i >= pocetakBroja; i--)
{
if (broj[i] > '9' || broj[i] < '0') // Ako nije cifra
{
this->postaviNaNulu();
return;
}
this->_cifre.push_back(broj[i] - '0');
}
// Ako je korisnik uneo vodece nule
this->ukloniVodeceNule();
}
void VelikiBroj::ukloniVodeceNule()
{
int brCifara = this->_cifre.size();
while (brCifara > 1 && this->_cifre[brCifara-1] == 0)
brCifara--;
this->_cifre.resize(brCifara);
// Ako smo dosli do -0, moramo da promenimo znak
if (this->_cifre.size() == 1 && this->_cifre[0] == 0)
this->_znak = true;
}
string VelikiBroj::uString() const
{
string s;
if (!this->_znak) s += '-'; // Dodajemo minus ako je potrebno
int i = this->_cifre.size();
while (i > 0)
{
i--;
s += (char)(this->_cifre[i] + '0');
}
return s;
}
//------------------------------
// Aritmeticke operacije
//------------------------------
VelikiBroj VelikiBroj::saberi(const VelikiBroj& broj) const
{
VelikiBroj rezultat;
// Ako su brojevi istog znaka, mozemo raditi kao na papiru
if (this->_znak == broj._znak)
{
rezultat._znak = this->_znak;
int aVelicina = this->_cifre.size();
int bVelicina = broj._cifre.size();
int velicina = max(aVelicina, bVelicina);
rezultat._cifre.resize(velicina);
char prenos = 0; // X pisem, PRENOS pamtim
char zbir;
for (int i = 0; i < velicina; i++)
{
// Moramo da pazimo ako je jedan broj duzi od drugog
zbir = ( (i < aVelicina) ? this->_cifre[i] : 0 ) + ( (i < bVelicina) ? broj._cifre[i] : 0 ) + prenos;
rezultat._cifre[i] = zbir % 10;
prenos = zbir / 10;
}
if (prenos > 0)
rezultat._cifre.push_back(prenos);
rezultat._znak = this->_znak;
}
else // A ako nisu, radimo komplementiranjem
{
rezultat._znak = true;
const VelikiBroj *prvi, *drugi;
if (this->_znak) // Pozitivan broj mora da bude prvi sabirak
{
prvi = this;
drugi = &broj;
}
else
{
prvi = &broj;
drugi = this;
}
int aVelicina = prvi->_cifre.size();
int bVelicina = drugi->_cifre.size();
int velicina = max(aVelicina, bVelicina);
rezultat._cifre.resize(velicina);
char prenos = 0;
char razlika;
for (int i = 0; i < velicina; i++)
{
razlika = ( (i < aVelicina) ? prvi->_cifre[i] : 0 ) - ( (i < bVelicina) ? drugi->_cifre[i] : 0 ) + prenos;
razlika += 10;
rezultat._cifre[i] = razlika % 10;
prenos = razlika / 10 - 1;
}
if (prenos < 0) // Obrcemo broj
{
prenos = 0;
for (int i = 0; i < velicina; i++)
{
razlika = 0 - rezultat._cifre[i] + prenos;
razlika += 10;
rezultat._cifre[i] = razlika % 10;
prenos = razlika / 10 - 1;
}
rezultat._znak = false;
}
}
rezultat.ukloniVodeceNule();
return rezultat;
}
VelikiBroj VelikiBroj::oduzmi(const VelikiBroj& broj) const
{
VelikiBroj pomocni = broj; // Konstruktor kopije
pomocni._znak = !pomocni._znak; // Menjamo znak
return this->saberi(pomocni);
}
VelikiBroj VelikiBroj::pomnozi(const VelikiBroj& broj) const
{
VelikiBroj rezultat;
// Odredjujemo znak
// + ako su oba cinioca istog znaka
rezultat._znak = (this->_znak == broj._znak);
// Odredjujemo koliko cifara moze da ima rezultat
int aVelicina = this->_cifre.size();
int bVelicina = broj._cifre.size();
rezultat._cifre.resize(aVelicina + bVelicina);
// Racunamo rezultat
char temp;
for (int i = 0; i < aVelicina; i++)
for (int j = 0; j < bVelicina; j++)
{
temp = rezultat._cifre[i+j] + this->_cifre[i] * broj._cifre[j];
rezultat._cifre[i+j] = temp % 10;
rezultat._cifre[i+j+1] += temp / 10;
}
// Uklanjamo vodece nule
rezultat.ukloniVodeceNule();
// Vracamo rezultat
return rezultat;
}
VelikiBroj VelikiBroj::podeli(const VelikiBroj& broj) const
{
VelikiBroj rezultat;
// Ukoliko je delilac nula, to nije dozvoljeno
// pa izbacujemo izuzetak
if (broj.uporedi(rezultat) == 0)
throw "Deljenje nulom";
// Proveravamo da li je deljenik manji ili jednak
// deliocu po apsolutoj vrednosti
int poredjenje = this->uporediApsolutne(broj);
// Ukoliko je manji, vracamo nulu
if (poredjenje == -1) return rezultat;
// Ukoliko su jednaki, vracamo jedinicu sa
// odgovarajucim znakom
if (poredjenje == 0)
{
if (this->_znak == broj._znak)
rezultat.izIntegera(1);
else
rezultat.izIntegera(-1);
return rezultat;
}
// Deljenik je veci, pa moramo da oduzimamo
VelikiBroj pomocni;
VelikiBroj jedan(1);
rezultat._znak = (this->_znak == broj._znak);
jedan._znak = rezultat._znak;
int brCifA = this->_cifre.size();
int brCifB = broj._cifre.size();
// Ukoliko deljenik ima dve ili vise cifre
if (brCifA - brCifB > 1)
{
for (int i = brCifA - brCifB; i > 2; i--)
rezultat._cifre.push_back(0);
rezultat._cifre.push_back(1);
pomocni = rezultat.pomnozi(broj);
}
// Vrsimo oduzimanje
while (true)
{
if (this->_znak == broj._znak)
pomocni = pomocni.saberi(broj);
else
pomocni = pomocni.oduzmi(broj);
if (pomocni.uporediApsolutne(*this) <= 0)
rezultat = rezultat.saberi(jedan);
else
break;
}
return rezultat;
}
//------------------------------
// Poredjenje
//------------------------------
int VelikiBroj::uporediApsolutne(const VelikiBroj& b) const
{
int brCifA = this->_cifre.size();
int brCifB = b._cifre.size();
// Ako jedan ima vise cifara, ocigledno je veci
if (brCifA < brCifB) return -1;
if (brCifA > brCifB) return 1;
// Imaju isti broj cifara, pa ih redom poredimo
for (int i = brCifA-1; i >= 0; i--)
if (this->_cifre[i] != b._cifre[i])
return (this->_cifre[i] < b._cifre[i]) ? -1 : 1;
// Ukoliko su im sve cifre jednake
return 0;
}
int VelikiBroj::uporedi(const VelikiBroj& b) const
{
// Ako nisu istog znaka, lako je odrediti
if (this->_znak != b._znak)
return (this->_znak) ? 1 : -1;
// Ako su istog znaka, poredimo apsolutne vrednosti
// i u zavisnosti od znaka vrsimo negaciju rezultata
int poredjenje = this->uporediApsolutne(b);
if (!this->_znak) poredjenje = -poredjenje;
return poredjenje;
}
int main()
{
VelikiBroj a("123");
VelikiBroj b("-123");
VelikiBroj c("11631");
VelikiBroj d("81315");
VelikiBroj e("-100000");
VelikiBroj f;
VelikiBroj g("369");
cout << "Uporedi apsolutno " << a.uString() << " i " << b.uString() << " : " << a.uporediApsolutne(b) << endl;
cout << "Uporedi apsolutno " << a.uString() << " i " << c.uString() << " : " << a.uporediApsolutne(c) << endl;
cout << "Uporedi apsolutno " << d.uString() << " i " << c.uString() << " : " << d.uporediApsolutne(c) << endl;
cout << "Uporedi apsolutno " << d.uString() << " i " << e.uString() << " : " << d.uporediApsolutne(e) << endl;
cout << "Uporedi apsolutno " << a.uString() << " i " << f.uString() << " : " << a.uporediApsolutne(f) << endl;
cout << endl;
cout << "Uporedi " << a.uString() << " i " << a.uString() << " : " << a.uporedi(a) << endl;
cout << "Uporedi " << a.uString() << " i " << b.uString() << " : " << a.uporedi(b) << endl;
cout << "Uporedi " << a.uString() << " i " << c.uString() << " : " << a.uporedi(c) << endl;
cout << "Uporedi " << d.uString() << " i " << c.uString() << " : " << d.uporedi(c) << endl;
cout << "Uporedi " << d.uString() << " i " << e.uString() << " : " << d.uporedi(e) << endl;
cout << "Uporedi " << a.uString() << " i " << f.uString() << " : " << a.uporedi(f) << endl;
cout << endl;
try
{
cout << b.uString() << " / " << b.uString() << " = " << b.podeli(b).uString() << endl;
cout << a.uString() << " / " << c.uString() << " = " << a.podeli(c).uString() << endl;
// cout << e.uString() << " / " << a.uString() << " = " << e.podeli(a).uString() << endl;
cout << d.uString() << " / " << c.uString() << " = " << d.podeli(c).uString() << endl;
cout << g.uString() << " / " << b.uString() << " = " << g.podeli(b).uString() << endl;
cout << g.uString() << " / " << a.uString() << " = " << g.podeli(a).uString() << endl;
cout << f.uString() << " / " << a.uString() << " = " << f.podeli(a).uString() << endl;
cout << a.uString() << " / " << f.uString() << " = " << a.podeli(f).uString() << endl;
}
catch (...)
{
cout << "Deljenje nulom!" << endl;
}
return 0;
}