Форум Flasher.ru - Хорошее дело или машина Тьюринга

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)

- - Хорошее дело или машина Тьюринга (http://www.flasher.ru/forum/showthread.php?t=110454)

Хорошее дело или машина Тьюринга

Уважаемые Господа flash-программисты.

Меня зовут Женя Лакштанов, я математик и занимаюсь с младшеклассниками математикой и, в частности, алгоритмикой. Недавно мне удалось найти неплохую реализацию машины Тьюринга:

http://www.danilova.ru/phpbb/viewtop...2619&start=180
(в конце страницы, под заголовком "Несколько задач для веселого грузовичка")

Там же есть примеры задач, которые мои дети писали "на бумажке". Ясно, что неплохо бы иметь под это дело интерпретатор. Я детально могу описать, как он может выглядеть, но я очень много лет не программировал, и у меня это займет много времени. Хотя, видимо для человека в форме, это дело 1часа.
Буду рад, если кто-нибудь возьмется сделать это.
Спасибо за внимание.

к сожалению вы попали на форум флэшеров, а не альтруистов. сомневаюсь что у кого-то найдется время и желание.

Колега ;)
Могу помочь. Пиши в личку. что нужно сделать. За 1 час не обещаю, но до понедельника управлюсь :). Хотя раздел для поста конечно ты выбрал не совсем верный. Это скорее для вакансий подходит.

Цитата:

Сообщение от KidsKilla

Да ладно... задание ведь не сложное.

Цитата:

Сообщение от zurmansor

Да ладно... задание ведь не сложное.

а это все не важно. тут кабэ в основном народ занятой и ленивый =)

я вот бездельничаю на работе... мог бы и сделать %)
Ток вот не понял, нужно чтобы программа сама прокладывала маршрут исходя из условий, или юзер сам определяет маршрут, а программа просто показывает, что будет сделано при таких условиях? (Второе можно сделать и меньше чем за час, а первое - муторно... конец рабочей недели, думать не хочется %)

Код:

/**

* ...

* @author wvxvw

* @version 0.1

*/



package  {



        public class PathXML {

                

                public static const LINE:String = 'line';

                public static const STATION:String = 'station';

                public static const CARGO:String = 'cargo';

                public static const TRUCK:String = 'truck';

                public static const BOX:String = 'box';

                public static const DIR:String = 'dir';

                public static const IN:String = 'in';

                public static const OUT:String = 'out';

                public static const LOADED:String = 'loaded';

                public static const EMPTY:String = 'empty';

                public static const LOAD:String = 'load';

                public static const UNLOAD:String = 'unload';

                public static const STOP:String = 'stop';

                public static const LEFT:String = 'left';

                public static const RIGHT:String = 'right';

                public static const LT:String = '<';

                public static const GT:String = '>';

                public static const SLASH:String = '/';

                

                private var _xml:XML;

                

                public function PathXML(xml:XML = null, i:int = 0) {

                        super();

                        _xml = new XML(LT + LINE + SLASH + GT);

                        for (var j:int = 0; j < i; j++ ) {

                                addStation();

                        }

                }

                

                public function addStation():void {

                        var xn:XML = new XML(LT + STATION + SLASH + GT);

                        var xin:XML = new XML(LT + IN + SLASH + GT);

                        var xout:XML = new XML(LT + OUT + SLASH + GT);

                        xn.appendChild(xin);

                        xn.appendChild(xout);

                        _xml.appendChild(xn);

                }

                

                public function setTruck(i:int, b:Boolean):void {

                        var tx:XML = new XML(LT + TRUCK + SLASH + GT);

                        tx.@[CARGO] = b ? LOADED : EMPTY;

                        _xml[STATION][i].appendChild(tx);

                }

                

                public function setBoxes(i:int, b:int):void {

                        var bx:XML = new XML(LT + BOX + SLASH + GT);

                        for (var j:int = 0; j < i; j++ ) {

                                _xml[STATION][b].appendChild(bx);

                        }

                }

                

                public function setStationIN(i:int, b:Boolean):void {

                        _xml[STATION][i][IN].@[DIR] = b ? LOAD : UNLOAD;

                }

                public function setStationOUT(i:int, b:String):void {

                        switch(b) {

                                case LEFT:

                                        _xml[STATION][i][OUT].@[DIR] = LEFT;

                                        break;

                                case RIGHT:

                                        _xml[STATION][i][OUT].@[DIR] = RIGHT;

                                        break;

                                default:

                                        _xml[STATION][i][OUT].@[DIR] = STOP;

                                        break;

                        }

                }

                

                public function moveTruck():void {

                        var tx:XML = getXMLItem(TRUCK)[0];

                        var bx:XML = new XML(LT + BOX + SLASH + GT);

                        var ttx:XML;

                        var tp:int;

                        if (tx.@[CARGO] == LOADED) {

                                if (tx.parent()[IN].@[DIR] == UNLOAD) {

                                        tx.@[CARGO] = EMPTY;

                                        tx.parent().appendChild(bx);

                                }

                        } else {

                                if (tx.parent()[BOX].length()) {

                                        if (tx.parent()[IN].@[DIR] == LOAD) {

                                                tx.@[CARGO] = LOADED;

                                                delete tx.parent()[BOX][0];

                                        }

                                } else {

                                        // all boxes removed from the station

                                }

                        }

                        trace(tx.parent()[OUT].@[DIR]);

                        if (tx.parent()[OUT].@[DIR] == LEFT) {

                                for (var i:int = 0; i < _xml[STATION].length(); i++ ) {

                                        if (_xml[STATION][i][TRUCK].length()) {

                                                ttx = _xml[STATION][i][TRUCK][0].copy();

                                                tp = i;

                                                break;

                                        }

                                }

                                delete _xml[STATION][tp][TRUCK][0];

                                _xml[STATION][tp - 1].appendChild(ttx);

                        } else if(tx.parent()[OUT].@[DIR] == RIGHT) {

                                for (var j:int = 0; j < _xml[STATION].length(); j++ ) {

                                        if (_xml[STATION][j][TRUCK].length()) {

                                                ttx = _xml[STATION][j][TRUCK][0].copy();

                                                tp = j;

                                                break;

                                        }

                                }

                                delete _xml[STATION][tp][TRUCK][0];

                                _xml[STATION][tp + 1].appendChild(ttx);

                        }

                }

                

                public function toString():String {

                        return _xml.toXMLString();

                }

                

                public function getXMLItem(s:String):XMLList {

                        return _xml.descendants(s);

                }

        }

        

}

Код:

import PathXML;

var tf:TextField = new TextField();

tf.border = true;

tf.width = 600;

tf.height = 400;

addChild(tf);

var tm:Timer = new Timer(500);

var px:PathXML = new PathXML(null, 8);

tm.addEventListener(TimerEvent.TIMER,renderPosition)

px.setTruck(2,true);

px.setBoxes(5,5);

for (var i:int = 0; i < px.getXMLItem(PathXML.STATION).length() - 1; i++){

        px.setStationIN(i, true);

        px.setStationOUT(i, PathXML.RIGHT);

}

px.setStationIN(i, true);

px.setStationOUT(i, PathXML.STOP);

//trace(px);

function renderPosition(tevt:TimerEvent):void {

        px.moveTruck();

        tf.text = px.toString();

}

tm.start();

Ну вот пример, правда в примере программа для грузовика составляется так, что все коробки он никогда не увезет, но это уже либо задача пользователя, либо автора %)

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

Кстати, читал: ученые после сложнейших вычислений и экспериментов пришли к выводу, что счастье можно купить - для этого нужно всего лишь делать подарки окружающим.

Млин, забыл добавить опцию остановить грузовик, ну ничего, вернусь домой - добавлю... ну и наверное нуна будет какой-нть более "дружественный ЮАЙ" приделать %)

ЗЫ. Пофиксил стопы

Спасибо всем за поддержку. Коллега Zurmansor уже изъявил желание помочь, поэтому вопросы по реализации можно, при желании, обсуждать с ним.

Я в восторге от комментария WVXVW по поводу программы, которая сама построит алгоритм для машины Тьюринга. Ведь, как известно, машина Тьюринга может реализовать любой алгоритм

http://ru.wikipedia.org/wiki/%D0%9F%...BD%D0%B3%D1%83

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

Ну я с теорией не дружу %) Не знал, что это не возможно... %) С виду очень похоже на написание бота для игры... какого-нть лесоруба для УО, например =)
Ну, если не нужно, чтобы компутер сам решал как проложить маршрут - так мой код вполне рабочий, грузовик ездит, коробки возит =)

Да, вот интересно стало, а что нужно делать, если в програме допущена ошибка?
Ну, я так понял, что грузовик не может перевозить больше 1 коробки за раз, поэтому сразу не рассматривал возможность загрузить коробку если грузовик полный... Ну, или более простой вариант - "конечная станция" дает указание грузовику двигаться дальше (вникуда), что в таком случае делать? Насильно останавливать, выдавать сообщение об ошибке? Отправлять на начало? Програмно запретить задавать такую возможность?

Цитата:

Сообщение от wvxvw

Програмно запретить задавать такую возможность?

Скорее всего. И ещё есть возможность бесконечного цикла. поэтому нужна кнопка "стоп". и валидация на условия - чтобы пользователь не добавлял пустые и одинаковые условия.

Ок, кнопка стоп не проблема, а чем плохо одинаковые условия (вариантов условий не так уж много, при определенной длине цепочки они все равно повторятся - или мне опять лень считать =)?

ну а если на два одинаковых условия пользователь назначит две разные команды? Можно конечно просто ограничить список условий... Смотря какую цель перед собой ставит преподаватель. Ну и можно выдавать сообщения об ошбку если грузовик после последнего склада поехал дальше.
Вообще да. лучше не ограничивать - пусть ученики наступают на грабли. чем больше шишек набьют сейчас, тем проще будет им потом :)

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

Я предлагаю не делать проверок на непротиворечивость. Пусть грузовик читает по порядку, и то, что подходит будет выполнять. Проблема "программиста" будет наглядной, мне кажется.

Объясняю, что значит непротиворечивые условия(они могут быть все таки разными):
Пришел ребенок с работы и видит мамину инструкцию:

Если ты голоден съешь котлету.
Если дрался в школе не ешь котлету.

То что ты "не голоден" не противоречит тому, что ты "не дрался" а значит указания по этим условиям не должны, в принципе, различаться

Т.е. применительно к нашему случаю... может все-таки раздать условиям приоритеты?
Например: Если на станции нету коробок, но в путевом листе сказано, что коробку нужно забрать - приоритет = наличие коробок (очевидно).
Если грузовик загружен, а на станции сказано еще раз загрузится - приоритет у загруженности грузовика.

Тут помоему нигде не получается ситуации, когда бы можно было одновременно выполнить 2 условия... или мне кажется?
Т.е. если проверка чего делать на станции всегда осуществляется в такой последовательности:
- наличие коробок
- заргуженность грузовика
- предписания станции
то после этой проверки получится 0..1 вариантов действий
т.е. если первое = тру, второе = фолс, а третье соответствует описанной раньше ситуации - решение только одно, если не соответствует - решений нету.

Да, и еще такой момент, коробки - каждая уникальная, или могут быть взаимозаменимыми?

А, елки, дошло наконец %) На станции может быть несколько предписаний? Если так, то, конечно, зачем одинаковые дублировать? =)
И, да, тогда несколько условий на станции могут удовлетворять одной ситуации... ну, даж не знаю... проще всего, конечно, выбирать первое из списка... ну, или рандомально %)

Т.е. отобрать у пользователя возможность изначально задать для одной ситуации 2 варианта поведения: получится, что на станции может быть максимум 4 предписания
1. для случая когда грузовик не загружен & коробок нет
2. для случая когда грузовик загружен & коробок нет
3. для случая когда грузовик не загружен & есть коробки
4. для случая когда грузовик загружен & есть коробки
Добавить 5-е условие сделать технически невозможным...

Не, приоритеты расставлять наверное не стоит. просто условия читаются попорядку: если подходит - выполняется действие и те условия которые стоят ниже - игнорируются.
если ученик пытается увезти груз с пустой базы - выдавать ошибку.
Нагрузить нагруженый грузовик у ученика не получится(такое команды нет, есть команда уехать с грузом или без груза и уехать направо или на лево. Всё.).
PS: Вчера сделал дропдаун лист с картинками для выбора условий и команд. Сегодня буду делать чтото наподобие гридвью для добавления команд и условий(не хочу использовать стандартные контролы)

Хм... я немного по другому изначально все понял, млин, ок, ближе к вечеру передлаю...

Ничего не понятно в данной теме, но с нетерпением жду результата, видимо, что-то интересное творится.

А чем все кончилось то? :)

Хехех, я нубом был, нубом и остался :) Но могу взамен написать машину Поста - это все ж таки куда проще будет :)