SisProg2 (565140), страница 2
Текст из файла (страница 2)
Таблица 3
| 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 |
Предположим, имеется входной ключ NYNY, который мы трансформируем в форме 0101. Далее выполняется поразрядная логическая операция “И” над этим ключом и первым столбцом таблицы 3. Результат дает 0101.
Сравним этот результат с первым столбцом таблицы.
3. Очевидно, что совпадение отсутствует. Этот процесс повторяется с каждым следующим столбцом таблицы 2 и выполняется сравнение с соответствующим столбцом таблицы 3. В рассматриваемом примере ключ 0101 приводит к выбору правила R3.
Таблица решающих правил и дерево решений
Рассмотрим полную решающую таблицу с ограниченным входом на три условия вида
|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| q1 q2 q3 | Y X Y | Y Y N | Y N Y | Y N N | N Y Y | N Y N | N N Y | N N N |
| действия | A1 | A2 | A2 | A3 | A1 | A1 | A1 | A1 |
Отвечающее этой таблице дерево решений можно представить в виде, когда в узлах ставятся условия, а дуги - выходящие из них метки Y или N. Не концевые вершины задают условия (вопросы), ответом из которых являются метки исходящих из них дуг. Концевые элементы (листья) отвечают действиям, которые нужно произвести. Часто здесь ставятся адреса передачи управления на подпрограммы выполнения действий, поэтому концевые листья часто называют вектором передачи. Отсюда имеем:
Легко видеть, что если q1 и q2 имеют значение Y, то q3 не требуется запрашивать. Выход не зависит от ответа на вопрос. Аналогичная ситуация возникает, если на q1 получен ответ N. Поэтому можно сократить дерево, как показано далее.
Этому дереву будет отвечать сокращенная таблица вида:
|
| 1 | 2 | 3 | 4 |
| q1 q2 q3 | Y Y - | Y N Y | Y N N | N - - |
| действия | A1 | A2 | A3 | A1 |
Отсутствие в сокращенной таблице некоторого входа, имевшегося в полной таблице, отвечает фразе “НЕ ИМЕЕТ ЗНАЧЕНИЯ”. Можно отметить, что работа с деревом решений значительно сложнее, чем с решающей таблицей. С другой стороны, между деревом решений и решающей таблицей имеет место полное соответствие.
Задание
1. Спроектировать программу, которая, используя полную таблицу решающих правил с числом условий, равным четырем, и заданным вектором переходов, позволяет сделать выбор точки перехода по заданному входному ключу.
2. Спроектировать программу, которая, используя сокращенную таблицу решающих правил для числа условий, равным четырем, позволяет отыскать точку перехода по входному ключу.
Литература
1. Э.Хамби. Программирование таблиц решений. - М.: Мир, 1976.
2. А.Берзтисс. Структуры данных. - М.: Статистика, 1974.
9
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
