Главная » Каталог    
рефераты Разделы рефераты
рефераты
рефератыГлавная

рефератыБиология

рефератыБухгалтерский учет и аудит

рефератыВоенная кафедра

рефератыГеография

рефератыГеология

рефератыГрафология

рефератыДеньги и кредит

рефератыЕстествознание

рефератыЗоология

рефератыИнвестиции

рефератыИностранные языки

рефератыИскусство

рефератыИстория

рефератыКартография

рефератыКомпьютерные сети

рефератыКомпьютеры ЭВМ

рефератыКосметология

рефератыКультурология

рефератыЛитература

рефератыМаркетинг

рефератыМатематика

рефератыМашиностроение

рефератыМедицина

рефератыМенеджмент

рефератыМузыка

рефератыНаука и техника

рефератыПедагогика

рефератыПраво

рефератыПромышленность производство

рефератыРадиоэлектроника

рефератыРеклама

рефератыРефераты по геологии

рефератыМедицинские наукам

рефератыУправление

рефератыФизика

рефератыФилософия

рефератыФинансы

рефератыФотография

рефератыХимия

рефератыЭкономика

рефераты
рефераты Информация рефераты
рефераты
рефераты

Набор процедур манипулирования с целыми числами произвольной длины


Отчет тестовой программы
Проверка работы конструкторов: Без инициализации: 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=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=1999999999999999999999999999999999999999999999
a-b=1
a*b=999999999999999999999999999999999999999999999000000000000000000000000000000000000000000000
--------------------------------------------------
Введено: a=-100000000000000000000000000000000000000000000 b=999999999999999999999999999999999999999999999
Результат: a=-100000000000000000000000000000000000000000000 b=999999999999999999999999999999999999999999999
-a=100000000000000000000000000000000000000000000
+a=-100000000000000000000000000000000000000000000
a
МОСКОВСКИЙ ИНСТИТУТ
РАДИОТЕХНИКИ ЭЛЕКТРОНИКИ И АВТОМАТИКИ МЕЖДУНАРОДНЫЙ ФАКУЛЬТЕТ ИНФОРМАТИКИ
ИНТЕР ЭВМ
К У Р С О В
А Я   Р А Б О Т А
по
дисциплине "Алгоритмические Языки и Программирование"
Студент Мозолев А. В.    Группа
МФ-3-91
Преподаватель Моисеев В.М.
Москва 1993г
Постановка задачи:
Составить набор процедур
манипулирования с целыми числами произвольной длины. Процедуры должны
обеспечивать: формирование и ввод целых чисел произвольной длины, сложение,
вычитание, сравнение и умножение целых чисел. Работоспособность процедур
продемонстрировать на демонстрационной программе.
Использованные средства языка:
Модуль, реализующий целые
числа произвольной длины, и тестовая программа написаны на языке С++.
Для представления целых
чисел произвольной длины определен класс UNLIM. Операции над этими числами
реализованы путем переопределения для класса UNLIM следующих операций:
+ (унарный и бинарный)
- (унарный и бинарный)
*
==
!=
<
>
<=
>=
<< (операция вывода класса OSTREAM)
Структура данных:
Абсолютная величина числа
произвольной длины хранится в памяти в виде массива типа CHAR. В каждом
элементе массива может находится число от 0 до 99, то есть два разряда всего
числа. В нулевом элементе хранятся младшие два разряда, в последнем элементе -
старшие два разряда. Если число имеет нечетное количество разрядов, то в
последнем элементе массива хранится один последний разряд, т.е. число от 0 до
9. Лидирующие нули в массиве не хранятся. Число 0
представлено массивом из одного элемента, в котором хранится
0.
С целью минимизировать
копирование и расход памяти класс UNLIM реализован так, что на одно
представление абсолютной величины могут ссылаться несколько чисел, при этом
ведется учет ссылок.
Объект класса UNLIM
состоит из поля SIGN - знака числа и поля PV - указателя на дескриптор
представления абсолютной величины. Число 0 всегда имеет знак PLUS.
Дескриптор представления
абсолютной величины числа представляет собой объект структуры DESCRIPTOR и
имеет следующие поля:
body    -
указатель на  массив,   в  
котором   хранится
представление абсолютной величины числа;
len               - длина массива body[] в байтах;
HowMany - количество ссылок на данное представление;
Реализация операций сравнения:
Из операций сравнения
только < и != напрямую сравнивают числа, остальные операции выражены через
эти две. При работе операций < и != сначала проверяются знаки и длины чисел,
и только в случае их совпадения производится поразрядное сравнение чисел (в
качестве разрядов здесь берутся целые байты - т.е. разряды в системе счисления
с основанием 100).
Реализация операций арифметики:
Операция унарный + просто возвращает само число.
Операция унарный - возвращает новый объект класса
UNLIM, который ссылается на то же представление модуля числа, что и аргумент, и
имеет знак, противоположный знаку аргумента.
Операция бинарный +
определена и для случаев, когда знаки операндов совпадают, и когда эти знаки
различны.
В первом случае знак
результата соответствует знаку одного (любого) из операндов, а модуль
результата является результатом сложения модулей операндов. При этом если
количество разрядов первого операнда равно A, а второго - B, то количество
разрядов операнда может быть либо max(A,B), либо max(A,B)+1, поэтому при
выделении памяти под массив для модуля результата берется второе значение.
Никакой оптимизации этого массива после сложения модулей операндов не делается,
так как в данном случае потеря памяти на лидирующие нули может быть максимум 1
байт, и выгоднее сэкономить на скорости, чем на памяти.
В случае, когда знаки
операндов различны, знак результата равен знаку операнда с максимальным
модулем, а модуль результата получатся вычитанием модуля операнда с минимальным
модулем из модуля операнда с максимальным модулем. При этом под модуль
результата выделяется массив длины, равной наибольшей из длин операндов, но
после вычитания чисел он оптимизируется функцией optimize(), которая удаляет
лидирующие нули (создает новый массив длины, необходимой для хранения модуля
числа без лидирующих нулей, копирует в него все значащие разряды,
переадресовывает ссылку дескриптора на этот массив и удаляет старый массив).
Сложение и вычитание
модулей аргументов производится в системе счисления с основанием 100.
Операция бинарный -
определена через унарный минус и бинарный плюс.
Операция * производится по
технологии, аналогичной умножению в столбик. При этом все действия ведутся в
системе счисления с основанием 100. Длина массива результата может быть равна
либо сумме длин операндов, либо этой сумме минус
1. Эта ситуация аналогична той, которая была при
сложении чисел с одинаковым знаком, и здесь тоже не делается оптимизации.
Операция << - просто
операция вывода класса OSTREAM, определенная для класса UNLIM. Сначала она
выводит '-' если знак числа отрицательный, а затем само число поразрядно (по
десятичным разрядам), начиная со старшего. При этом используется функция
digit(number), которая возвращает значение десятичного разряда с номером
number.
Функция- конструктор                        unlim(char*)                         обрабатывает
инициализацию 
символьной  строкой.  При 
этом  распознаются
следующие ошибочные ситуации:  инициализация пустой строкой;
недопустимый 
символ в строке;  строка содержит
знак,  но не
содержит  
значения.   Во   всех   
этих    случаях    число
инициализируется нулем.
Функция- конструктор                      unlim(unlim&)                         обрабатывает
инициализацию другим объектом класса UNLIM.
//#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Тестовая программа для
класса UNLIM\n"
            <<"(целые числа с
произвольной точностью)\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<<"\n\n"
            <<"Проверка вывода,
арифметики и сравнения:\n\n";
      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<<"\n\n"
                  <<"-a="<<-a<<CR<<"+a="<<+a<<"\n\n";
            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!=b\n";
            if (a==b)
r<<"a==b\n";
            r     <<"\na+b="<<(a+b)<<CR
                  <<"a-b="<<(a-b)<<CR
                  <<"a*b="<<(a*b)
                  <<"\n\n--------------------------------------------------\n\n"
                  ;
            }
      }
#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&),
                  abs(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
                        char

      }
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
abs(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 (abs(a)<abs(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;
      }
#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&),
                  abs(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;
      }
рефераты Рекомендуем рефератырефераты

     
Рефераты @2011