АВТ
Language:

Remote Training on Programming

Problems On-line status Contests FAQ
For authors:
Register  ||  Login
 
Hello, Guest! Login or register.

228. BitArray

Time Limit: 1 seconds
Memory Limit:1500KB
Points:5
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 Author/source:
Educational Courses / Data Structures and Algorithms / Data Structures /
228. 226. Brackets Control 227. Brackets Replace 245. Divisors
Educational Courses / C/C++for EPO-21 / Lab 4 /
228. 242. BitArray - 2
We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. The art of tackling miniproblems with all our energy will sharpen our talents for the real problems. Donald E. Knuth.
time generating 0.468 sec.
© Copyright VSTU, AVT, Nosov D.A.