to mi się jeszcze nie zdarzyło....
Zrobiłem sobie własne samorozszerzalne BigInty...
lecz..mój program daję różne wyniki w zależności od tego w jakim katalogu jest odpalany :/??:/ Oczywiście żadnych operacji które mogły by na to wpłynąć nie robie.
Zastanawiam się, czy to może mieć związek z dynamiczną alokacją pamięci..bo nic innego nie przychodzi mi do głowy...
spotkał się ktoś z czymś takim?
Generalnie alokuję pamięć za pomocą new, czasami, jak rozszerzam tablicę, to przepisuję zawartość za pomocą memcpy... i tyle operacji na pamięci. Żadnych wyjątków, że nie udało mi się zaalokować pamięci nie dostaję... nie mam pojęcia co się dzieje!!! MASAKRA :/
z całym szacunkiem dla moderatorów, którzy to przenieśli...ten kod, chyba nie jest Newbie:
#include <iostream>
#include <limits.h>
#include "bigint.h"
using namespace std;
int main()
{
BigInt tab[1001];
tab[0]=0;
tab[1]=1;
for(int i=2; i<1001; i++)
{
tab[i]= tab[i-1]*3- tab[i-2] + 2;
}
int c=0, i;
cin>>c;
while(c--)
{
cin>>i;
cout<<tab[i]<<endl;
}
return 0;
}
#ifndef BIGINT_H
#define BIGINT_H
#include <string>
#include <iomanip>
#include <iostream>
#include <cmath>
using namespace std;
typedef int64_t uLL; // uint64_t, to to samo co unsigned long long
class BigInt
{
public:
BigInt(uLL val=0);
BigInt(string number);
BigInt(const BigInt& a);
~BigInt();
enum sig{PLUS=false, MINUS=true};
void write() const;
void read(string number);
friend istream& operator>>(istream& s, BigInt& a);
friend ostream& operator<<(ostream& s, const BigInt& a);
friend BigInt operator+(uLL a, BigInt& b); //przyjmuje przez referencję ze względu na szybkość (natomiast, nie możemy przyjmować obu przez referencję, ponieważ, argumentem pierwszym może być stała, która to nie może zwrócić referencji)
BigInt operator+(const BigInt& b)const; //tu także. Nie trzeba wcale tak robić
BigInt operator-(const BigInt& b)const;
BigInt& operator=(BigInt b);
BigInt operator-()const;
BigInt operator*(int b); //pomocniczy.
BigInt operator*(const BigInt& b);
//operatory logiczne
bool operator==(const BigInt& b)const;
bool operator!=(const BigInt& b)const;
bool operator<(const BigInt& b)const;
bool operator>(const BigInt& b)const;
bool operator<=(const BigInt& b)const;
bool operator>=(const BigInt& b)const;
BigInt moreMinusLess(const BigInt& a, const BigInt& b)const;
BigInt lessMinusMore(const BigInt& a, const BigInt& b)const;
void expandAlocation(uLL newCapacity);
uLL capacity; //bieżąca pojemność danej liczby
uLL length; //bieżąca faktyczna długość danej liczby
private:
static const uLL base = 1000000000; //10^9
static const int digs = 9;
bool sign;
uLL *value; //uchwyt do tablicy w której będziemy trzymać wartość naszej liczby
};
#endif // BIGINT_H
#include "bigint.h"
/////////////////////////////////////////////////////////////////
//jest to konstruktor z argumentem domniemanym. Jeżeli nie podamy argumentu,
//będzie miał on wartość 0, co ustaliliśmy przy deklaracji funkcji
BigInt::BigInt(uLL val)
{
if(val==0)
{
sign = false;
length=1; // dlugość==0, bo zapiszemy sobie tam 0
capacity=2;//100;//2*length; // żeby potem zbyt często nie rozszerzać liczby, to ustalamy
//sobie początkową wartość pojemności trochę na wyrost
value = new uLL[capacity]; //alokujemy tablice o pojemności capacity
value[0]=val;
}
else
{
if(val<0) //czy liczba jest ujemna
{
sign=true;
val=-val;
}else sign=false;
length = ceil(floor(log10(val)+1)/(float)digs); // w ten sprytny sposób dowiadujemy się ile cyfr ma liczba val
//skoro log10(100)=2 (a 100 ma 3 cyfry)
//dla log10(1000)=3 (a 1000 ma 4 cyfry);
//dla 100<a<1000 log10(a) nalezy do (3,4)
capacity = 2*length;
value = new uLL[capacity];
for(int i=0; i<length; i++)
{
value[i]= val%base;
val /= base;
}
}
}
/////////////////////////////////////////////////////////////////
BigInt::BigInt(string number)
{
BigInt a;
*this = a;
read(number);
}
/////////////////////////////////////////////////////////////////
BigInt::BigInt(const BigInt& a):sign(a.sign), capacity(a.capacity),length(a.length)
{
// \note (noisy#9#): do usunięcia
//cout<<"Pracuje konstruktor kopiujacy(poj: "<<capacity<<")"<<endl;
value = new uLL[a.capacity];
memcpy(value,a.value,sizeof(uLL)*a.length);
}
/////////////////////////////////////////////////////////////////
BigInt& BigInt::operator=(BigInt a)
{
// TODO (noisy#1#): Dowiedzieć się dlaczego tak uparcie to nie chciało działać kiedy operator przypisania dostawał argument przez referencję.
if(&a==this) return *this;
this->~BigInt(); //jawne wywołanie konstruktora. Skoro jakiś obiekt ma być zapisany na nasz
//to powinnismy zwolnic pamięć jaką wcześniej nasz obiekt posiadał
BigInt w;
sign = a.sign;
capacity = a.capacity;
length = a.length;
value = new uLL[capacity];
memcpy(value,a.value,sizeof(uLL)*a.length);
//cout<<"Przypusuje =, poj:"<<capacity<<endl;
}
/////////////////////////////////////////////////////////////////
BigInt::~BigInt()
{
delete[] value; // zwalniamy pamięć w jakiej trzymaliśmy wartość naszej liczby
}
/////////////////////////////////////////////////////////////////
void BigInt::write()const
{
if(sign)cout<<"-";
cout<<value[length-1];
for(int i=length-2; i>=0; i--)
{
cout<<setw(digs)<<setfill('0')<<value[i];
}
}
/////////////////////////////////////////////////////////////////
ostream& operator<<(ostream& s, const BigInt& a)
{
a.write();
return s;
}
/////////////////////////////////////////////////////////////////
void BigInt::read(string number)
{
if(number[0]=='-') //czy liczba jest ujemna
{
sign=true;
number.erase(0,1);
}
else sign=false;
// TODO (noisy#5#): zastanowić się, czy zrobić zabezpieczenie przed -0
length = ceil(number.size()/(float)digs);
if(length>capacity) //jezeli bieżąca pojemność naszej liczby jest za mała, to sobie robimy więcej miejsca
{
expandAlocation(2*length); //zeby zbyt często nie powiększać (bo to jest kosztowne ze względu na czas)
//cout<<"wczytywanie, poj: "<<capacity<<endl; //to alokuje dwa razy wiecej niż w danej chwil potrzeba
}
int LengthFirsDigit = number.size()%digs; // reszta " dużych cyfr" będzie posiadała po digs małych cyfr
int c=1; //poprawka // TODO (noisy#4#): Pomyslec, czy da sie to lepiej zapisac!!
if(LengthFirsDigit != 0)
{
value[length-1] = atoll(number.substr(0,LengthFirsDigit).c_str()); //wczytanie pierwszej "cyfry" z lewej
number.erase(0,LengthFirsDigit); //number zawiera same duże cyfry, które zawieracją dokładnie digs małych cyfr
c=0;
}
for(int i=length-2+c, k=0; i>=0; i--,k++)
{
value[i] = atoll( number.substr(k*digs,digs).c_str() );
}
}
/////////////////////////////////////////////////////////////////
istream& operator>>(istream& s, BigInt& a)
{
string number;
cin>>number;
a.read(number);
return s;
}
/////////////////////////////////////////////////////////////////
BigInt BigInt::operator+(const BigInt& b)const
{
const BigInt &a=*this; //dla wygody, by na pierwszy argument (który się dostaje domyślnie), nie odwoływać się
//np this.value[0], a na drugi b.value[0], tylko symetrycznie a.value[0], b.value[0]
if(a.sign == MINUS && b.sign == MINUS) /*(-3)+(-4) = -(3+4) */ return -((-a)+(-b));
else if(a.sign == MINUS && b.sign == PLUS) /* (-5)+8 = -(5-8) */ return -((-a)-b);
else if(a.sign == PLUS && b.sign == MINUS) /* 23+(-12)=23-(12) */ return a-(-b);
else if(a.sign == PLUS && b.sign == PLUS)
{
BigInt w;
int maxLength = max(a.length, b.length); //jaką maksymalną długość będzie miała suma? np 999 + 99= 1098
//czyli max(3,2)+1 = 4, czyli ok
if(maxLength >= w.capacity)w.expandAlocation(2*maxLength);
int minLength = min(a.length, b.length);
w.length=0;
int c=0;
uLL &i=w.length; //skoro zmienna i jest referencją na w.length to musimy pamietac,
//że inkrementując i, robimy to tak naprawde na w.length,
//ale o to nam właśnie chodzi, robicy referencje dla wygody
for (i=0; i < minLength; i++)
{
w.value[i] = (a.value[i] + b.value[i] + c) % base;
c = (a.value[i] + b.value[i] + c) / base;
}
for(; w.length < a.length; i++)
{
w.value[i] = (a.value[i] + c) % base;
c = (a.value[i] + c) / base;
}
for(; w.length < b.length; i++)
{
w.value[i] = (b.value[i] + c) % base;
c = (b.value[i] + c) / base;
}
if(c > 0) w.value[i++] = c;
return w; //zwracam przez wartość, gdyż operator=, zadba mi o to, by skopiować należycie zawartość
//gdybyśmy zwracali przez referencje, to żadne kopiowanie by się nie odbyło, a musimy
//pamiętać, że przecież wykona się destruktor, który nam skasuje pamiec. Referencja odnosiła
//by się wówczas do miejsca, które nie wiadomo na co wskazuje.
}
}
/////////////////////////////////////////////////////////////////
BigInt operator+(uLL a, BigInt& b)
{
return b+a;
}
/////////////////////////////////////////////////////////////////
void BigInt::expandAlocation(uLL newCapacity)
{
// \note (noisy#9#): do usunięcia
//cout<<"(EA) poj: "<<newCapacity<<endl;
uLL *newValue = new uLL[newCapacity];
memcpy(newValue,value,sizeof(uLL)*length); //kopiuje wszystkie komórki ze starej tablicy do nowej
delete []value; //skoro te komórki są już skopiowane, to mogę zwolnić pamięć
value = newValue; //przepisuje wskaźnik nowej tablicy na starą, by klasa ciągle mogła się odnosić do value
capacity=newCapacity;
}
/////////////////////////////////////////////////////////////////
BigInt BigInt::operator-(const BigInt& b)const
{
const BigInt &a=*this;
BigInt w;
if(a==b)
w=0;
else
if(a.sign == PLUS && b.sign == PLUS)
w = (a>b)?
moreMinusLess(a,b):
lessMinusMore(a,b);
else
if(a.sign == MINUS && b.sign == PLUS)/*(-4)-(2) = -(4+2) */
w = -((-a)+b);
else
if(a.sign == PLUS && b.sign == MINUS)/*(4)-(-2) = 4 + 2 */
w = a+(-b);
else /*a.sign == MINUS && b.sign == MINUS*/
{
if(a<b) // (-23)-(-12) = (-23)+12 = (12)-(23)
w = lessMinusMore(-b,-a);
else // (-14)-(-20) = (-14)+20 = (20)-(14)
w = moreMinusLess(-b,-a);
}
//cout<<"oDejmowanie, w: "<<w<<endl;
return w;
}
/////////////////////////////////////////////////////////////////
BigInt BigInt::moreMinusLess(const BigInt& a, const BigInt& b)const
{
// jeżeli a > 0, b > 0, a>b -> wynik będzie dodatni
BigInt w;
w.length=a.length;
w.expandAlocation(2*w.length);
int i=0, borrow=0;
for(; i<b.length; i++)
{
w.value[i] = a.value[i] - b.value[i] - borrow;
//cout<<w.value[i]<<"= a.value["<<i<<"]="<<a.value[i]<<" - "<<"b.value["<<i<<"]="<<b.value[i]<<" - borrow="<<borrow<<endl;
if(w.value[i]<0)
{
w.value[i]+= BigInt::base;
//cout<<"w.value["<<i<<"]="<<w.value[i]<<endl;
borrow=1;
}
else borrow=0;
}
////////////////////////////////////////////////////////////////// TEGO TUTAJ BRAKOWAŁO :/ ////////////////
for(; i<a.length ;i++)
{
w.value[i] = a.value[i] - borrow;
borrow=0;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
while(w.length >1 && w.value[w.length-1]==0)
{
w.length--;
}
return w;
}
/////////////////////////////////////////////////////////////////
BigInt BigInt::lessMinusMore(const BigInt& a, const BigInt& b)const
{
//a-b = (14)-(17) = -((-14)+(17)) = -((17)-(14)) = -(b-a)
return -moreMinusLess(b,a);
}
/////////////////////////////////////////////////////////////////
bool BigInt::operator==(const BigInt& b)const
{
const BigInt &a=*this;
if(a.length!=b.length || a.sign!=b.sign ) return false;
for(int i=0; i<length; i++)
{
if(a.value[i]!=b.value[i]) return false;
}
return true;
}
/////////////////////////////////////////////////////////////////
bool BigInt::operator!=(const BigInt& b)const
{
return !(*this==b);
}
/////////////////////////////////////////////////////////////////
BigInt BigInt::operator-()const
{
BigInt w=*this;
w.sign = !sign;
return w;
}
bool BigInt::operator<(const BigInt& b)const
{
const BigInt &a=*this;
if(a.sign == MINUS && b.sign == PLUS ) return true; // -a < b
else if(a.sign == PLUS && b.sign == MINUS ) return false; // a > -b
else if( a == b ) return false;
else if(a.sign == PLUS && b.sign == PLUS )
{
if( a.length > b.length) return false;
else if (a.length < b.length) return true;
else //( a.length == b.length )
{
for(int i=a.length-1; i>=0; i--)
{
if(a.value[i] < b.value[i] ) return true;
else if(a.value[i] > b.value[i] ) return false;
//else (a.value[i] == b.value[i]) continue...
}
}
}
else{ //(a.sign == MINUS && b.sign == MINUS )
if( a.length > b.length) return true;
else if (a.length < b.length) return false;
else //( a.length == b.length )
{
for(int i=a.length-1; i>=0; i--)
{
if(a.value[i] > b.value[i] ) return true;
else if(a.value[i] < b.value[i] ) return false;
//else (a.value[i] == b.value[i]) continue...
}
}
}
}
/////////////////////////////////////////////////////////////////
bool BigInt::operator>(const BigInt& b)const
{
return !(*this==b || *this<b);
}
/////////////////////////////////////////////////////////////////
bool BigInt::operator<=(const BigInt& b)const
{
return (*this<b || *this==b);
}
/////////////////////////////////////////////////////////////////
bool BigInt::operator>=(const BigInt& b)const
{
return (*this>b || *this==b);
}
/////////////////////////////////////////////////////////////////
BigInt BigInt::operator*(int b)
{
BigInt &a=*this;
//cout<<value[0];
BigInt w;
w.length = a.length;
w.expandAlocation(2*w.length);
int c=0;
for(int i=0; i<a.length; i++)
{
w.value[i] = (a.value[i]*b+c)%base;
//cout<<"w.value["<<i<<"]="<<w.value[i]<<", ("<<a.value[i]<<"*"<<b<<")="<<(a.value[i]*b+c)%base<<endl;
c=(a.value[i]*b)/base;
//cout<<"przeniesienie= "<<c<<endl;
}
while (c > 0)
{
w.value[w.length] = c % base;
c /= base;
w.length++;
}
//cout<<"mNozenie, w: "<<w<<endl;
return w;
}
/////////////////////////////////////////////////////////////////
BigInt BigInt::operator*(const BigInt& b)
{
BigInt &a=*this;
BigInt w;
w.expandAlocation(2*(a.length+b.length));
// FIXME (noisy#1#): do naprawy
for(int i=0; i<b.length;i++)
{
BigInt pom(a*b.value[i]);
//cout<<pom<<endl;
pom.expandAlocation(pom.length+i);
for(int j = pom.length-1; j>=0; j--)
{
pom.value[j+i] = pom.value[j];
}
for(int j=0; j<i; j++)
{
pom.value[j]=0;
}
pom.length += i;
w = w + pom;
}
return (a.sign != b.sign)?-w:w;
}
/////////////////////////////////////////////////////////////////
</b>