Практика программирования (Бейсик, Си, Паскаль)


Дерево решений - часть 3


Совет 2 (общий)

Для удобства манипуляций со значениями вершин их целесообразно рассматривать и как одномерные строки, и как двумерные массивы 2x3, каждый элемент которых представлен соответствующим символом. Первое удобно для организации сравнения позиций, а второе—для перестановки фишек. Связь между одномерным индексом k и парой двумерных индексов (i,j) осуществляется по формулам:

k = i * 3 + j. i = k div 3. j = k mod 3.

Следует не забывать, что приведенные формулы справедливы, если индексы в массивах отсчитываются от 0, например так, как это делается в Си. Однако в строках Бейсика и Паскаля индексы символов отсчитываются от 1. Поэтому в соответствующих фрагментах программ введена соответствующая коррекция значения одномерного индекса k.

Совет 3 (общий)

Для более четкой организации структуры программы выделим следующие программные единицы:

  • level — процедура, порождающая новые вершины в дереве решений из позиции с индексом from;

  • change (il, jl) —процедура, осуществляющая обмен символа с указанными индексами, и символа "*", расположенного в позиции (i, j). Если новая позиция допустима и она еще не содержится в дереве решения, то процедура change присоединяет новую позицию к дереву решений и увеличивает значение счетчика вершин птах;

  • poisk — процедура, осуществляющая поиск исходной позиции роs 0 в дереве решений. Если исходная позиция найдена среди приводимых вершин, то процедура poisk осуществляет раскрутку цепочки ходов до главной вершины дерева;

  • print_tab(s) —процедура отображения очередного хода, представленного строкой s, в форме таблички размером 2x3. Координаты левого верхнего угла таблички на экране представлены глобальными переменными (х0, у0).

Программа 6_01.bas

DECLARE SUB change (il AS INTEGER, j1 AS INTEGER)

DECLARE SUB printTAB (s AS STRING)

DECLARE SUB level ()

DECLARE SUB poisk ()

REM Дерево решений BASIC

DEFINT A-Z

DIM SHARED x0 AS INTEGER, y0 AS INTEGER, nmax AS INTEGER, k AS INTEGER

DIM SHARED from AS INTEGER




- Начало -  - Назад -  - Вперед -



Книжный магазин