АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

228. Битовый массив

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Неизвестный

Создайте класс 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.


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Учебные курсы / Алгоритмы и структуры данных / Структуры данных /
1986. Билеты на электричку 228. 695. Близкие числа 1946. Высота дерева 245. Делители
Учебные курсы / Программирование на языке высокого уровня / Лабораторная 4 /
228. 242. Битовый массив-2
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.