IPB
ЛогинПароль:

> ВНИМАНИЕ!

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Игра 20 вопросов, Вопросы по алгоритмам
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 6
Пол: Мужской
Реальное имя: Николай

Репутация: -  0  +


Цитата

Реализовать "дерево решений". Нелистьевые вершины такого дерева содержат предикаты (вопросы, ответы на которые могут принимать значения либо "да", либо "нет"). Пользователь программы должен задумать простой объект и давать ответы на вопросы программы в соответствии со свойствами этого объекта. Пользователь получает вопросы, содержащиеся в вершинах дерева, начиная с его корня. Ответ "да" пользователя соответствует пути, проходящему через левого потомка текущей вершины, а ответ "нет" - пути, проходящему через правого потомка текущей вершины. После каждого ответа выбирается соответствующая ветвь и процесс повторяется. Листьевые вершины дерева решений содержат определение того объекта, которому соответствует последовательность ответов пользователя, ведущих от корня дерева к данному листу. Когда в процессе движения программа доходит до листа, она выводит содержащееся там определение объекта, "угадывая" тем самым объект, задуманный пользователем. Если программа угадала верно, считается, что она выиграла. Если же ответ не верен, то программа начинает "обучаться", предлагая пользователю ввести вопрос, ответ на который ("да" или "нет") зафиксирует различие между объектом, который задумал пользователь, и объектом, который "вычислила" программа. Вопрос, сформулированный пользователем, затем помещается в новую вершину дерева, потомками которого становятся лист с определением "старого" объекта и лист с определением "нового" объекта. После этого можно начать новый тур игры. Конец игры определяется программой по ответу пользователя на специальное приглашение к новому туру.

Цитата

Система имеет один первоначальный вопрос и два ответа, при первом запуске просит пользователя загадать объект, после чего задает вопрос, например:

Объект живое существо?

В зависимости от ответа пользователя Да или Нет, выдает ему ответ, например Автомобиль или Человек. Если программа угадала с первого раза, то предлагает сыграть еще раз, инача предлагает ввести пользователю дополнительный вопрос, который поможет идентифицировать объект. Сами вопросы и объекты хранятся в виде бинарного дерева. Где не терминальные узлы содержат вопросы, а терминальные - объекты.
Входные данные: ответ пользователя Да или Нет, новый объект, новый вопрос.
Выходные соответственно вопросы системы, результат угадывания, запрос о вводе нового объекта или вопроса, запрос о продолжении.
При добавлении нового вопроса, соответственно меняется структура бинарного дерева.


Вот структура дерева:
Цитата

PTree=^Tree;
Tree=record
info:string[70];
da,net:PTree;
end;


Есть узел current, на котором в текущий момент стоит указатель, current в данный момент терминальный узел.
Как правильно написать функции добавления нового вопроса в дерево?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата
Как правильно написать функции добавления нового вопроса в дерево?
Ну, например, так:
procedure AddLeaf(var root: PTree; s: string);
begin
new(root);
root^.da := nil; root^.net := nil;
root^.info := s;
end;

procedure NewQuestTo(var root: PTree);
var s: string;
begin
write(' question -> '); readln(root^.info);

write('YES answer -> '); readln(s);
AddLeaf(root^.da, s);
write('NO answer -> '); readln(s);
AddLeaf(root^.net, s);
end;
и передать в NewQuestTo твой current. Тогда тот узел, на который он указывает, из терминального превратится в НЕтерминальный.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 6
Пол: Мужской
Реальное имя: Николай

Репутация: -  0  +


Спасибо. Как грамотно записать дерево в файл, что бы потом воссоздать его? Дерево бинарное, не сбалансированное.

Сообщение отредактировано: XBugiman -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Ну, что-то вот в таком виде:

const
EOT = '**';

procedure SaveTree(var f: text; var curr: ptree; L, R: byte);
begin
if curr <> nil then begin

L := Ord(curr^.da <> nil);
R := Ord(curr^.net <> nil);
writeln(f, curr^.info);
writeln(f, L, ' ', R);

if L = 1 then SaveTree(f, curr^.da, L, R);
if R = 1 then SaveTree(f, curr^.net, L, R);
end
else write(f, EOT);
end;

var
s: string;

procedure LoadTree(var f: text; var curr: ptree; L, R: byte);
begin
if s <> EOT then begin
readln(f, s);
readln(f, L, R);

new(curr);
curr^.info := s;
if L = 1 then LoadTree(f, curr^.da, L, R)
else curr^.da := nil;

if R = 1 then LoadTree(f, curr^.net, L, R)
else curr^.net := nil;
end
else curr := nil;
end;


Вызывать - так:
  // Запись:
assignfile(f, 'testtree.txt'); rewrite(f);
savetree(f, root, 0, 0);
closefile(f);

// ...
// Чтение:
assignfile(f, 'testtree.txt'); reset(f);
s := '';
root_new := nil;
loadtree(f, root_new, 0, 0);
closefile(f);
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 23:24
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name