3.1.3. Характеристические векторы

Важной разновидностью смежного размещения является случай, когда такому представлению подвергается подпоследовательность последовательности.

В этом случае подпоследовательность можно представить характеристическим вектором – последовательности из 0 и 1.

Так например, для последовательности S={1,2,3,4,5,6,7,8,9} характеристический вектор последовательности чисел, кратных 3 имеет вид (0,0,1,0,0,1,0,0,1).

3.1.4. Списки. Деревья

Использование списков для разработки алгоритма «Крестики-нолики»

На практических занятиях рассматривался один из вариантов решения «примитивной» игровой задачи – «крестики-нолики». Рассматривался один из возможных подходов к решению задачи- критериальный подход. Суть которого сводится к введению некоторого критерия оценки веса каждой из клеточек игрового поля, в зависимости от текущей ситуации и перспектив развития игры для алгоритма.

Была предложена достаточная простая схема формирования критерия оценки веса «клетки» игрового поля. Например, для всех угловых клеток поля итоговый (суммарный) критерий складывается из значений частных критериев () по всем исходящим из клетки линиям, на которых образуется выигрышная или проигрышная ситуация (для угловых клеток таких линий три).

Для простоты, чтобы не вводить сложных структур данных, был предложен следующий простой алгоритм вычисления весовой оценки клетки. Для каждой клетки смежной с клеткой, для которой производится вычисления критерия вводится собственная переменная, принимающая значение (в зависимости от ситуации)(см. рис.9). Критериивычисляются для каждой из «операционных» линий.

Тогда, с помощью языка GRAPH, алгоритм вычисления критерия по линии (*,x, y) можно представит граф-программой (см. рис. 9).

Следует заметить, что не всегда при разработке алгоритмов следует использовать сложные «изящные» решения. Очень часто, для достаточно несложных задач простые решения оказываются более результативными и качественными.

Однако для трехмерной игры в «крестики-нолики» предложенный подход явно неприемлем.

Рассмотрим его модификацию, использующую модель данных – линейный список.

Поместим в корень дерева ссылку на элемент матрицы, содержащей координаты базовой угловой вершины, расположенной в точке (0, 0), далее в списке расположены ссылки на координаты смежных с ней операционных линий так, как это представлено на рисунке 11.

Здесь в матрице Mv вектора содержат координаты элементов матрицы игрового поля, например. Используя построенный список можно вычислить критериидля базовой угловой вершины. Для оставшихся 3 вершин можно сформировать еще 3 списка, но можно этого и не делать.

Если ввести линейное преобразование

связанное с поворотом осей координат на заданный угол , и в матрицеA над каждым вектором произвести данное преобразование, то получим новую матрицув которой все элементы повернуты на угол. Для того, чтобы перебрать все варианты угловых вершин необходимо сделать три поворота.