Загрузка...
Учебная работа. Реферат: Манипулирование с целыми числами произвольной длины
Манипулировани
е
с целыми числами случайной длины
Постановка задачки:
Составить набор процедур манипулирования с целыми числами случайной длины. Процедуры должны обеспечивать: формирование и ввод целых чисел случайной длины, сложение, вычитание, сопоставление и умножение целых чисел. Работоспособность процедур показать на демонстрационной программке.
Использованные средства языка:
Модуль, реализующий целые числа случайной длины, и тестовая программка написаны на языке С++.
Для представления целых чисел случайной длины определен класс UNLIM. Операции над этими числами реализованы методом переопределения для класса UNLIM последующих операций:
+ (унарный и бинарный)
— (унарный и бинарный)
*
==
!=
<
>
<=
>=
<< (операция вывода класса OSTREAM) .
структура данных:
Абсолютная величина числа случайной длины хранится в памяти в виде массива типа CHAR. В любом элементе массива может находится число от 0 до 99, другими словами два разряда всего числа. В нулевом элементе хранятся младшие два разряда, в крайнем элементе — старшие два разряда. Если число имеет нечетное количество разрядов, то в крайнем элементе массива хранится один крайний разряд, т.е. число от 0 до 9. Фаворитные нули в массиве не хранятся. Число 0 представлено массивом из 1-го элемента, в каком хранится 0.
С целью минимизировать копирование и расход памяти класс UNLIM реализован так, что на одно объект класса UNLIM состоит из поля SIGN — знака числа и поля PV — указателя на дескриптор представления абсолютной величины. Число 0 постоянно имеет символ PLUS.
Дескриптор представления абсолютной величины числа представляет собой объект структуры DESCRIPTOR и имеет последующие поля:
body — указатель на массив, в каком хранится количество ссылок на данное представление;
Реализация операций сопоставления:
Из операций сопоставления лишь < и != впрямую ассоциируют числа, другие операции выражены через эти две. При работе операций < и != поначалу проверяются знаки и длины чисел, и лишь в случае их совпадения делается поразрядное сопоставление чисел (в качестве разрядов тут берутся целые байты — т.е. разряды в системе счисления с основанием 100).
Реализация операций математики:
Операция унарный + просто возвращает само число.
Операция унарный — возвращает новейший объект класса UNLIM, который ссылается на то же символ, обратный знаку аргумента.
Операция бинарный + определена и для случаев, когда знаки операндов совпадают, и когда эти знаки различны.
В первом случае символ результата соответствует знаку 1-го (хоть какого) из операндов, а модуль результата является результатом сложения модулей операндов. При всем этом если количество разрядов первого операнда равно A, а второго — B, то количество разрядов операнда быть может или max(A,B), или max(A,B)+1, потому при выделении памяти под массив для модуля результата берется 2-ое случае утрата памяти на фаворитные нули быть может максимум 1 б, и прибыльнее сберечь на скорости, чем на памяти.
В случае, когда знаки операндов различны, символ результата равен знаку операнда с наибольшим модулем, а модуль результата получатся вычитанием модуля операнда с наименьшим модулем из модуля операнда с наибольшим модулем. При всем этом под модуль результата выделяется массив длины, равной большей из длин операндов, но опосля вычитания чисел он оптимизируется функцией optimize(), которая удаляет фаворитные нули (делает новейший массив длины, нужной для хранения модуля числа без фаворитных нулей, копирует в него все значащие разряды, переадресовывает ссылку дескриптора на этот массив и удаляет старенькый массив).
Сложение и вычитание модулей аргументов делается в системе счисления с основанием 100.
Операция бинарный — определена через унарный минус и бинарный плюс.
Операция * делается по технологии, аналогичной умножению в столбик. При всем этом все деяния ведутся в системе счисления с основанием 100. Длина массива результата быть может равна или сумме длин операндов, или данной сумме минус 1. Эта ситуация подобна той, которая была при сложении чисел с схожим знаком, и тут тоже не делается оптимизации.
Операция << — просто операция вывода класса OSTREAM, определенная для класса UNLIM. Поначалу она выводитactiveXесли символ числа отрицательный, а потом само число поразрядно (по десятичным разрядам), начиная со старшего. При всем этом употребляется функция digit(number), которая возвращает
Функция- конструктор unlim(char*) обрабатывает инициализацию символьной строчкой. При всем этом распознаются последующие неверные ситуации: инициализация пустой строчкой; недопустимый знак в строке; строчка содержит символ, но не содержит значения. Во всех этих вариантах число инициализируется нулем.
Функция- конструктор unlim(unlim&) обрабатывает инициализацию иным объектом класса UNLIM.
отчет испытательной программки
Проверка работы конструкторов:
Без инициализации:
unlim a;
a=0
инициализация строчкой:
unlim b=»123″
b=123
unlim c=»-123″
c=-123
unlim d=»+123″
d=123
unlim e=»+» Unlim class error: Sign without value. Value=0
e=0
unlim f=»-» Unlim class error: Sign without value. Value=0
f=0
unlim g=»aaa» Unlim class error: Not digit symbol in string. String ignored. Value=0
g=0
unlim h=»4a123″ Unlim class error: Not digit symbol in string. String ignored. Value=0
h=0
Проверка вывода, математики и сопоставления:
Введено:
a=123
b=45
Итог:
a=123
b=45
a=-123 +a=123
a>b a>=b a!=b
a+b=168 a-b=78 a*b=5535
Введено:
a=+0000000000000000123
b=0000000000000000000000000000000045
Итог:
a=123
b=45
a=-123 +a=123
a>b a>=b a!=b
a+b=168 a-b=78 a*b=5535
Введено:
a=-123
b=-45
Итог:
a=-123
b=-45
a=123 +a=-123
a<b a<=b a!=b
a+b=-168 a-b=-78 a*b=5535
Введено:
a=123
b=-45
Итог:
a=123
b=-45
a=-123 +a=123
a>b a>=b a!=b
a+b=78 a-b=168 a*b=-5535
Введено:
a=-123
b=45
Итог:
a=-123
b=45
a=123 +a=-123
a<b a<=b a!=b
a+b=-78 a-b=-168 a*b=-5535
Введено:
a=1000000000000000000000000000000000000000000000
b=999999999999999999999999999999999999999999999
Итог:
a=1000000000000000000000000000000000000000000000
b=999999999999999999999999999999999999999999999
a=-1000000000000000000000000000000000000000000000 +a=1000000000000000000000000000000000000000000000
a>b a>=b a!=b
a+b=1999999999999999999999999999999999999999999999 a-b=1 a*b=999999999999999999999999999999999999999999999000000000000000000000000000000000000000000000
Введено:
a=-100000000000000000000000000000000000000000000
b=999999999999999999999999999999999999999999999
Итог:
a=-100000000000000000000000000000000000000000000
b=999999999999999999999999999999999999999999999
a=100000000000000000000000000000000000000000000 +a=-100000000000000000000000000000000000000000000
a<b a<=b a!=b
a+b=899999999999999999999999999999999999999999999 a-b=-1099999999999999999999999999999999999999999999 a*b=-99999999999999999999999999999999999999999999900000000000000000000000000000000000000000000
Введено:
a=+00000000000000
b=-00000000000000
Итог:
a=0
b=0
a=0 +a=0
a<=b a>=b a==b
a+b=0 a-b=0 a*b=0
programm1;
//#include <string.h>
#include <iostream.h>
#include <fstream.h>
//#include <values.h>
#include «unlimit.h»
#define CR «n»
void main()
{
ofstream r(«report.txt»,1);
ostream_withassign rc;
rc=cout;
cout<<«nТестовая программка для класса UNLIMn»
<<«(целые числа с случайной точностью)n»
;
cout=r;
r <<«отчет испытательной программыn»
<<«nПроверка работы конструкторов:n»
<<» Без инициализации:n»
;
r <<» unlim a;n»;
unlim a;
r <<» a=»<<a<<«n»
<<» инициализация строчкой:n»
<<» unlim b=»123″n»;
unlim b=»123″;
r <<» b=»<<b<<CR
<<» unlim c=»-123″n»;
unlim c=»-123″;
r <<» c=»<<c<<CR
<<» unlim d=»+123″n»;
unlim d=»+123″;
r <<» d=»<<d<<CR
<<» unlim e=»+»n»;
unlim e=»+»;
r <<» e=»<<e<<CR
<<» unlim f=»-«n»;
unlim f=»-«;
r <<» f=»<<f<<CR
<<» unlim g=»aaa»n»;
unlim g=»aaa»;
r <<» g=»<<g<<CR
<<» unlim h=»4a123″n»;
unlim h=»4a123″;
r <<» h=»<<h<<«nn»
<<«Проверка вывода, математики и сопоставления:nn»;
while ( a!=»0″ || b!=»0″ )
{
cout=rc;
cout<<«nВводите одно за иным 2 числа; для окончания — оба нулиn»;
char
aa[128],
bb[128];
cout<<» a=»;
cin >>aa;
cout<<» b=»;
cin >>bb;
cout=r;
r <<«Введено:n»
<<» a=»<<aa<<CR
<<» b=»<<bb<<CR
<<«nРезультат:n»
;
a=aa;
b=bb;
r <<» a=»<<a<<CR<<» b=»<<b<<«nn»
<<«-a=»<<-a<<CR<<«+a=»<<+a<<«nn»;
if (a<b) r<<«a<b «;
if (a>b) r<<«a>b «;
if (a<=b) r<<«a<=b «;
if (a>=b) r<<«a>=b «;
if (a!=b) r<<«a!=bn»;
if (a==b) r<<«a==bn»;
r <<«na+b=»<<(a+b)<<CR
<<«a-b=»<<(a-b)<<CR
<<«a*b=»<<(a*b)
<<«nn—————————————————nn»
;
}
}
programm2;
#define COUNT unsigned int
#define TRUE 1
#define FALSE 0
#define ILLEGAL 10
enum
{
PLUS,
MINUS
};
extern class unlim
{
public:
unlim(char*);
unlim();
unlim(unlim&);
~unlim();
unlim
&operator = (char*),
&operator = (unlim&);
friend int
operator == (unlim&,unlim&),
operator != (unlim&,unlim&),
operator > (unlim&,unlim&),
operator >= (unlim&,unlim&),
operator < (unlim&,unlim&),
operator <= (unlim&,unlim&);
friend unlim
operator + (unlim&), // unary
operator — (unlim&), // unary
operator + (unlim&,unlim&), // binary
operator — (unlim&,unlim&), // binary
operator * (unlim&,unlim&),
абс(unlim&);
friend ostream
&operator << (ostream&,unlim&);
private:
struct descriptor
{
char
*body;
COUNT
len,
HowMany;
};
descriptor
*pv; //pointer to value descriptor
char
sign,
digit(COUNT number);
char
&operator [](COUNT i) {return pv->body[i];}
void
init0(), //init by zero
NotDigit(), //Message «no digit» & init0
optimize(), //optimize length of body
error(char*); //display error Message
};
inline int operator ==(unlim &a,unlim &b)
{
return !(a!=b);
}
inline int operator <=(unlim &a,unlim &b)
!(a!=b);
inline int operator >=(unlim &a,unlim &b)
{
return !(a<b);
}
inline int operator >(unlim &a,unlim &b)
{
return !(a<b) && (a!=b);
}
inline unlim operator +(unlim &x)
{
return x;
}
programm3;
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <iostream.h>
#define COUNT unsigned int
#define TRUE 1
#define FALSE 0
#define ILLEGAL 10
enum
{
PLUS,
MINUS
};
class unlim
{
public:
unlim(char*);
unlim();
unlim(unlim&);
~unlim();
unlim
&operator = (char*),
&operator = (unlim&);
friend int
operator == (unlim&,unlim&),
operator != (unlim&,unlim&),
operator > (unlim&,unlim&),
operator >= (unlim&,unlim&),
operator < (unlim&,unlim&),
operator <= (unlim&,unlim&);
friend unlim
operator + (unlim&), // unary
operator — (unlim&), // unary
operator + (unlim&,unlim&), // binary
operator — (unlim&,unlim&), // binary
operator * (unlim&,unlim&),
абс(unlim&);
friend ostream
&operator << (ostream&,unlim&);
private:
struct descriptor
{
char
*body;
COUNT
len,
HowMany;
};
descriptor
*pv; //pointer to value descriptor
char
sign,
digit(COUNT number);
char &operator [](COUNT i) {return pv->body[i];}
void
init0(), //init by zero
NotDigit(), //Message «no digit» & init0
optimize(), //optimize length of body
error(char*); //display error Message
};
inline void unlim::error(char *Message)
{
cout <<«Unlim class error: «
<<Message
<<«n»;
}
void unlim::init0()
{
(pv->body)=new char;
*(pv->body)=0;
(pv->len)=1;
sign=PLUS;
}
char unlim::digit(COUNT number)
{
if ( number>=(pv->len) )
return ILLEGAL;
char byte=(pv->body)[number/2];
if (number%2==0)
return byte%10;
else
return byte/10;
}
unlim::unlim()
{
pv=new descriptor;
init0();
(pv->HowMany)=1;
}
unlim::~unlim()
{
if ( —(pv->HowMany)==0 )
{
delete pv->body;
delete pv;
}
}
char DecVal(char symbol)
{
if ( isdigit(symbol) )
return symbol-‘0’;
return ILLEGAL;
}
unlim::unlim(char *string)
{
pv=new descriptor;
(pv->HowMany)=1;
COUNT Length=strlen(string);
if (Length==0)
{
error(«Empty string assigned. Value=0»);
init0();
return;
}
else
{
COUNT LeftLimit=0;
switch (string[0])
{
case ‘-‘:
sign=MINUS;
LeftLimit=1;
break;
case ‘+’:
LeftLimit=1;
default:
sign=PLUS;
}
if (Length-LeftLimit==0)
{
error(«Sign without value. Value=0»);
init0();
return;
}
else
{
while (string[LeftLimit]==’0′)
LeftLimit++;
if ( (Length-=LeftLimit)==0 )
{
init0();
return;
}
COUNT DestLength=Length/2+Length%2;
(pv->body)=new char[DestLength];
for ( COUNT si=Length+LeftLimit-1, ki=0 ; ki<DestLength ; si-=2,ki++ )
{
char a=DecVal(string[si]);
if (a==ILLEGAL)
{
NotDigit();
return;
}
(pv->body)[ki]=a;
if (si!=LeftLimit)
{
char a=DecVal(string[si-1]);
if (a==ILLEGAL)
{
NotDigit();
return;
}
(pv->body)[ki]+=10*a;
}
}
(pv->len)=Length;
}
}
}
void unlim::NotDigit()
{
error(«Not digit symbol in string. String ignored. Value=0»);
delete pv->body;
init0();
}
unlim::unlim(unlim &arg)
{
(arg.pv)->HowMany++;
pv=arg.pv;
sign=arg.sign;
}
unlim &unlim::operator=(unlim &arg)
{
(arg.pv)->HowMany++;
if ( —(pv->HowMany)==0 )
{
delete pv->body;
delete pv;
}
pv=arg.pv;
sign=arg.sign;
return *this;
}
unlim &unlim::operator=(char *string)
{
return *this=unlim(string);
}
ostream &operator<<(ostream &s,unlim &x)
{
if (x.sign==MINUS)
s << «-«;
for ( COUNT i=((x.pv)->len) ; i>0 ; i— )
s << int(x.digit(i-1));
return s;
}
int operator!=(unlim &a,unlim &b)
{
if ( (a.pv)->len != (b.pv)->len)
return TRUE;
if (a.sign!=b.sign)
return TRUE;
COUNT length=((a.pv)->len)/2+((a.pv)->len)%2;
for ( COUNT i=0 ; i<length ; i++ )
if (a[i]!=b[i])
return TRUE;
return FALSE;
}
int operator<(unlim &a,unlim &b)
{
if (a.sign!=b.sign)
return a.sign==MINUS;
if ( (a.pv)->len == (b.pv)->len )
{
COUNT i=((a.pv)->len)-1;
while ( a.digit(i) == b.digit(i) )
{
if (i==0)
return FALSE;
i—;
}
char
aLess= a.digit(i) < b.digit(i),
SignPlus= a.sign==PLUS;
return ( aLess && SignPlus) || ( !aLess && !SignPlus );
}
else
( !aShort && !SignPlus );
}
inline int operator ==(unlim &a,unlim &b)
{
return !(a!=b);
}
inline int operator <=(unlim &a,unlim &b)
!(a!=b);
inline int operator >=(unlim &a,unlim &b)
{
return !(a<b);
}
inline int operator >(unlim &a,unlim &b)
{
return !(a<b) && (a!=b);
}
inline unlim operator +(unlim &x)
{
return x;
}
unlim абс(unlim &x)
{
unlim r=x;
r.sign=PLUS;
return r;
}
unlim operator -(unlim &x)
{
if ( (x.pv)->len==1 && x[0]==0 )
{
unlim y;
return y;
}
unlim y=x;
if (x.sign==PLUS)
y.sign=MINUS;
else
y.sign=PLUS;
return y;
}
void unlim::optimize()
{
COUNT i=pv->len/2+pv->len%2-1;
char optimized=FALSE;
while (pv->body[i]==0)
{
optimized=TRUE;
if (i—==0)
{
init0();
return;
}
}
if (optimized)
{
char *NewBody=new char[++i];
for (COUNT ni=0;ni<i;ni++)
NewBody[ni]=pv->body[ni];
delete pv->body;
pv->body=NewBody;
pv->len=(i—)*2;
}
if ( (pv->body[i]/10)==0 && (pv->len%2)==0 )
pv->len—;
}
inline COUNT max (COUNT a,COUNT b)
{
return (a>b)?a:b;
}
unlim operator +(unlim &a,unlim &b)
{
unlim r;
delete (r.pv)->body;
if (a.sign==b.sign)
{
r.sign=a.sign;
COUNT
rlen=max( (a.pv)->len,(b.pv)->len )+1,
alen=(a.pv)->len/2+(a.pv)->len%2,
blen=(b.pv)->len/2+(b.pv)->len%2;
(r.pv)->len=rlen;
rlen=rlen/2+rlen%2;
(r.pv)->body=new char[rlen];
*(r.pv)->body=0;
for (COUNT i=0;i<rlen;i++)
{
unsigned char sum=( i<alen ? a[i] : 0)+( i<blen ? b[i] : 0);
r[i]+=sum%100;
r[i+1]=sum/100;
}
if ( r.digit( (r.pv)->len-1 )==0 )
(r.pv)->len—;
}
else
{
unlim
aa=a,
bb=b;
if (абс(a)<абс(b))
{
aa=b;
bb=a;
}
r.sign=aa.sign;
COUNT
rlen=(aa.pv)->len,
blen=(bb.pv)->len/2+(bb.pv)->len%2;
(r.pv)->len=rlen;
rlen=rlen/2+rlen%2;
(r.pv)->body=new char[rlen];
*(r.pv)->body=0;
for (COUNT i=0;i<rlen;i++)
{
char sub=aa[i]-( i<blen ? bb[i] : 0 )+r[i];
if (sub<0)
{
r[i+1]=-1;
sub+=100;
}
else
r[i+1]=0;
r[i]=sub;
}
r.optimize();
}
return r;
}
unlim operator -(unlim &a,unlim &b)
{
return a+(-b);
}
unlim operator *(unlim &a,unlim &b)
{
unlim r;
delete (r.pv)->body;
if (a.sign==b.sign)
r.sign=PLUS;
else
r.sign=MINUS;
COUNT
rlen=(a.pv)->len+(b.pv)->len,
alen=(a.pv)->len/2+(a.pv)->len%2,
blen=(b.pv)->len/2+(b.pv)->len%2;
(r.pv)->len=rlen;
rlen=rlen/2+rlen%2;
(r.pv)->body=new char[rlen];
COUNT i;
for (i=0;i<rlen;i++)
r[i]=0;
for (i=0;i<alen;i++)
{
unsigned int
next=0,
mul;
for(COUNT j=0;j<blen;j++)
{
next+=r[i+j];
mul=a[i]*b[j]+next;
r[i+j]=mul%100;
next=mul/100;
}
r[i+blen]=next;
}
if ( r.digit((r.pv)->len-1)==0 )
(r.pv)->len—;
if ( r.digit((r.pv)->len-1)==0 )
r.init0();
return r;
}
]]>