Задачка - 3. Язык решения задачи

Перейти вниз

Задачка - 3. Язык решения задачи

Сообщение автор Gudleifr в Вс Июн 11, 2017 1:02 pm



Нужно решить типовую задачу "перевозки": "волк-коза-капуста", "3  миссионера и 3 каннибала", "рыцари и оруженосцы", "help-the-sail". Не изложить готовое решение: "Сначала везем этого, потом - того..", а придумать способ, которым можно объяснить правила игры программе, которая решит задачу сама.

Примерный алгоритм решения:
1) Начальная ситуация описывается кадром стека (удобнее, конечно, шкалой, но тогда не нужны стековые манипуляторы) - для каждого персонажа (и лодки), по одному значению-состоянию (левый/правый берег);
2) Верхний кадр стека проверяется на условие победы (все на правом берегу), в случае успеха - конец;
3) Верхний кадр стека проверяется на недопустимость (волк ест козу, каннибалы - миссионеров и ть.д.), в случае успеха - кадр удаляется со стека и возвращаемся к шагу 2;
4) Верхний кадр стека заменяется последовательностью кадров, которые из него можно получить при очередном перемещении лодки. Возвращаемся к шагу 2.

Т.к. все перечисленные в начале поста задачи решаемые, стек исчерпаться не должен.
Вывод программы - протокол кадров и принятых по ним решений, в идеале - только продуктивные перемещения персонажей. Продумать, как избежать зацикливания алгоритма.
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения