Forth http://fforum.winglion.ru/ |
|
Решение задачи на Prolog'e http://fforum.winglion.ru/viewtopic.php?f=12&t=2704 |
Страница 2 из 2 |
Автор: | вопрос [ Вт фев 08, 2011 20:11 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
если найду способ подкрасить текст - прокомментирую просто полный перебор, результаты откладываются в 2 списка run_with_symbols( List , Symbols , Result, [[ Temp_value , [ _ , _ ] , _]] , Rresult, []) , синим - результат хороший, красным - результат который хуже Rresult = Rest result то, что не осталось в списке Result после сравнения подумаю, как раскрасить |
Автор: | вопрос [ Ср апр 13, 2011 20:42 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
Задача о кенгуру на прологе вот такое условие тут всё симметрично, но симметрия нарушена камушками, которые выделены в красный |
Автор: | вопрос [ Ср апр 13, 2011 20:43 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
решение задачи на Прологе для SWI обратив внимание на критику, там дальше размещаю комментарий, в комментарии я буду clauses называть "словами" - так привычнее фортерам, на самом деле это "правила" % решение задачи про нерешительного кенгуру путём полного перебора Условие лежит в списке, который лежит в статическом правиле stones может быть, стоило это сделать лучше, но какая разница это список списков вида stones( где каждый список – камень. Два слова run:- и runwx(Х) run with x построены одинаково, только первое начинает поск от 0,0 для второго можно ввести Х (т.к. Y всегда 0). run:- run забирает список из stones , и передаёт его слову stage (этап), само играя роль первого (предварительного) этапа. stage(Start_Len, Len, PosX, PosY, S_Array, Way) получает Start_Len – стартовая длина – длина, с которой начали Len – длина, с помощью которой допрыгнули до данного места PosX, PosY – данное место S_Array – оставшиеся непройденными камни Way – путь. stage совершает 2 попытки: end_possible и если нет, то след. stage end_possible(Len, PosX, PosY ) – возможно ли с этого камня прыгнуть на берег и, если это слово получает удачу: print_result(EndWay, Start_Len) – печатать результат, в последнее слово (это функция на самом деле) передаются EndWay – окончательный вариант пути и Start_Len – длина, с которой начали если этот end_possible терпит провал (не получается допрыгнуть до берега), вызывается jump_possible(Len, PosX, PosY , S_Array, TEMP, ResArray) который возвращает список доступных для данной длины предыдущего прыжка камней т.е. мы уже не пробуем допрыгнуть до берега, а пытаемся найти другой каменъ. TEMP – служебный список, ResArray – список доступных камней, то, ради чего вызывается слово. При вызове ResArray – неопределён и получает своё значение из TEMP в конце перебора. следующие за вызовом jump_possible строки подготавливают следующий этап – новый вызов stage со «следующими» данными. jump_possible(Len, PosX, PosY , S_Array, [], ResArray), one_of_array(ResArray, One) изымает один из камней из ResArray – ведь это список доступных и этот список нужно перебрать по одному. same_one_of_array(S_Array, Part_of_One, New_S_Array), - изымает такой же камень из S_Array – ведь, когда мы на него прыгнем, он станет «пройденным» и не будет смысла на него вновь прыгать NewWay = [ [ C, D ] | Way ] - этот камень добавляется в путь. новый рекурсивный вызов stage (получается – следующий этап) получает Start_Len – стартовую длину – неизменной Nlen – длину, которая на новом этапе будет предыдущей – из списка, сформированного jump_possible – это тоже список списков, в кот. входит и длина. чтобы не вычислять ещё лишний раз C, D - координаты нового камня New_S_Array, - список непройденных камней без этого последнего камушка NewWay – путь с этим последним камнем если мы взглянем на «слово» run, то увидим, что от «слова» stage оно отличается только отсутствием попытки закончить перебор end_possible и наличием факта получения условий. Фактически ветвление (перебор) осуществляет one_of_array – получив список камней доступных при данной длине из данного пункта, оно (слово) выдаёт по одному все доступные; для каждого этапа (для каждого вызова stage) формируется свой список ResArray, который для других этапов не важен и с ним работает только слово one_of_array one_of_array(ResArray, One):- получив ResArray, он выдаёт много раз One – один камень в конце каждой успешной попытки находится fail, чтобы "попросить" ещё одну успешную попытку К сожалению, при большом количестве камней полный перебор очень долог. При небольшом - нет. Список, который "путь" в конце печатается так как сформирован - т.е. последние прыжки - слева. |
Автор: | : AL/M ; [ Ср апр 13, 2011 21:52 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
непонятно как пользоваться вашей прогой. по запросу runwx(15.6) получил кучу сообщений вроде "for start-length 17.3367 the way is [[19, 25], [19, 17]]" -- как это понимать? Как узнать путь для конкретной длины прыжка? И еще: у вас предполагается что кенгуру идет снизу вверх или слева направо? как только разберусь с этим проверю и выложу своё решение на питоне P.S. предлагаю все решения выкладывать в исходную тему независимо от языка, либо по крайней мере для каждой задачи заводить отдельную тему для не-форт решений |
Автор: | вопрос [ Ср апр 13, 2011 22:40 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
: AL/M ; писал(а): непонятно как пользоваться вашей прогой. по запросу runwx(15.6) получил кучу сообщений вроде "for start-length 17.3367 the way is [[19, 25], [19, 17]]" -- как это понимать? Как узнать путь для конкретной длины прыжка? И еще: у вас предполагается что кенгуру идет снизу вверх или слева направо? как только разберусь с этим выложу своё решение на питоне P.S. предлагаю все решения выкладывать в исходную тему независимо от языка, либо по крайней мере для каждой задачи заводить отдельную тему для не-форт решений Всё правильно, чтобы не разрушать интригу это Проложное решение несовершенно - оно ищет ВСЕ решения, среди них нужно выбрать правильное вручную. Кстати, почему runwx(15.6) , старт с первой горизонтали должен быть целым runwx(15) таким образом окончательным решением оно пока не есть путь кенгуру - снизувверх Цитата: for start-length 17.3367 означало бы "для обнаруженной возможной длины первого прыжка 17.3367"
|
Автор: | : AL/M ; [ Ср апр 13, 2011 22:57 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
вопрос писал(а): Кстати, почему runwx(15.6) , старт с первой горизонтали должен быть целым runwx(15) под 15.6 я подразумевал ограничение максимальной длины прыжка. а почему он должен быть целым? |
Автор: | вопрос [ Ср апр 13, 2011 23:03 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
таково условие задачи (иначе её нельзя было бы решить в целых числах, но не только) - камни - в узлах решётки runwx(15) подразумевает "стартовать с Х = 15, У = 0" У = 0 - это берег, У = 25 - другой берег, а Х - в узлах решётки runwithx |
Автор: | вопрос [ Чт апр 14, 2011 18:03 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
Кстати, да. Пролог на то и Prolog, что ограничение максимальной длины можно двумя буквами runwml(A):- A < 25, A >= 0, runwml - старт с 0,0 (цветом выделл) но с максимальной дланой А - теперь А - макс. длина, как хотелосъ runwxwml старт с А , 0 максим. длина L Добавив эти слова в код, можно уменьшить макс. длину |
Автор: | вопрос [ Чт апр 14, 2011 18:08 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
Запросив runwxwml(18,14). старт 18 0 мак. длина 14 ?- runwxwml(18,14). |
Страница 2 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |