codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
//------------------------------------------------------------ // 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; }
Private
[
?
]
Run code
Submit