Feladat: 3. Valósítsa meg a nagyon nagy számok típusát! Ábrázoljuk a számokat számjegyeik sorozatával, amelyet egy dinamikus helyfoglalású tömbben helyezzünk el, és implementáljuk a hatékony összeadás és a szorzás műveleteit! Alkalmazzon operátor túlterhelést és kivételkezelést! Tegye lehetővé két nagy szám típusú változó közötti értékadást!
Nagy számok típusa: A feladat a nagy számok ábrázolását, azok összeadását és szorzását tűzi ki célul.
Típusérték-halmaz: A számokat számjegyeikből alkotott dinamikus helyfoglalású tömbben tároljuk, balról jobbra és külön a hosszát. Így a tömb utolsó indexű értéke lesz az egyes helyi értékű, az első pedig a legnagyobb helyi érték. Formálisan:
Típusműveletek: Értékadás operátor: Az értékadást teszi lehetővé (tényleg).
Bitshift << operátor: A számjegyeket string-gé alakítja.
Összeadás operátor: Két Szam típusú számot képes összeadni. c:= a + b
Szorzás egésszel operátor: Egy nagy szám és egy egész típusú szám szorzása. c:=a*d;
Szorzás nagy számmal operátor: Két nagy szám összeszorzása. c:=a*b
Implementáció: Az implementáció a specifikációknak megfelelően történik. A ciklusok indexelése mindenhol megváltozik 1-ről 0-ra, ezt külön nem jelzem minden függvénynél. További változások:
Értékadás operátor: Mivel az adatok dinamikus helyfoglalású tömbben tárolódnak, amire egy pointer mutat, ezért a közvetlen másolás esetén mindkét objektum ugyanarra a memóriacímre mutatna. Ezért az (a=b') értékadásnál valójában törölni kell az aktuális pointert és újra lefoglalni a memóriát, majd feltölteni.
Bitshift << operátor: A bitshift operátor implementálása a specifikációnak megfelelően történik, ahol az os String valójában egy ostream, így a is valójában << operátorral valósul meg.
Összeadás operátor: Az implementáció a specifikációnak megfelelően történik. Megjegyzés: A tovabb egyetlen változó, ennek a ciklus folyamán történő változását jelzik az alsó indexek.
Szorzás egésszel operátor: Az implementáció ebben az esetben jelentősen eltér a specifikácitól. Ennek oka a maradékok egyenletes eloszlásában keresendő. Bár a végeredmény ugyanaz lesz. További magyarázat a kódnál található.
Szorzás nagy számmal operátor: A megvalósítás elég egyszerű. Az előző két operátor segítségével oldjuk meg a feladatot. A c.length-ről nem esik szó, ezt az összeadás és az egész-szorzás operátorokok már kezelik, így nekünk azzal semmi dolgunk.
C++ megvalósítás: A nagy szám osztálya a fentieknek megfelelően a Szam nevet kapja: class Szam {…}
Az osztályban két privát változó van, a szám hossza és a számjegyek. A számjegyeket dinamikus helyfoglalású 2byte-os short integerként tároljuk, a hossz egyszerű integer. private: short* szjegyek; int length;
A osztályban 5 konstruktor van, ezek a következők: Szam(std::string szam); Szam(); Szam(short* input, int len); Szam(long* input, int len); Szam(int input);
A konstruktorok feladata, hogy a length és szjegyek értékét megadják. Ezen felül a konstruktorok felelnek azért, hogy a szám ne kezdődhessen 0-kal. Az egyes konstruktoroknak egyéb feladataik is vannak. A string-ből képző konstruktor „megtisztítja” a bemenetet a betűktől és egyéb karakterektől. Ide tartozik a „-” jel is, így a negatív szám ily módon pozitívvá válik. Ez a felhasználót remélhetőleg nem téveszti meg, hiszem a program egyértelműen elmondja, hogy csak pozitív számokkal dolgozik. A short és long tömbökből képző konstruktorok közel azonosak az = operátorral. Mivel a C++-ban a dinamikus helyfoglalású tömbök méretét nem lehet meghatározni, ezt a számot „pórázon” kell vinni a tömb mellett, ezt szolgálja a len változó. Az egész bemenet hasonló a stringhez, itt nincs szükség se kezdő nullák lecsapására, se egyéb karakterek eltávolítására. A osztályban egyetlen barát függvény található, ez a << operátor. Az osztály definíciója (szam.h): class Szam { public: Szam(std::string szam); Szam(); Szam(short* input, int len); Szam(long* input, int len); Szam(int input);
~Szam(); enum Exceptions {NUMBER_ERROR}; Szam operator+(const Szam& masik); Szam operator*(const int masik); Szam operator*(const Szam& masik); friend std::ostream& operator<<(std::ostream &os, const Szam& a); Szam& operator=(const Szam& mivel); private: short* szjegyek; int length; }; std::ostream& operator<<(std::ostream &os, const Szam& a);
Metódusok: A metódusok definíciója a szam.cpp-ben található. Szükséges könyvtárak: – iostream, sstream, string, cstdlib, math.h A definíciók elé írandó még a using namespace std;
Szam::Szam() Feladat: Legalapabb konstruktor. Létrehoz egy 1 hosszú tömböt, melynek egyetlen, első eleme a 0. Az egy hosszt is elmenti az osztály privát változójába. Bemeneti változók: nincsenek Kimeneti változók: nincs (maga az osztály) Kód: Szam::Szam() { this->szjegyek = new short[1]; this->szjegyek[0] = 0; this->length = 1; }
Szam::Szam (string input) Feladat: Ez a konstruktor stringet kér paraméterként, amit első lépésben megtisztít a felesleges karakterektől és jelektől (betűk, előjelek, stb.). A tiszta stringről aztán levágja a kezdő nullákat, majd létrehozza a privát változókat és értéket ad nekik. Bemeneti változók: string számokkal, karakterekkel, mindennel Kimeneti változók: nincs (maga az osztály)
Kód: Szam::Szam (string input) { //1. lépés: String megtisztítása a felesleges betűktől, speciális hülyeségektől, amit a user odaszemetel string tiszta_string; for (unsigned int i = 0; i < input.length(); i++) { if (int(input[i]) >= 48 && int(input[i]) <= 57) { // 0 karakter ascii kódja 48, a 9-esé 57, a többi a közte lévő sorban tiszta_string += input[i]; } } //2. képés: A kezdő nullák lecsapása. this->length = tiszta_string.length(); { int i = 0; while (tiszta_string[i] == '0' && this->length > 1) { this->length--; i++; } } //3. képés: A tiszta string konvertálása számjegyekké if (this->length < 1) { //0 és 1 hossz miatti félreértések elkerülésére a 0 számmal kapcsolatban. this->szjegyek = new short[1]; this->szjegyek[0] = 0; this->length = 1; } else { //A többi szám this->szjegyek = new short[this->length]; for (int i = 0; i < this->length; i++) { szjegyek[i] = short(tiszta_string[i])-48; //Ascii kód } } }
Szam::Szam (int input) Feladat: Negatív számra kivételt dob, a többi számra létrehozza az objektumot a megfelelő hosszon és számjegyekkel. Itt nincs szükség a kezdő nullák levágására. Bemeneti változók: az egész szám Kimeneti változók: nincs (maga az osztály) Kód: Szam::Szam (int input) {
if (input < 0) throw CONSTRUCT_NEGATIVE; //Negatív számnál dobjon kivételt if (input == 0) { //Nulla this->length = 1; this->szjegyek = new short[this->length]; this->szjegyek[0] = 0; } else { //Többi this->length = int(log10(input))+1; this->szjegyek = new short[this->length]; for (int i = 1; i <= this->length; i++) { szjegyek[length-i] = input%10; input = input/10; } } }
Szam::Szam (short* input, int len) Feladat: Egy short int tömbre mutató pointer és annak hossza a bemenet. A tömböt átmásolja az objektum szjegyek tömbjébe a hosszot pedig eltárolja a length-ben. Bemeneti változók: short int tömbre mutató pointer és hossza (int). Kimeneti változók: nincs (maga az osztály) Kód: Szam::Szam (short* input, int len) { this->length = len; int i = 0; //1. lépés: kezdő nullák lecsapása while (input[i] == 0 && this->length > 1) { this->length--; i++; } //2. lépés: szám eltárolása if (this->length < 1) { //0 this->szjegyek = new short[1]; this->szjegyek[0] = 0; this->length = 1; } else { //többi this->szjegyek = new short[this->length]; for (int j = 0; j < this->length; j++, i++) { szjegyek[j] = input[i]; } } }
Szam::Szam (long* input, int len) Feladat: Egy long int tömbre mutató pointer és annak hossza a bemenet. A tömböt átmásolja az objektum szjegyek tömbjébe a hosszot pedig eltárolja a length-ben. Bemeneti változók: long int tömbre mutató pointer és hossza (int). Kimeneti változók: nincs (maga az osztály) Kód: Szam::Szam (long* input, int len) { this->length = len; int i = 0; //1. lépés: kezdő nullák lecsapása while (input[i] == 0 && this->length > 1) { this->length--; i++; } //2. lépés: szám eltárolása if (this->length < 1) { this->szjegyek = new short[1]; this->szjegyek[0] = 0; this->length = 1; } else { this->szjegyek = new short[this->length]; for (int j = 0; j < this->length; j++, i++) { szjegyek[j] = input[i]; } } }
Szam::~Szam () Feladat: Az osztály törlésére szolgáló destruktor. Felszabadítja a számra lefoglalt memóriát. Bemeneti változók: nincsenek. Kimeneti változók: nincs (destruktor) Kód: Szam::~Szam () { delete[] this->szjegyek; }
ostream& operator<<(ostream &os, const Szam& a) Feladat: A Szam barát függvénye, de az std-hez tartozik. Ostream-be írja ki a tárolt számot. Bemeneti változók: ostream referencia, szám objektuma. Kimeneti változók: az ostream-mel tér vissza, amit kapott. Megjegyzés: Mivel barát függvény, hozzáfér az a bemeneti Szam privát változóihoz. Kód: ostream& operator<<(ostream &os, const Szam& a) {
for (int i = 0; i < a.length; i++) { os << a.szjegyek[i]; } return os; }
Szam& Szam::operator=(const Szam& a) Feladat: Értékadás operátor. Törli a szjegyek din. hely. tömböt, új értéket az a length-nek és beírja az új számjegyeket. Ha a két Szam azonos, akkor az elején visszadobja. Bemeneti változók: a Szam, amivel értéket adunk Kimeneti változók: a Szam, ami új értéket kapott Kód: Szam& Szam::operator=(const Szam& a) { if (this == &a) return *this; delete[] szjegyek; this->szjegyek = new short[a.length]; this->length = a.length; for (int i = 0; i < a.length; i++) { this->szjegyek[i] = a.szjegyek[i]; } return *this; }
Szam Szam::operator+(const Szam& masik) Feladat: Két nagy szám összeadása. Első lépésként kiszámolja az új Szam maximális hosszát, ami a rosszabbik szám +1 lehet (biz. Trivi :) ). Létrehozza a tovabb változót, amiben az összeadás 10 feletti részét viszi majd tovább a következő ciklusra. Bemeneti változók: Az összeadás egyik tagja this, a másik a paraméterként megjelenő Szam; Kimeneti változók: az összeg Szam Kód: Szam Szam::operator+(const Szam& masik) { //Az új szám maximális lehetséges hosszának meghatározása: hosszabbik szám maximum 1 nagyságrenddel változhat (99+99 is csak 198 stb.) int uj_length; if (length >= masik.length) uj_length = length+1; else uj_length = masik.length+1; short* x; //Eredmény számjegyei x = new short[uj_length]; short tovabb = 0; //Az összeadás 10 feletti részét ebben visszük tovább for (int i = 1; i <= uj_length; i++) { //Amíg van egyik vagy másik számjegy, addig hozzáadjuk az előző körből hozott "maradékhoz". if (i <= length) tovabb += szjegyek[length-i];
if (i <= masik.length) tovabb += masik.szjegyek[masik.length-i]; //Egyesek az összeg aktuális helyiértékére, a többit továbbvisszük. x[uj_length-i] = tovabb%10; tovabb = tovabb/10; } Szam ret(x, uj_length); delete[] x; return ret; }
Szam Szam::operator*(const int egesz) Feladat: Egy nagy szám egész számszorosát adja vissza. Negatív paraméter esetén kivételt dob. Az új szám maximális hossza a nagy szám hossza + az egész szám hossza. A maradékok feltorlódhatnak, ezért long tömböt használunk. A további biztonság kedvéért a maradékokat több lépésben, külön-külön visszük át a következő helyiértékre, ez jelentősen nem növeli meg a futásidőt sem. Bemeneti változók: A nagy szám a this, az egész paraméterként jelenik meg. Kimeneti változók: Az eredmény Szam Kód: Szam Szam::operator*(const int egesz) { //Az új szám maximális hossza: if (egesz < 0) throw MULTI_NEGATIVE; int uj_length = length + int(log10(egesz+0.5))+1; // pl ha 10 az int, akkor a logaritmus értéke 1, az szorzat is 1 nagyságrenddel változik stb long *x; //Nagy maradékok is lehetnek. x = new long[uj_length]; for (int i = 1; i <= length; i++) { x[uj_length-i] = szjegyek[length-i] * egesz; } for (int i = length+1; i <= uj_length; i++) { x[uj_length-i] = 0; } bool kesz = false; //Maradékok kezelése - bár többször végigmegy a tömbön, az x biztosan nem csúszik ki, míg ha egyben menne a végig, a maradék annyira feltorlódna egy nagy egész esetén, hogy a longból is kicsúszna while (!kesz) { kesz = true; for (int i = 1; i < uj_length; i++) { if (x[i] >= 10) { x[i-1] += x[i]/10; x[i] = x[i]%10; if (x[i-1] >= 10) kesz = false; }
} } return Szam(x,uj_length); }
Szam Szam::operator*(const Szam& masik) Feladat: Két nagy szám szorzatát adja meg. A második szám számjegyeit egyesével szorozza be, majd a megfelelő helyiértékre szorozza 10-essével. Ezeket a nagy számokat hozzáadja az x-hez, ami majd a végeredmény lesz. Bemeneti változók: Az egyik nagy szám a this, a másik paraméterként jelenik meg. Kimeneti változók: Az eredmény Szam Kód: Szam Szam::operator*(const Szam& masik) { Szam x,temp; ostringstream os; for (int i = 1; i <= masik.length; i++) { temp = *this * int(masik.szjegyek[masik.length-i]); for (int j = 1; j < i; j++) { temp = temp * 10; } x = x + temp; temp = Szam(); } return x; }
Teszkörnyezet: Az alábbi tesztökörnyezetet használtama a teszteléshez: #include "szam.h" #include
#include #include <sstream> #include using namespace std; //Konstansok: const string MENU_WELCOME = "Ez a program majdnem tetszoleges nagy egesz szamok es vele kapcsolatos muveletekkel kepes dolgozni. Valassz az alabbi pontok kozul."; const string MENU_OPTIONS = "\n\n1. a+b (operator+)\n2. a*integer (operator*)\n3. a*b (operator*)\n4. a:=b (operator=)\n5. Kiiratas(operator<<)\n6. 'a' szam megadasa\n7. 'b' szam megadasa\n0. Kilepes"; const string MENU_QUESTION = "Valassz(0-7): ";
const string MENU_NEED_TWO_NUMS = "Es most kerek 2 szamot, a-t es b-t!"; const string MENU_FILE_OR_KEY = "Fajlbol szeretnel szamot beolvasni? (y/n) "; const string MENU_IN_FILE = "Ird be a fajl utvonalat, amiben a szam van (elso sorban kell lennie): "; const string MENU_IN_KEY = "Ird be ide a szamot: "; const string MENU_IN_INT = "Irj be egy pozitiv integert: "; const string MENU_FILE_ERR = "Fajlbeolvasasi hiba."; const string MENU_RES = "A muvelet eredmenye: ";
/////////////////////////////////////////////// //Menü osztály deklarációja class Menu { public: //Konstruktor Menu(); int Run(); private: //A nagy szám osztályának egy példánya enum Exceptions {UNK_OPTION, FILE_ERROR}; Szam a; //egyik szám Szam b; //másik szám Szam c; //eredmény int d; //integer int opt; //választott szám //A menü kiíratása void WriteMenu() const; //Válaszlehetőség bekérése int GetOption(); //Szám bekérése Szam GetSzam(); int GetInt(); //Beviteli lehetőségek bool FileInput(string filename, Szam &x); }; /////////////////////////////////////////////// int main() { Menu menu;
return menu.Run(); }
/////////////////////////////////////////////// //A Menu osztály funkciói: Menu::Menu() { this->opt = 0; } int Menu::Run() { cout << MENU_WELCOME << endl; cout << MENU_NEED_TWO_NUMS << endl; try { try { a = this->GetSzam(); b = this->GetSzam(); do { this->WriteMenu(); opt = this->GetOption(); switch (opt) { case 6: a = GetSzam(); break; case 7: b = GetSzam(); break; case 1: c = a + b; cout << "a: " << a << endl << endl; cout << "b: " << b << endl << endl; cout << "Osszeg: " << c << endl << endl; break; case 3: c = a * b; cout << "a: " << a << endl << endl; cout << "b: " << b << endl << endl; cout << "Szorzat: " << c << endl << endl; break; case 2: d = this->GetInt();
c = a * d; cout << "a: " << a << endl << endl; cout << "int: " << d << endl << endl; cout << "Szorzat: " << c << endl << endl; break; case 4: a = b; cout << "Az ertekadas megtortent!"; break; case 5: cout << "a: " << a << endl << endl; cout << "b: " << b << endl << endl; break; case 0: cout << "Viszlát!"; break; default: throw UNK_OPTION; } //switch } while (opt != 0); //do return 0; } catch(Szam::Exceptions ex) { //try if (ex == Szam::MULTI_NEGATIVE) cout << "Negativ szorzotag!" << endl; if (ex == Szam::CONSTRUCT_NEGATIVE) cout << "Hiba! Negativ szamot kaptam!" << endl; } } catch(Menu::Exceptions ex) { //try if (ex == FILE_ERROR) cout << "Fajlhiba tortent!" << endl; if (ex == UNK_OPTION) cout << "Ismeretlen menupont!" << endl; } return 1; } void Menu::WriteMenu() const { cout << MENU_OPTIONS << endl; } int Menu::GetOption() { string temp; do {
cout << MENU_QUESTION; getline(cin, temp); } while (atoi(temp.c_str()) < 0 || atoi(temp.c_str()) > 7); return atoi(temp.c_str()); } int Menu::GetInt() { string temp; int x; cout << MENU_IN_INT << endl; getline(cin, temp); x = atoi(temp.c_str()); return x; } Szam Menu::GetSzam() { int step = 0; string temp; Szam x; do { if (step == 0) cout << MENU_FILE_OR_KEY; if (step == 1) cout << MENU_IN_FILE; if (step == 2) cout << MENU_IN_KEY; getline(cin, temp); switch (step) { case 0: //Fájl vagy billentyűzet if (temp == "y" || temp == "Y" || temp == "1") step = 1; if (temp == "n" || temp == "N" || temp == "0") step = 2; break; case 1: //Fájl if (this->FileInput(temp, x)) step = 3; break; case 2: //Bill x = Szam(temp); step = 3; break; } } while (step < 3); return x; }
bool Menu::FileInput(string temp, Szam &x) { ifstream befile; string sor, szamstr; befile.open(temp.c_str()); if (befile.fail()) { cout << MENU_FILE_ERR << endl; return false; } while(!befile.eof()) { getline(befile, sor); szamstr += sor; } x = Szam(szamstr); return true; } ///////////////////////////////////////////////
Fekete doboz tesztelés: –
A különböző menüpontok végrehajtása, próbája:
–
Értékadás
–
Összadás
–
Szorzás egésszel
–
Szorzás nagy számmal.
Fehér doboz tesztelés: –
0,1 és egészen nagy bemenetek tesztje.
–
Kivételek előcsalása
