АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
News FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

228. BitArray

Time Limit: 1 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added Undefined

Создайте класс BitArray, реализующий структуру данных "битовый массив" и имеющий следующий интерфейс:

class BitArray
{
public:

  //конструктор с одним параметром - длиной массива
  //выделяет память и заполняет массив нулевыми байтами
  BitArray(int n);

  //конструктор копий
  BitArray(const BitArray &b);

  //деструктор
  ~BitArray();

  //функция, возвращающая размер массива
  int size(void);

  //операция индексирования
  int operator [] (const unsigned int i) const;

  //присвоить i-му биту значение v (0 или 1)
  void setbit(int i, int v);

  //операция присваивания
  BitArray& operator = (const BitArray &b);

  //операция & - побитовое "И" двух массивов. Если длина одного массива 
  //меньше длины другого, его недостающие биты считаются равными 0
  BitArray operator &(const BitArray &b) const;

  //операция | - побитовое "ИЛИ" двух массивов. Если длина одного массива 
  //меньше длины другого, его недостающие биты считаются равными 0
  BitArray operator | (const BitArray &b) const;

  //операция ~ - инвертирование битов массива (0 на 1, 1 на 0)
  BitArray operator ~ (void) const;

  //операция вывода - выводит в одну строчку без пробелов значения в массиве - нули или единицы
  friend ostream& operator << (ostream &os, const BitArray &b);

  //операции сравнения
  bool operator == (const BitArray &b) const;
  bool operator != (const BitArray &b) const;

private:
  //сюда вставьте закрытые данные, какие считаете нужным
  ...
}

В проверяющую систему отправляется полная реализация класса без какого-либо дополнительного кода. Отправляемая программа не должна содержать функцию main! Вместо этого в конце программы поставьте строчку:

#include "bit-array-test.h"

Тем самым вы подключите функцию main (её текст вам недоступен ;), которая и будет тестировать ваш класс.


Ограничения:

Общее количество одновременно существующих объектов не превышает 1000, их суммарная длина в битах не превышает 7 млн.


Пример некоторых проверок, которые будут выполняться над вашим классом:

int main(void)
{
 BitArray a(50), b(80);
 for (int i=0; i<60; i++) b.setbit(i,1);
 a=b;
 for (int i=0; i<80; i++) b.setbit(i,0);
 cout << a << endl << b << endl;
 if (a==b) cout << "YES"; else cout << "NO"; cout << endl;
 if (a!=b) cout << "NO"; else cout << "YES"; cout << endl;
 if (a==a) cout << "YES"; else cout << "NO"; cout << endl;
 if (a!=a) cout << "NO"; else cout << "YES"; cout << endl;
 BitArray c = a & b;
 cout << c << endl;
 BitArray d(10); d.setbit(0,1); d.setbit(3,1);
 c = a | b;
 cout << c << endl;
 c = ~c;
 cout << c << endl;
 return 0;
}

Результат, который должен получиться для этого примера:

11111111111111111111111111111111111111111111111111111111111100000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
NO
NO
YES
YES
00000000000000000000000000000000000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111111111111100000000000000000000
00000000000000000000000000000000000000000000000000000000000011111111111111111111

Дополнительное задание.Cделайте так, чтобы операцию индексирования можно было использовать не только справа, но и слева от присваивания, т.е. писать выражения вида a[i]=1 и избавиться тем самым от не очень красивых вызовов функции setbit.


View Problem Statistics Submit Problem discussion Author/source:
Educational Courses / Algorithms and Data Structures / Data Structures /
1982. Assignments 228. 226. Brackets Control 227. Brackets Replace 1945. Cockroaches
Educational Courses / Programming on high-level language / Lab 4 /
228. 242. BitArray - 2
time generating 0.203 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.