оно мяукает?

кошка

оно лает?

собака

рис. 12. Преобразование дерева животных (первый случай)

Во втором случае компьютер приходит к некоторому решению, но оно не удовлетворяет пользователя:

Компьютер: оно мяукает? Игрок: да

Компьютер: это кошка? Игрок: нет Компьютер: не знаю

В подобной ситуации придётся запросить задуманное животное и его отличие от догадки компьютера:

Компьютер: кто это? Игрок: тигр

Компьютер: чем оно отличается от животного кошка ? Игрок: оно крупнее кошки

В таком случае первоначальное дерево придётся преобразовать иным способом (рис. 1.3).

оно мяукает?

оно крупнее кошки?

тигр

кошка

Рис 1.3. Преобразование дерева животных (второй Ыучай)

Так компьютер запоминает новых животных. Теперь можно приступить к реализации игры. Необходимо предусмотреть функции загрузки и сохранения построенных деревьев.

1.3.2. Генератор формул

Автоматическое создание дерева математического выражения

В школаЬс и в вузах очень любят типовые задачи. Задание у всех одно и то же, только какая-нибудь математическая функция разная. Например, у одного ученика f(x) = sin(x) + 5, а у другого - f(x) = х + 10 / х. Выдумывать функции для всего класса учителю приходится самому. Почему бы не поручить эту работу компьютеру?

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

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

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

Компьютер: оно мяукает? Игрок: нет Компьютер: не знаю

При возникновении такой ситуации предлагается ввести определение для нового животного:

Компьютер: кто это? Игрок: собака

Компьютер: как отличить это животное? Игрок: оно лает

После ответа пользователя дерево животных приобретает вид, изображённый на рис. 1.2.

Пример вывода:

f = cos(sin(y cos(x - у)) * 5)

Решение

Любой человек, имеющий представление о задаче разбора математического выражения, сразу же скажет, что выражение представляет собой древовидную структуру, нетерминальными узлами которой являются операции, а терминальными - переменные и константы. Любому узлу может быть также сопоставлена унарная функция, такая как sin или cos (рис. 1.4). Обратите внимание: в наших обозначениях унарный минус также является функцией. Так, чтобы иметь возможность получить функцию вида f(x) = -х, придётся указать минус в списке унарных функций.

Глава 1. Структуры данных

Рис 1.4. Дерево функщли f = cos(sln(y л со$(х - у)) * 5)

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

Можно предложить следующий простой алгоритм генерации функций длиной N операций:

создать дерево из одного терминального ула

ЦИКЛ N раз

выбрать случайный термкаальный узел .

сделать его нетерминальным, добавив два тзрюшаданых узла-потонка КОНЕЦ ЦИКЛА ... . I

прагтоять яащдсаог -УЗЛУ оиучайво! выбсяацую укарцув фунжцип (или ничего) щясшсать кацпивог тесашнапьвовсу узлу случайную переменку или константу Хфхшисать каждому нетерминальному узлу случайно выбранную операцию

Займёмся теперь его реализацией. Поскольку дерево состоит из узлов, нам потребуется новый тип данных узел :

struct TreeNode {

bool isTerminal; string Function; string Value, Operation;

TreeNode *Left, *Right;

является ли узел терминальным унарная функция

содержимое узла: переменная либо операция

указатели на узлы-потомки

TreeNodeO : isTerminal (true) {} узел создается как

терминальный

Поскольку нам потребуется обходить все узлы дерева, удобнее будет держать их в отдельной структуре данных - векторе Tree, а не писать рекурсивные функции обхода. Пригодятся также ссылки на существующие терминальные узлы:

vector<TreeNode *> Tree; vector<TreeNode *> TerminalNodes;

Ещё три глобальных вектора предназначены для хранения переменных, операций и функций:

vector<string> Variables, Operations, Functions;

Эти векторы мы будем заполнять, вводя с клавиатуры строки, разделённые пробелами. Для их чтения служит функция ReadValues ():

vector<string> ReadValues() {

vector<string> result; string line, value;

getline(cin, line); считать с клавиатуры строку

Поскольку о приоритете операций не делается никаких предположений, скобки в выражениях не опускаются.

Пример ввода:

переменные: х у 5 операции: + - * функции: sin cos количество операций: 3

количество операций

прочитать переменные

прочитать операции

прочитать функции

добавить в список функций ещё столько же пустых функций, чтобы случайно выбирать пустую функцию с вероятностью 1/2 fill n(back inserter(Functions), Functions.size(), );

добавить в дерево первый узел и поместить его в список терминальных

Tree.push back(new TreeNode());

TerminalNodes.push back(Tree.back()); randomizep;

for(int i = 0; i < N; i++)

{ выбрать случайный терминальный узел

int г = random(TerminalNodes.size());

TreeNode *it - TerminalNodes[r];

исключить его из списка терминальных TerminalNodes.erase(TerminalNodes.begin() + r); it->isTerminal - false;

добавить левый и правый узлы-потомки Tree.push back(new TreeNode()); TerminalNodes.push back(Tree.back{)); it->Left = Tree.backO; Tree.push back(new TreeNode()); TerminalNodes.push back(Tree.back()); it->Right = Tree.backO;

дерево сгенерировано. Осталось назначить узлам

переменные, операции и функции

for (unsigned i = 0; i < Tree.sizeO; i++)

TreeNode *p = Tree[i]; выбрать функцию

p->Function = Functions[random(Functions.size())] ;

для терминального узла выбрать переменную, для нетерминального - операцию if (p->isTenninal)

p->Value = Variables!random(Variables.sizeO)];

else

p->Operation = Operations[random(Operations.size())];

напечатать готовое выражение

cout f = PrintTree(Tree[0]) endl;

for(unsigned i = 0; i < Tree.sizeO; i++) очистить память delete Tree[i];

return 0;

istringstream is(line);

while(is value) в цикле считать каждое значение

result.push back(value); return result;

Последняя служебная функция предназначена для получения строкового представления дерева (то есть готовой записи сгенерированной математической функции):

string PrintTree(TreeNode *it) строковое представление дерева

с корнем it

терминальный узел выводится без изменений

если задана унарная функция, добавляется имя функции

и круглые скобки

if(it->isTenninal)

return it->Function == ? it->Value :

it->Function + + it->Value + );

для нетерминального узла результат состоит из:

- унарной функции (если она есть);

- открывающей круглой скобки;

- строкового представления левого поддерева;

- знака операции;

- строкового представления правого поддерева; - закрывающей круглой скобки

return it->Function + ( + PrintTree(it->Left) + + it->Operation + - + PrintTree(it->Right) + ) ;

Основная работа выполняется в функции main (), прямо следующей приведённому выше псевдокоду:

int main(int argc, char* argv[]) {

int N;

Variables = ReadValues(); Operations = ReadValues(); Functions = ReadValues(); прочитать количество операций cin N;