Отправляет email-рассылки с помощью сервиса Sendsay

Легкое решение задач по математике и физике!

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 261 RSS
←   Апрель 2007   →
 1
 2
 3
 4
 5
 6
 7
 8
08.04.2007
11:36:47
11:46:59
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://www.help-studia.ru
Открыта: 05-11-2006

Автор
help-studia

Статистика

261 подписчиков
0 за неделю
←   Все выпуски   →

Легкое решение задач по математике и физике! Третье отличие С от С++



  2005-2007 Учебный физико-математический студенческий центр

Легкое решение задач по математике и физике! #9

       
 

Здравствуйте, уважаемые наши подписчики!
Главная
О нашей работе
Регистрация заказа
Запись на  курсы ЕГЭ
Стоимость работы
Способы оплаты
Обратная связь

 
Подпишитесь на нашу рассылку на Subscribe.Ru
Легкое решение задач по математике и физике!
 

logo 




Представляю Вам 9-ый выпуск рассылки.

Сегодня Мы рассмотрим третье отличие С от С++.


Третье отличие С от С++
   предпочитайте new и delete вместо malloc и free

 Причины отказа от malloc, free на самом деле очень простые. Они ничего не знают о конструкторах и деструкторах.

Рассмотрим следующие два способа выделения памяти для массива из 10-ти строк string.

string *stringArray1 =
  static_cast<string*>(malloc(10 * sizeof(string)));

string *stringArray2 = new string[10];

Здесь stringArray1 указывает на память под 10 элементов строк, но в этой памяти не сконструировано никаких объектов. Иными словами, stringArray1 полность бесполезен. Напротив, stringArray2 указывает на 10 полностью сконструированных объектов и каждый из них может принимать участие в любых операциях со строками.
Едем дальше. Допустим, Вам каким-то магическим способом удалось построить эти 10 строк. Но дальше в программе Вам понадобится выполнить следующий код:


free(stringArray1);
// или:

delete [] stringArray2;
 
Вызов функции free уничтожит память под все 10 объектов, но не вызовет ни одного  деструктора для этих объектов. То есть все десять строк по прежнему будут "висеть" в памяти. Хорошо? Не очень! С другой стороны, delete уничтожая память где лежат объекты, уничтожит и сами объекты, вызывая у них деструкторы.

new, delete так устроены, что взаимодействуют с конструкторами и деструкторами. Они являются наиболее правильным и безопасным выбором!

Не стоит также смешивать использование new, delete с malloc, free. Совместное их использование может приводить к совершенно непредсказуемым ситациям. Не нужно напрашиваться на неприятности, используя для выделения памяти malloc и delete для уничтожения.


Для завершения рассылки приведём небольшую задачку, типичную для курсовых работ математических факультетов!
Требуется создать класс больших чисел. В нём должны быть операции сложения, вычитания и умножения. Число должно иметь произвольную длину и произвольное основание системы счисления.

Код:

// отключаем ненужные предупреждения
#pragma warn -inl
#pragma warn -lvc

// подключаем необходимые системные библиотеки
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

// класс больших чисел
class HugeInt {
 public:
   long Size; // Size - текущая длина
   short Coef[SizeMax]; // Массив коэффициентов
   // цифры хранятся в обратном порядке. Это - некая "заготовка на будущее": дело в том,
   // что реализации алгоритмов при этом имеют более естественный вид.

   HugeInt();
   HugeInt(const HugeInt&);
   ~HugeInt() {};

   void zero(); // Обнулить число

   HugeInt& operator=(const HugeInt&);

   HugeInt operator+(const HugeInt &B);
   HugeInt operator-(const HugeInt &B);
   HugeInt operator*(const HugeInt &B);
   HugeInt operator/(HugeInt &B);

   short operator==(const HugeInt&);
   short operator!=(const HugeInt&);
   short operator<(const HugeInt&);
   short operator>(const HugeInt&);
   short operator<=(const HugeInt&);
   short operator>=(const HugeInt&);

   short isZero(); // проверить число на ноль

   void input(char*); // для ввода
   void output(); // для вывода
};

// Объявление вида HugeInt A;
// Создается полностью пустое число
HugeInt::HugeInt()
{
   Size = 0;
}
// Конструктор копирования
// Создает число, равное A
HugeInt::HugeInt(const HugeInt &A)
{
   Size = A.Size;
   for(int i=0; i<SizeMax; i++) Coef[i] = A.Coef[i];
}

// A.zero() - обнулить число
void HugeInt::zero()
{
   for(int i=0; i<SizeMax; i++) Coef[i]=0;
   Size=1;
}

HugeInt& HugeInt::operator=(const HugeInt &A)
{
   if (this == &A) return *this; // Если присваивание вида A=A - выйти
   zero();
   Size = A.Size;
   for(int l=0; l<Size; l++)
      Coef[l] = A.Coef[l];
   return *this;
}

// 1 - да, "истина"
// 0 - нет, "ложь"
short HugeInt::operator==(const HugeInt &A)
{
   short ret = 1;
   for (int i=0; i<Size; i++)
      if (Coef[i]!=A.Coef[i]) {
    ret = 0;
         break;
      }
   return ret;
}

short HugeInt::operator!=(const HugeInt &A)
{
   short ret = 1;
   if (*this==A) ret = 0;
   return ret;
}

short HugeInt::operator<(const HugeInt &A)
{
   short ret = 0;
   if (Size<A.Size) ret = 1;
   if (Size==A.Size) {
      for (int i=Size-1; i>=0; i--) {
         if (Coef[i]<A.Coef[i]) {
            ret = 1;
            break;
    }
         if (Coef[i]>A.Coef[i]) {
            ret = 0;
            break;
    }
      }
   }
   return ret;
}

short HugeInt::operator>(const HugeInt &A)
{
   short ret = 0;
   if (Size>A.Size) ret = 1;
   if (Size==A.Size) {
      for (int i=Size-1; i>=0; i--) {
         if (Coef[i]>A.Coef[i]) {
       ret = 1;
            break;
         }
         if (Coef[i]<A.Coef[i]) {
            ret = 0;
            break;
         }
      }
   }
   return ret;
}

short HugeInt::operator<=(const HugeInt &A)
{
   short ret = 0;
   if ((*this == A) || (*this < A)) ret = 1;
   return ret;
}

short HugeInt::operator>=(const HugeInt &A)
{
   short ret = 0;
   if ((*this == A) || (*this > A)) ret = 1;
   return ret;
}

// проверить число на ноль
short HugeInt::isZero()
{
   short ret=0;
   HugeInt Zero(*this); Zero.zero();
   if (Zero==*this) ret = 1;
   return ret;
}

// Схема для сложения очень проста: складываем цифры слева направо(цифры хранятся в обратном
// порядке). Если зафиксировано переполнение (т.е при сложении получена цифра, большая
// максимально возможной в данной системе счисления), то происходит "перенос"(carry) в следующий разряд.
HugeInt HugeInt::operator+(const HugeInt &B)
{
   // C = A + B
   HugeInt A(*this);
   HugeInt C; // максимальный размер C должен быть достаточен для хранения суммы

   int i;
   long temp; // temp здесь и далее играет роль "временной" цифры,
              // до выполнения переноса. Возможно, temp > BASE.

   const short *a=A.Coef, *b=B.Coef;
   short *c=C.Coef, carry = 0;

   // Складываем два числа, i - номер текущей цифры
   if (B.Size <= A.Size) {
      // если B.Size <= A.Size.
      for (i=0; i<B.Size; i++) {
         temp = a[i] + b[i] + carry;
         if (temp >= BASE) { // переполнение. Перенести единицу.
            c[i] = temp - BASE;
            carry = 1;
         } else {
            c[i] = temp;
       carry = 0;
         }
      }

      // Меньшее число кончилось
      for (; i < A.Size; i++) {
         temp = a[i] + carry;
         if (temp >= BASE) {
            c[i] = temp - BASE;
       carry = 1;
         } else {
            c[i] = temp;
            carry = 0;
    }
      }

      // Если остался перенос - добавить его в дополнительный разряд
      if (carry) {
         c[i] = carry;
         C.Size = A.Size+1;
      }
      else C.Size = A.Size;
   } else {
      // если A.Size <= B.Size.
      for (i=0; i<A.Size; i++) {
         temp = a[i] + b[i] + carry;
    if (temp >= BASE) { // переполнение. Перенести единицу.
            c[i] = temp - BASE;
            carry = 1;
         } else {
            c[i] = temp;
            carry = 0;
         }
      }

      // Меньшее число кончилось
      for (; i < B.Size; i++) {
         temp = b[i] + carry;
         if (temp >= BASE) {
       c[i] = temp - BASE;
            carry = 1;
         } else {
            c[i] = temp;
            carry = 0;
         }
      }

      // Если остался перенос - добавить его в дополнительный разряд
      if (carry) {
         c[i] = carry;
         C.Size = B.Size+1;
      }
      else C.Size = B.Size;
   }
   return C;
}

// Вычитание осуществляется аналогично, с той лишь разницей, что осуществляется перенос
// "заимствования". Мы работаем с положительными числами, поэтому если вычитаемое большое по размеру - происходит выход.
HugeInt HugeInt::operator-(const HugeInt &B)
{
   // C = A - B
   HugeInt A(*this);
   HugeInt C;

   int i;
   long temp, carry=0;

   // A должно быть больше B, так как мы работаем с неотриц. целыми
   if ( A >= B ) {
      const short *a=A.Coef, *b=B.Coef;
      short *c=C.Coef;

      for (i=0; i<B.Size; i++) {
         temp = a[i] - b[i] + carry;
         if (temp < 0) {
            c[i] = temp + BASE;
            carry = -1;
    } else {
            c[i] = temp;
            carry = 0;
         }
      }

      for (; i<A.Size; i++) {
         temp = a[i] + carry;
         if (temp < 0) {
            c[i] = temp + BASE;
            carry = -1;
         } else {
            c[i] = temp;
            carry = 0;
         }
      }

      // Размер результата может быть гораздо меньше, чем у исходного числа
      // Устанавливаем его по первому положительному разряду
      i = A.Size-1;
      while ( (i>0) && (c[i]==0) ) i--;
      C.Size = i+1;
   } else {
      const short *a=B.Coef, *b=A.Coef;
      short *c=C.Coef;

      for (i=0; i<A.Size; i++) {
         temp = a[i] - b[i] + carry;
         if (temp < 0) {
            c[i] = temp + BASE;
            carry = -1;
         } else {
            c[i] = temp;
            carry = 0;
         }
      }

      for (; i<B.Size; i++) {
         temp = a[i] + carry;
         if (temp < 0) {
            c[i] = temp + BASE;
            carry = -1;
         } else {
            c[i] = temp;
            carry = 0;
         }
      }

      // Размер результата может быть гораздо меньше, чем у исходного числа
      // Устанавливаем его по первому положительному разряду
      i = B.Size-1;
      while ( (i>0) && (c[i]==0) ) i--;
      C.Size = i+1;
   }
   return C;
}

HugeInt HugeInt::operator*(const HugeInt &B)
{
   // C = A * B
   HugeInt A(*this);
   HugeInt C; // максимальный размер C должен быть достаточен для хранения произведения

   int i, j;
   const short *a=A.Coef, *b=B.Coef;
   short *c=C.Coef;
   long temp, carry;

   // Обнулить необходимую для работы часть C
   for ( i=0; i <= A.Size+B.Size; i++ ) c[i]=0;
   for ( i = 0; i < A.Size; i++) {
      carry = 0;
      // вычисление временного результата с одновременным прибавлением
      // его к c[i+j] (делаются переносы)
      for (j = 0; j < B.Size; j++) {
         temp = a[i] * b[j] + c[i+j] + carry;
    carry = temp/BASE;
         c[i+j] = temp - carry*BASE;
      }
      c[i+j] = carry;
   }

   // Установить размер по первой ненулевой цифре
   i = A.Size + B.Size - 1;
   if ( c[i] == 0 ) i--;
   C.Size = i+1;

   return C;
}

// вспомогательная функция, для умножения на обычное число базового типа
// C = A*B
void SMul(const HugeInt &A, const short B, HugeInt &C) {
   long i, temp;
   const short *a=A.Coef;
   short *c=C.Coef, carry=0;

   for (i=0; i<A.Size;i++) {
      temp = a[i]*B + carry;
      carry = temp / BASE;
      c[i] = temp - carry*BASE; // с[i] = temp % BASE
   }

   if (carry) {
      // Число удлинилось за счет переноса нового разряда
      c[i] = carry;
      C.Size = A.Size+1;
   }
   else C.Size = A.Size;
}
// вспомогательная функция, где делитель - обычное число базового типа
void SDiv(const HugeInt &A, const short B, HugeInt &Q, short &R) {
   short r=0, *q=Q.Coef;
   const short *a=A.Coef;
   long i, temp;
   for ( i=A.Size-1; i>=0; i--) { // идти по A, начиная от старшего разряда
      temp = r*BASE + a[i]; // r - остаток от предыдущего деления
      // вначале r=0, temp - текущая цифра A с
      // учетом перенесенного остатка
      q[i] = temp / B; // i-я цифра частного
      r = temp - q[i]*B; // остаток примет участие в вычислении
      // следующей цифры частного
   }
   R = r;
   // Размер частного меньше, либо равен размера делимого
   i = A.Size-1;
   while ( (i>0) && (q[i]==0) ) i--;
   Q.Size = i+1;
}

HugeInt HugeInt::operator/(HugeInt &B)
{
   // Q = A/B, R=A%B
   HugeInt A(*this);
   HugeInt Q, R;

   // Вырожденный случай 1. Делитель больше делимого.
   if ( A.Size < B.Size ) {
      Q.zero();
      R=A;
      return Q;
   }

   // Вырожденный случай 2. Делитель - число базового типа.
   if ( B.Size == 1) {
      SDiv ( A, B.Coef[0], Q, R.Coef[0]);
      R.Size = 1;
      return Q;
   }

   // Создать временный массив U, равный A
   // Максимальный размер U на цифру больше A, с учетом
   // возможного удлинения A при нормализации
   HugeInt U; U.zero(); U = A;

   // Указатели для быстрого доступа
   const short *b=B.Coef;
   short *u=U.Coef, *q=Q.Coef;
   long n=B.Size, m=U.Size-B.Size;
   long uJ, vJ, i;
   long temp1, temp2, temp;
   short scale; // коэффициент нормализации
   short qGuess, r; // догадка для частного и соответствующий остаток
   short borrow, carry; // переносы

   // Нормализация
   scale = BASE / ( b[n-1] + 1 );
   if (scale > 1) {
      SMul (U, scale, U);
      SMul (B, scale, B);
   }

   // Главный цикл шагов деления. Каждая итерация дает очередную цифру частного.
   // vJ - текущий сдвиг B относительно U, используемый при вычитании,
   // по совместительству - индекс очередной цифры частного.
   // uJ - индекс текущей цифры U
   for (vJ = m, uJ=n+vJ; vJ>=0; --vJ, --uJ) {
      qGuess = (u[uJ]*BASE + u[uJ-1]) / b[n-1];
      r = (u[uJ]*BASE + u[uJ-1]) % b[n-1];

      // Пока не будут выполнены условия (2) уменьшать частное.
      while ( r < BASE) {
         temp2 = b[n-2]*qGuess;
         temp1 = r*BASE + u[uJ-2];
         if ( (temp2 > temp1) || (qGuess==BASE) ) {
            // условия не выполнены, уменьшить qGuess
       // и досчитать новый остаток
            --qGuess;
            r += b[n-1];
         } else break;
      }

      // Теперь qGuess - правильное частное или на единицу больше q
      // Вычесть делитель B, умноженный на qGuess из делимого U,
      // начиная с позиции vJ+i
      carry = 0; borrow = 0;
      short *uShift = u + vJ;

      // цикл по цифрам B
      for (i=0; i<n;i++) {
         // получить в temp цифру произведения B*qGuess
         temp1 = b[i]*qGuess + carry;
         carry = temp1 / BASE;
         temp1 -= carry*BASE;
         // Сразу же вычесть из U
         temp2 = uShift[i] - temp1 + borrow;
    if (temp2 < 0) {
            uShift[i] = temp2 + BASE;
            borrow = -1;
         } else {
            uShift[i] = temp2;
            borrow = 0;
    }
      }

      // возможно, умноженое на qGuess число B удлинилось.
      // Если это так, то после умножения остался
      // неиспользованный перенос carry. Вычесть и его тоже.
      temp2 = uShift[i] - carry + borrow;
      if (temp2 < 0) {
         uShift[i] = temp2 + BASE;
         borrow = -1;
      } else {
         uShift[i] = temp2;
         borrow = 0;
      }

      // Прошло ли вычитание нормально ?
      if (borrow == 0) { // Да, частное угадано правильно
         q[vJ] = qGuess;
      } else { // Нет, последний перенос при вычитании borrow = -1,
         // значит, qGuess на единицу больше истинного частного
    q[vJ] = qGuess-1;
         // добавить одно, вычтенное сверх необходимого B к U
         carry = 0;
         for (i=0; i<n; i++) {
            temp = uShift[i] + b[i] + carry;
            if (temp >= BASE) {
          uShift[i] = temp - BASE;
               carry = 1;
            } else {
               uShift[i] = temp;
               carry = 0;
            }
         }
         uShift[i] = uShift[i] + carry - BASE;
      }

      // Обновим размер U, который после вычитания мог уменьшиться
      i = U.Size-1;
      while ( (i>0) && (u[i]==0) ) i--;
      U.Size = i+1;
   }
   // Деление завершено !
   // Размер частного равен m+1, но, возможно, первая цифра - ноль.
   while ( (m>0) && (q[m]==0) ) m--;
   Q.Size = m+1;

   // Если происходило домножение на нормализующий множитель -
   // разделить на него. То, что осталось от U - остаток.
   if (scale > 1) {
      short junk; // почему-то остаток junk всегда будет равен нулю:
      SDiv ( B, scale, B, junk);
      SDiv ( U, scale, R, junk);
   } else R=U;

   return Q;
}

void HugeInt::input(char* string)
{
   short buf[SizeMax]; // вспомогательный массив коэффициентов
   Size=0;
   for (int i=0; ;i++)
   // вычисляем размер, т.е. если i-ый элемент является терминирующим нулём ('\0'),
   // то значит это последний элемент
      if (string[i]=='\0') {
         Size=i;
         break;
      } else {
    char ch = string[i];
    buf[i] = atoi(&ch);
      }

   // цифры хранятся в обратном порядке, поэтому коэффициенты нужно перевернуть
   for (int j=0; j<Size; j++)
      Coef[j] = buf[Size-j-1];
}

void HugeInt::output()
{
   for (int i=0; i<Size; i++) cout << Coef[Size-i-1];
}

int main()
{
   // создаём числа
   HugeInt A, B, C;

   clrscr();

   char buf[100];
   cout << "введите a="; cin >> buf;
   A.input(buf);
   cout << "введите b="; cin >> buf;
   B.input(buf);
   cout << "введите c="; cin >> buf;
   C.input(buf);

   HugeInt Result;
   Result = A + B;
   cout << endl << "a+b=";
   Result.output();
   Result = A - B;
   cout << endl << "a-b=";
   Result.output();
   Result = A * B;
   cout << endl << "a*b=";
   Result.output();
   Result = A / B;
   cout << endl << "a/b=";
   Result.output();

   cout << endl;
   cout << endl << "a<b " << (short(A<B) ? "да" : "нет");
   cout << endl << "a>b " << (short(A>B) ? "да" : "нет");
   cout << endl << "a==b " << (short(A==B) ? "да" : "нет");
   cout << endl << "a!=b " << (short(A!=B) ? "да" : "нет");
   cout << endl << "a>=b " << (short(A>=B) ? "да" : "нет");
   cout << endl << "a<=b " << (short(A<=B) ? "да" : "нет");
   cout << endl;
   cout << endl << "a is zero: " << (A.isZero() ? "да" : "нет");
   cout << endl << "b is zero: " << (B.isZero() ? "да" : "нет");
   cout << endl << "c is zero: " << (C.isZero() ? "да" : "нет");
   getche();
   return 0;
}

Работоспособность данной программы проверялась в среде Borland С++ 4.5

Решение подобных задач вы можете заказать на этой страничке. 		 
2005-2007 help-studia andy kras



В избранное