35. Моделирование. "Волчий остров"

Остров (прямоугольник фиксированного размера) заселен дикими кроликами,

волками и волчицами. Имеется по несколько представителей каждого вида.

Кролики с вероятностью 1/9 передвигаются в один из восьми соседних

квадратов или остаются на прежнем месте. Каждый кролик с вероятностью 1/5

превращается в двух кроликов. Каждая волчица передвигается случайным

образом, пока в одном из восьми соседних квадратов не окажется кролик, за

которым она охотится. Если волчица и кролик оказываются в одном квадрате,

волчица съедает кролика и получает одно "очко". В противном случае она

теряет 0.1 "очка". Волки и волчицы c нулевым количеством "очков" умирают.

Волк ведет себя подобно волчице до тех пор, пока поблизости не исчезнут все

кролики; тогда если волчица находится в одном из восьми близлежащих

квадратов, волк гонится за ней. Если волк и волчица окажутся в одном

квадрате и там нет кролика, которого нужно съесть, они производят потомство

случайного пола.

Для создания более устойчивой экологической системы острова введите на

острове запретные зоны для хищников.

Разработать набор классов, реализующих данную программу.

Предусмотреть редактирование, сохранение на диске и восстановление с диска

популяции, гибкое изменение параметров системы, пошаговую демонстрацию и

режим быстрого просчета.

36. Множество с хэш-таблицей

Реализовать класс-шаблон, объектами которого являются множества элементов с

элементами типа T (int, float, myObject, и т.д.) Для внутреннего

представления множества использовать динамическую хэш-таблицу.

Предполагается, что элемента типа Т можно сравнивать на равенство, кроме того

для элементов типа Т определен оператор int() преобразования в целое число.

Операции над множеством:

* узнать мощность множества

* добавить/удалить элемент

* проверить есть ли элемент в множестве

* сделать множество пустым

* ввод/вывод множество в поток

Отношения между двумя множествами:

* равны ли два множества

* содержит ли одно множество другое

* пересечение двух множеств

* объединение двух множеств

* разность двух множеств

* симметрическая разность двух множеств

Реализовать класс "Итератор множества", который позволяет перебирать

элементы заданного множества. Порядок перебора элементов не фиксирован.

Набор методов итератора:

* установить итератор в начальное состояние,

* проверить: итератор перебрал все элементы множества,

* выдать текущий элемент,

* перейти к следующему элементу.

Пример:

myObject e(..);

SetOf S;

S.adjoinElement( e ); // добавить элемент e в S.

SetIterator Iter( S );

for( Iter.reset(); !Iter.done(); Iter.next() ) {

myObject tmp = I.value();

...

}

Рекомендуется сначала сделать обычные классы с типом элемента myObject, не

используя шаблоны. После того, как эти классы будут отлажены, можно

модифицировать их для использования шаблонов.

37. МНОЖЕСТВО НА БАЗЕ ДБ-ДЕРЕВА

1. Реализовать шаблонный класс "Двоичное Б-дерево" элементов типа Т

(описание двоичного Б-дерева смотри в книге Н.Вирта "Алгоритмы и

структуры данных"). Предполагается, что элементы типа Т

можно сравнивать на равенство (==) и относительно некоторого порядка <.

2. Реализовать шаблонный класс "Множество" элементов типа Т на базе двоичного

Б-дерева.

Операции над множеством:

* узнать мощность множества

* добавить/удалить элемент

* проверить есть ли элемент в множестве

* сделать множество пустым

* ввод/вывод множество в поток

Отношения между двумя множествами:

* равны ли два множества

* содержит ли одно множество другое

* пересечение двух множеств

* объединение двух множеств

* разность двух множеств

* симметрическая разность двух множеств

Реализовать класс "Итератор множества", который позволяет перебирать

элементы заданного множества. Порядок перебора элементов не фиксирован.

Набор методов итератора:

* установить итератор в начальное состояние,

* проверить: итератор перебрал все элементы множества,

* выдать текущий элемент,

* перейти к следующему элементу.

Пример:

myObject e(..);

SetOf S;

S.adjoinElement( e ); // добавить элемент e в S.

SetIterator Iter( S );

for( Iter.reset(); !Iter.done(); Iter.next() ) {

myObject tmp = I.value();

...

}

38. Б-ДЕРЕВО

Реализовать шаблонный класс "Б-дерево" элементов типа Т в предположении,

что все дерево помещается в оперативной памяти. Порялок дерева задается

при инициализации и не меняется. Для элементов типа Т

определен оператор порядка < и сравнения на равенство ==.

Необходимо реализовать:

* поиск элемента в дереве

* вставка и удаление элемента

* вывод дерева в поток в порядке возрастания элементов

* ввод из потока

* проверка дерева на пустоту

* очистка дерева