Kodowanie Efektywnych Algorytmów - Ćwiczenia 7
Poprzednie
Następne
Temat: Operacje na dużych liczbach
Często zdarza się, że trzeba operować na liczbach większych niż maksymalne wartości, których używamy w kompilatorach. Wówczas na pomoc muszą przyjść operacje pisemne na tzw. Bignumach.
Poniżej przykładowa implementacja klasy BigNum (do dużych liczba naturalnych) wraz z komentarzami, którą można wykorzystać do implementacji zadań:
// Implementacja struktury BigNum, realizujacej arytmetyke wielkich liczb
struct BigNum {
// Makro słuzace do eliminowania wiodacych zer
#define REDUCE() while(len>1 && cyf[len-1]==0) len--;
// Podstawa, przy której wykonywane sa obliczenia oraz liczba zer w podstawie
static const int BASE=1000000000, BD=9;
// Zmienna len reprezentuje aktualna długosc liczby (liczbe cyfr), a al
// wielkosc zaalokowanej pamieci do przechowywania cyfr liczby
int len, al;
// Wskaznik do tablicy cyfr liczby
LL* cyf;
// Konstruktor liczby o wartosci v i zaalokowanej pamieci dla l cyfr
BigNum(int v=0, int l=2) {
len=1; al=l;
cyf = new LL[al];
REP(x,al) cyf[x]=0;
cyf[0]=v;
if (v>=BASE) przen(1);
}
// Konstruktor, przypisujacy wartosc innej liczby typu BigNum
BigNum(const BigNum &a) {
len=al=a.len;
cyf = new LL[al];
REP(x,al) cyf[x]=a.cyf[x];
}
// Destruktor
~BigNum(){delete cyf;}
// Funkcja przyjmuje jako parametr zapotrzebowanie na liczbe cyfr i jesli
// zapotrzebowanie jest wieksze od aktualnego rozmiaru tablicy cyfr, to dokonuje
// realokacji
void Res(int l) {
if (l>al) {
l=max(l,2*al);
LL* n = new LL[l];
REP(x,l) n[x] = x>=al ? 0 : cyf[x];
delete cyf;
cyf = n;
al = l;
}
}
// Funkcja dokonuje przenoszenia do starszych cyfr nadmiaru powstałego na skutek
// wykonywania operacji. Jest to jedyne miejsce w całej strukturze, gdzie
// wykonuje sie ta operacje. Parametr okresla liczbe cyfry, do której nalezy
// wykonac przenoszenie nadmiaru
void przen(int p) {
int x=0;
for(;x<p || cyf[x]<0 || cyf[x]>=BASE;x++) {
Res(x+2);
if(cyf[x]<0){LL i=(-cyf[x]-1)/BASE+1; cyf[x]+=i*BASE; cyf[x+1]-=i;}else
if(cyf[x]>=BASE){LL i=cyf[x]/BASE; cyf[x]-=i*BASE; cyf[x+1]+=i;}
}
len=max(len,x+1);
REDUCE();
}
// Od tego miejsca zaczyna sie implementacja operatorów. Przepisywanie tej
// czesci kodu nie jest wymagane - nalezy przepisywac tylko te operatory, z
// których sie korzysta. Niektóre operatory korzystaja z innych - w takich
// przypadkach, przy kazdym operatorze napisane jest, implementacji jakich
// operatorów on wymaga
// Ponizsze makro pozwala skrócic zapis nagłówków operatorów
#define OPER1(op) bool operator op (const BigNum &a) const
/* Operatory porownawcze */
OPER1(==) {
if(a.len!=len) return 0;
REP(x,len) if(cyf[x]!=a.cyf[x]) return 0;
return 1;
}
OPER1(<) {
if(len!=a.len) return len<a.len;
int x=len-1;
while(x && a.cyf[x]==cyf[x]) x--;
return cyf[x]<a.cyf[x];
}
OPER1(>) { return a<*this; } /* Wymaga < */
OPER1(<=) { return !(a<*this); } /* Wymaga < */
OPER1(>=) { return !(*this<a); } /* Wymaga < */
OPER1(!=) { return !(*this==a); } /* Wymaga == */
// Operacje dla liczb typu int
/* Operatory Bignum - Int */
BigNum &operator=(int a) {
REP(x,len) cyf[x]=0;
len=1; cyf[0]=a;
if (a>=BASE) przen(1);
return *this;
}
void operator+=(int a){cyf[0]+=a; przen(1);}
void operator-=(int a){cyf[0]-=a; przen(1);}
void operator*=(int a){REP(x,len) cyf[x]*=a; przen(len);}
int operator%(int a) {
LL w=0;
FORD(p,len-1,0) w=(w*BASE+cyf[p])%a;
return w;
}
// Operacje wyłacznie na liczbach typu BigNum
/* Operatory Bignum - Bignum */
#define OPER2(op) BigNum& operator op (const BigNum &a)
OPER2(+=) {
Res(a.len);
REP(x,a.len) cyf[x]+=a.cyf[x];
przen(a.len);
return *this;
}
OPER2(-=) {
REP(x,a.len) cyf[x]-=a.cyf[x];
przen(a.len);
return *this;
}
OPER2(*=) {
BigNum c(0,len+a.len);
REP(x,a.len) {
REP(y,len) c.cyf[y+x]+=cyf[y]*a.cyf[x];
c.przen(len+x);
}
*this=c;
return *this;
}
OPER2(=) {
Res(a.len);
FORD(x, len-1, a.len) cyf[x]=0;
REP(x,a.len) cyf[x]=a.cyf[x];
len=a.len;
return *this;
}
// Operatory słuzace do wczytywania i wypisywania liczb
// Funkcja przypisuje liczbie BigNum wartosc liczby z przekazanego wektora,
// zapisanej przy podstawie p
/* OPERATORY DO WCZYTYWANIA - WYPISYWANIA */
void read(const vector<int> &v,int p) { /* Wymaga += (int), *= (int) */
*this=0;
FORD(x,v.size()-1,0) {
*this *= p;
*this += v[x];
}
}
// Funkcja przypisuje liczbie BigNum wartosc liczby z napisu zapisanego przy
// podstawie 10
BigNum &operator=(string a) { /* Wymaga = (int) */
int s=a.length();
*this=0;
Res(len=s/BD+1);
REP(x,s) cyf[(s-x-1)/BD]=10*cyf[(s-x-1)/BD]+a[x]-'0';
REDUCE();
return *this;
}
// Funkcja wypisuje wartosc liczby BigNum zapisanej przy podstawie 10
void write() const {
printf("%d", int(cyf[len-1]));
FORD(x,len-2,0) printf("%0*d", BD, int(cyf[x]));
}
// Funkcja wypisuje do przekazanego bufora wartosc liczby zapisanej przy
// podstawie 10
void write(char *buf) const {
int p = sprintf(buf, "%d", int(cyf[len-1]));
FORD(x,len-2,0) p += sprintf(buf+p, "%0*d", BD, int(cyf[x]));
}
/* Inne operatory */
// Operator przesuniecia w prawo o n cyfr w prawo
BigNum &operator<<=(int ile) {
if(cyf[0]==0 && len==1) return *this;
Res(len+ile);
FORD(x,len-1,0) cyf[x+ile]=cyf[x];
REP(x,ile) cyf[x]=0;
len+=ile;
return *this;
}
// Operator przesuniecia w prawo o n cyfr w lewo
BigNum &operator>>=(int ile) {
if(ile>=len) ile=len;
REP(x,len-ile) cyf[x]=cyf[x+ile];
FOR(x,len-ile,ile) cyf[x]=0;
len-=ile;
if(len==0) len=1;
return *this;
}
BigNum sqrt() { /* Wymaga <, += (BigNum), *= (BigNum), <<= (int), + (BigNum), * (BigNum), << (int) */
int n=(len+1)/2;
BigNum a(0,n), sq;
FORD(i,n-1,0) {
int l=0, r=BASE-1;
while(l<r) {
int m=(l+r+1)/2;
if (*this < sq+(a*2*m<<i)+(BigNum(m)*m<<2*i))
r=m-1;
else
l=m;
}
sq+=(a*2*l<<i)+(BigNum(l)*l<<2*i);
a.cyf[i]=l; a.len=n;
}
return a;
}
// Makra pozwalajace na skrócenie zapisu nagłówków ponizszych operatorów
#define OPER3(op) BigNum operator op(const BigNum &a) const {BigNum w=*this; w op ## = a; return w; }
#define OPER4(op) BigNum operator op(int a) {BigNum w = *this; w op ## = a; return w; }
OPER3(+); /* Wymaga += (BigNum) */
OPER3(-); /* Wymaga -= (BigNum) */
OPER3(*); /* Wymaga *= (BigNum) */
OPER4(<<); /* Wymaga <<= (int) */
OPER4(>>); /* Wymaga >>= (int) */
};
Poniżej przykładowa implementacja klasy Integer (do dużych liczb całkowitych) wraz z komentarzami, którą można wykorzystać do implementacji zadań:
// Implementacja liczb całkowitych bazujaca na typie BigNum
int Signum(int x){return x>0?1:(x==0?0:-1);}
int Abs(int x){return x>=0?x:-x;}
struct Integer{
BigNum x;
int sgn; //Znak liczby: -1 dla ujemnych, 0 dla zera, 1 dla dodatnich
// Konstruktor, przyjmujacy jako parametry wartosc bezwzgledna oraz znak
// tworzonej liczby
Integer(const BigNum &a, const int &znak) {x = a; sgn = znak;}
Integer(const BigNum &a){x = BigNum(a); sgn = a > BigNum(0);}
// Konstruktor tworzacy zmienna równa liczbie a
Integer(const int &a = 0){x = BigNum(Abs(a)); sgn = Signum(a);}
// Operator zwraca liczbe o przeciwnym znaku
Integer operator- () const {return Integer(x, sgn*-1);}
// Operatory porównawcze
bool operator<(const Integer &b) const{
if (sgn != b.sgn) return sgn < b.sgn;
if (sgn == -1) return b.x < x;
return x < b.x;
}
bool operator==(const Integer &b) const{return sgn == b.sgn && x == b.x;}
// Makra pozwalajace na skrócenie zapisu nagłówków operatorów
#define OPER5(op) Integer operator op (const Integer &b) const
OPER5(-) {return *this + (-b);}
OPER5(+) {
if (sgn == -1) return -(-(*this) + (-b));
if (b.sgn >= 0) return Integer(x + b.x, min(1, sgn + b.sgn));
if (x < b.x) return Integer(b.x - x, -1);
return Integer(x - b.x, x > b.x);
}
OPER5(*){ return Integer(x*b.x, sgn*b.sgn);}
#define OPER6(op) Integer &operator op ## = (const Integer &b) {return *this = *this op b;}
OPER6(+)
OPER6(-)
OPER6(*)
// Funkcja wypisuje liczbe Integer zapisana przy podstawie 10 na
// standardowe wyjscie
void write() const{if (sgn==-1) printf("-"); x.write();}
};
Poniżej przykładowa implementacja klasy Frac do liczb wymiernych o dużych licznikach i mianownikach wraz z komentarzami, którą można wykorzystać do implementacji zadań:
BigNum NatNWD(const BigNum &a,const BigNum& b){return b==BigNum(0) ? a: NatNWD(b, a%b);}
struct Frac{
Integer a,b;
Frac(const Integer &aa=0,const Integer &bb=1){
a = aa; b = bb;
if(b<0) { a=-a; b=-b; }
Integer d = Integer(NatNWD(aa.x,bb.x));
a/=d; b/=d;
}
bool operator<(const Frac&x) const { return a*x.b < x.a*b;}
bool operator==(const Frac&x) const { return a == x.a && b == x.b;}
#define OPER7(op) Frac operator op (const Frac &x) const
OPER7(+){ return Frac(a*x.b+b*x.a,b*x.b); }
OPER7(-){ return Frac(a*x.b-b*x.a,b*x.b); }
OPER7(*){ return Frac(a*x.a,b*x.b); }
OPER7(/){ return Frac(a*x.b,b*x.a); }
bool isZero(){return a==Integer(0);}
void write(){a.write();printf("/");b.write();}
#define OPER8(op) Frac &operator op ## =(const Frac &b) {return *this = *this op b;}
OPER8(+)
OPER8(-)
OPER8(*)
OPER8(/)
};
Aby powyższe kody działały są niezbędne również nagłówki z tzw. biblioteczki UW:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define MP make_pair
#define FOR(v,p,k) for(int v=p;v<=k;++v)
#define FORD(v,p,k) for(int v=p;v>=k;--v)
#define REP(i,n) for(int i=0;i<(n);++i)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
#define ALL(c) c.begin(),c.end()