Автор |
Сообщение |
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
Запросив runwxwml(18,14). старт 18 0 мак. длина 14 ?- runwxwml(18,14). for start-length 13.8924 the way is [[21, 25], [21, 21], [18, 16], [17, 8], [6, 7]] for start-length 13.8924 the way is [[19, 25], [19, 21], [18, 16], [17, 8], [6, 7]] for start-length 13.8924 the way is [[17, 25], [17, 21], [18, 16], [17, 8], [6, 7]] for start-length 13.8924 the way is [[15, 25], [15, 21], [18, 16], [17, 8], [6, 7]] for start-length 9 the way is [[19, 25], [19, 21], [18, 16], [18, 9]] for start-length 9 the way is [[17, 25], [17, 21], [18, 16], [18, 9]] for start-length 12.083 the way is [[23, 25], [23, 21], [19, 17], [23, 11]] for start-length 12.083 the way is [[15, 25], [15, 21], [19, 17], [23, 11]] for start-length 12.083 the way is [[19, 25], [19, 21], [18, 16], [23, 11]] for start-length 12.083 the way is [[17, 25], [17, 21], [18, 16], [23, 11]] for start-length 12.53 the way is [[23, 25], [23, 21], [19, 17], [12, 11]] for start-length 12.53 the way is [[15, 25], [15, 21], [19, 17], [12, 11]] for start-length 12.53 the way is [[13, 25], [13, 21], [19, 17], [12, 11]] for start-length 12.53 the way is [[21, 25], [21, 21], [19, 15], [12, 11]] for start-length 12.53 the way is [[19, 25], [19, 21], [19, 15], [12, 11]] for start-length 12.53 the way is [[17, 25], [17, 21], [19, 15], [12, 11]] for start-length 12.53 the way is [[21, 25], [21, 21], [18, 16], [12, 11]] for start-length 12.53 the way is [[19, 25], [19, 21], [18, 16], [12, 11]] for start-length 12.53 the way is [[17, 25], [17, 21], [18, 16], [12, 11]] for start-length 12.53 the way is [[15, 25], [15, 21], [18, 16], [12, 11]] for start-length 12.3693 the way is [[23, 25], [23, 21], [21, 12]] for start-length 12.3693 the way is [[21, 25], [21, 21], [21, 12]] for start-length 12.3693 the way is [[19, 25], [19, 21], [21, 12]] for start-length 12.3693 the way is [[17, 25], [17, 21], [21, 12]] for start-length 13.1529 the way is [[21, 25], [21, 21], [16, 13]] for start-length 13.1529 the way is [[19, 25], [19, 21], [16, 13]] for start-length 13.1529 the way is [[17, 25], [17, 21], [16, 13]] for start-length 13.1529 the way is [[15, 25], [15, 21], [16, 13]] for start-length 13.1529 the way is [[13, 25], [13, 21], [16, 13]] for start-length 13.1529 the way is [[11, 25], [11, 21], [16, 13]] end of search
Запросив runwxwml(18,14). старт 18 0 мак. длина 14 [pre][b] ?- runwxwml(18,14).[/b] for start-length 13.8924 the way is [[21, 25], [21, 21], [18, 16], [17, 8], [6, 7]] for start-length 13.8924 the way is [[19, 25], [19, 21], [18, 16], [17, 8], [6, 7]] for start-length 13.8924 the way is [[17, 25], [17, 21], [18, 16], [17, 8], [6, 7]] for start-length 13.8924 the way is [[15, 25], [15, 21], [18, 16], [17, 8], [6, 7]] for start-length[b][color=#FF0040] 9 [/color][/b]the way is [[19, 25], [19, 21], [18, 16], [18, 9]] for start-length[b][color=#FF0000] 9 [/color][/b]the way is [[17, 25], [17, 21], [18, 16], [18, 9]] for start-length 12.083 the way is [[23, 25], [23, 21], [19, 17], [23, 11]] for start-length 12.083 the way is [[15, 25], [15, 21], [19, 17], [23, 11]] for start-length 12.083 the way is [[19, 25], [19, 21], [18, 16], [23, 11]] for start-length 12.083 the way is [[17, 25], [17, 21], [18, 16], [23, 11]] for start-length 12.53 the way is [[23, 25], [23, 21], [19, 17], [12, 11]] for start-length 12.53 the way is [[15, 25], [15, 21], [19, 17], [12, 11]] for start-length 12.53 the way is [[13, 25], [13, 21], [19, 17], [12, 11]] for start-length 12.53 the way is [[21, 25], [21, 21], [19, 15], [12, 11]] for start-length 12.53 the way is [[19, 25], [19, 21], [19, 15], [12, 11]] for start-length 12.53 the way is [[17, 25], [17, 21], [19, 15], [12, 11]] for start-length 12.53 the way is [[21, 25], [21, 21], [18, 16], [12, 11]] for start-length 12.53 the way is [[19, 25], [19, 21], [18, 16], [12, 11]] for start-length 12.53 the way is [[17, 25], [17, 21], [18, 16], [12, 11]] for start-length 12.53 the way is [[15, 25], [15, 21], [18, 16], [12, 11]] for start-length 12.3693 the way is [[23, 25], [23, 21], [21, 12]] for start-length 12.3693 the way is [[21, 25], [21, 21], [21, 12]] for start-length 12.3693 the way is [[19, 25], [19, 21], [21, 12]] for start-length 12.3693 the way is [[17, 25], [17, 21], [21, 12]] for start-length 13.1529 the way is [[21, 25], [21, 21], [16, 13]] for start-length 13.1529 the way is [[19, 25], [19, 21], [16, 13]] for start-length 13.1529 the way is [[17, 25], [17, 21], [16, 13]] for start-length 13.1529 the way is [[15, 25], [15, 21], [16, 13]] for start-length 13.1529 the way is [[13, 25], [13, 21], [16, 13]] for start-length 13.1529 the way is [[11, 25], [11, 21], [16, 13]] end of search[/pre]
|
|
|
|
Добавлено: Чт апр 14, 2011 18:08 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
Кстати, да. Пролог на то и Prolog, что ограничение максимальной длины можно двумя буквами runwml(A):- A < 25, A >= 0, stones(S_Array), B is A * 1.25, jump_possible(B, 0, 0 , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search').
runwxwml(A,L):- A < 25, A >= 0, L < 25, L >= 0, stones(S_Array), B is L * 1.25, jump_possible(B, A, 0 , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search'). runwml - старт с 0,0 (цветом выделл) но с максимальной дланой А - теперь А - макс. длина, как хотелосъ runwxwml старт с А , 0 максим. длина L Добавив эти слова в код, можно уменьшить макс. длину
Кстати, да. Пролог на то и Prolog, что ограничение максимальной длины можно двумя буквами
[pre]runwml(A):- A < 25, A >= 0, stones(S_Array), B is A * 1.25, jump_possible(B, [color=#BF00FF][b]0, 0 [/b][/color], S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search').
runwxwml(A,L):- A < 25, A >= 0, L < 25, L >= 0, stones(S_Array), B is[color=#FF0000] L[/color] * 1.25, jump_possible(B, [color=#8000FF][b]A, 0 [/b][/color], S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search').[/pre] runwml - старт с[color=#BF00FF][b] 0,0 [/b][/color](цветом выделл) но с максимальной дланой А - теперь А - макс. длина, как хотелосъ
runwxwml старт с[color=#8000FF][b] А , 0[/b][/color] максим. длина [color=#FF0000]L[/color] Добавив эти слова в код, можно уменьшить макс. длину
|
|
|
|
Добавлено: Чт апр 14, 2011 18:03 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
таково условие задачи (иначе её нельзя было бы решить в целых числах, но не только) - камни - в узлах решётки runwx(15) подразумевает "стартовать с Х = 15, У = 0" У = 0 - это берег, У = 25 - другой берег, а Х - в узлах решётки
runwithx
таково условие задачи (иначе её нельзя было бы решить в целых числах, но не только) - камни - в узлах решётки runwx(15) подразумевает "стартовать с Х = 15, У = 0" У = 0 - это берег, У = 25 - другой берег, а Х - в узлах решётки
run[b]w[/b][color=#FF0000]ith[/color][b]x[/b]
|
|
|
|
Добавлено: Ср апр 13, 2011 23:03 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
вопрос писал(а): Кстати, почему runwx(15.6) , старт с первой горизонтали должен быть целым runwx(15) под 15.6 я подразумевал ограничение максимальной длины прыжка. а почему он должен быть целым?
[quote="вопрос"] Кстати, почему runwx(15.6) , старт с первой горизонтали должен быть целым runwx(15)[/quote] под 15.6 я подразумевал ограничение максимальной длины прыжка. а почему он должен быть целым?
|
|
|
|
Добавлено: Ср апр 13, 2011 22:57 |
|
|
|
|
|
Заголовок сообщения: |
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"
[quote=": AL/M ;"]непонятно как пользоваться вашей прогой. по запросу runwx(15.6) получил кучу сообщений вроде "for start-length 17.3367 the way is [[19, 25], [19, 17]]" -- как это понимать? Как узнать путь для конкретной длины прыжка? И еще: у вас предполагается что кенгуру идет снизу вверх или слева направо?
как только разберусь с этим выложу своё решение на питоне
P.S. предлагаю все решения выкладывать в исходную тему независимо от языка, либо по крайней мере для каждой задачи заводить отдельную тему для не-форт решений[/quote]
Всё правильно, чтобы не разрушать интригу это Проложное решение несовершенно - оно ищет ВСЕ решения, среди них нужно выбрать правильное вручную. Кстати, почему runwx(15.6) , старт с первой горизонтали должен быть целым runwx(15) таким образом окончательным решением оно пока не есть
путь кенгуру - снизувверх [quote]for start-length 17.3367[/quote] означало бы "для обнаруженной возможной длины первого прыжка 17.3367"
|
|
|
|
Добавлено: Ср апр 13, 2011 22:40 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
непонятно как пользоваться вашей прогой. по запросу runwx(15.6) получил кучу сообщений вроде "for start-length 17.3367 the way is [[19, 25], [19, 17]]" -- как это понимать? Как узнать путь для конкретной длины прыжка? И еще: у вас предполагается что кенгуру идет снизу вверх или слева направо?
как только разберусь с этим проверю и выложу своё решение на питоне
P.S. предлагаю все решения выкладывать в исходную тему независимо от языка, либо по крайней мере для каждой задачи заводить отдельную тему для не-форт решений
непонятно как пользоваться вашей прогой. по запросу runwx(15.6) получил кучу сообщений вроде "for start-length 17.3367 the way is [[19, 25], [19, 17]]" -- как это понимать? Как узнать путь для конкретной длины прыжка? И еще: у вас предполагается что кенгуру идет снизу вверх или слева направо?
как только разберусь с этим проверю и выложу своё решение на питоне
P.S. предлагаю все решения выкладывать в исходную тему независимо от языка, либо по крайней мере для каждой задачи заводить отдельную тему для не-форт решений
|
|
|
|
Добавлено: Ср апр 13, 2011 21:52 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
решение задачи на Прологе для SWI обратив внимание на критику, там дальше размещаю комментарий, в комментарии я буду clauses называть "словами" - так привычнее фортерам, на самом деле это "правила" % решение задачи про нерешительного кенгуру путём полного перебора % без эвристики % это не тот список камней, который приведен в условии задачи
stones( [ [1,21], [3,21], [5,21], [7,21], [9,21], [11,21], [13,21], [15,21], [17,21], [19,21], [21,21], [23,21], [8,13], [16,13], [3,12], [21,12], [12,11], [1,11], [23,11], [6,9], [18,9], [6,7], [18,7], [17,8], [0,3], [2,3], [4,3], [6,3], [8,3], [10,3], [12,3], [14,3], [16,3], [18,3], [20,3], [22,3], [18,16], [19,15], [19,17], [24,3] ] ).
print_result(EndWay, Start_Len):- write('for start-length '), write(Start_Len), write(' the way is '), write(EndWay), nl, fail.
jump_possible(Len, PosX, PosY , S_Array, TEMP, ResArray) :- S_Array = [], ResArray = TEMP. jump_possible(Len, PosX, PosY , S_Array, TEMP, ResArray) :- S_Array = [ A | B ] , P_Len is Len * 0.8 , A = [ C , D ] , F_Len is sqrt( (C-PosX) ** 2 + (D-PosY) ** 2 ) , ( P_Len >= F_Len -> TEMP2 = [ [ F_Len , C , D ] | TEMP ] , jump_possible(Len, PosX, PosY , B , TEMP2, ResArray) ; jump_possible(Len, PosX, PosY , B , TEMP, ResArray) ) . end_possible(Len, PosX, PosY ):- End_Len is 25 - PosY , P_Len is Len * 0.8 , P_Len >= End_Len.
one_of_array(ResArray, One):- ResArray = [ C | D ] , One = C ; ResArray = [ C | D ] , one_of_array( D, One).
same_one_of_array(ResArray, One, New_ResArray):- ResArray = [ C | D ] , One = C -> New_ResArray = D ; ResArray = [ C | D ] , New_ResArray = [ C | F ], same_one_of_array( D, One, F).
stage(Start_Len, Len, PosX, PosY, S_Array, Way) :- S_Array = [ A | B ] , ( end_possible(Len, PosX, PosY ) -> EndX is PosX, EndY is 25, EndWay = [ [ EndX, EndY ] | Way ] , print_result(EndWay, Start_Len) ; jump_possible(Len, PosX, PosY , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , Part_of_One = [ C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] | Way ] , stage(Start_Len, NLen, C, D , New_S_Array, NewWay) ) . run:- stones(S_Array), jump_possible(30, 0, 0 , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search'). runwx(A):- A < 25, A >= 0, stones(S_Array), jump_possible(30, A, 0 , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search'). Условие лежит в списке, который лежит в статическом правиле stonesможет быть, стоило это сделать лучше, но какая разница это список списков вида stones( [ [1,21], ... [24,3] ] ). где каждый список – камень. Два слова run:- и runwx(Х) run with xпостроены одинаково, только первое начинает поск от 0,0 для второго можно ввести Х (т.к. Y всегда 0). run:- stones(S_Array), jump_possible(30, 0, 0 , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search'). 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), One = [ NLen , C , D ] , Part_of_One = [ C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] | Way ] , stage(Start_Len, NLen, C, D , New_S_Array, NewWay) 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_arrayone_of_array(ResArray, One):- ResArray = [ C | D ] , One = C ; ResArray = [ C | D ] , one_of_array( D, One, F). получив ResArray, он выдаёт много раз One – один камень в конце каждой успешной попытки находится fail, чтобы "попросить" ещё одну успешную попытку К сожалению, при большом количестве камней полный перебор очень долог. При небольшом - нет. Список, который "путь" в конце печатается так как сформирован - т.е. последние прыжки - слева.
решение задачи на Прологе для SWI обратив внимание на критику, там дальше размещаю комментарий, в комментарии я буду clauses называть "словами" - так привычнее фортерам, на самом деле это "правила"
[pre]% решение задачи про нерешительного кенгуру путём полного перебора % без эвристики % это не тот список камней, который приведен в условии задачи
stones( [ [1,21], [3,21], [5,21], [7,21], [9,21], [11,21], [13,21], [15,21], [17,21], [19,21], [21,21], [23,21], [8,13], [16,13], [3,12], [21,12], [12,11], [1,11], [23,11], [6,9], [18,9], [6,7], [18,7], [17,8], [0,3], [2,3], [4,3], [6,3], [8,3], [10,3], [12,3], [14,3], [16,3], [18,3], [20,3], [22,3], [18,16], [19,15], [19,17], [24,3] ] ).
print_result(EndWay, Start_Len):- write('for start-length '), write(Start_Len), write(' the way is '), write(EndWay), nl, fail.
jump_possible(Len, PosX, PosY , S_Array, TEMP, ResArray) :- S_Array = [], ResArray = TEMP. jump_possible(Len, PosX, PosY , S_Array, TEMP, ResArray) :- S_Array = [ A | B ] , P_Len is Len * 0.8 , A = [ C , D ] , F_Len is sqrt( (C-PosX) ** 2 + (D-PosY) ** 2 ) , ( P_Len >= F_Len -> TEMP2 = [ [ F_Len , C , D ] | TEMP ] , jump_possible(Len, PosX, PosY , B , TEMP2, ResArray) ; jump_possible(Len, PosX, PosY , B , TEMP, ResArray) ) . end_possible(Len, PosX, PosY ):- End_Len is 25 - PosY , P_Len is Len * 0.8 , P_Len >= End_Len.
one_of_array(ResArray, One):- ResArray = [ C | D ] , One = C ; ResArray = [ C | D ] , one_of_array( D, One).
same_one_of_array(ResArray, One, New_ResArray):- ResArray = [ C | D ] , One = C -> New_ResArray = D ; ResArray = [ C | D ] , New_ResArray = [ C | F ], same_one_of_array( D, One, F).
stage(Start_Len, Len, PosX, PosY, S_Array, Way) :- S_Array = [ A | B ] , ( end_possible(Len, PosX, PosY ) -> EndX is PosX, EndY is 25, EndWay = [ [ EndX, EndY ] | Way ] , print_result(EndWay, Start_Len) ; jump_possible(Len, PosX, PosY , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , Part_of_One = [ C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] | Way ] , stage(Start_Len, NLen, C, D , New_S_Array, NewWay) ) . run:- stones(S_Array), jump_possible(30, 0, 0 , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search'). runwx(A):- A < 25, A >= 0, stones(S_Array), jump_possible(30, A, 0 , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search').[/pre]
Условие лежит в списке, который лежит в статическом правиле [b]stones[/b] может быть, стоило это сделать лучше, но какая разница это список списков вида [pre][b]stones[/b]( [ [1,21], ... [24,3] ] ).[/pre] где каждый список – камень.
Два слова [b]run[/b]:- и [b]runwx(Х)[/b] [color=#FF00BF]run with x[/color] построены одинаково, только первое начинает поск от 0,0 для второго можно ввести Х (т.к. Y всегда 0). [pre]run:- stones(S_Array), jump_possible(30, 0, 0 , S_Array, [], ResArray), one_of_array(ResArray, One), One = [ NLen , C , D ] , same_one_of_array(S_Array, Part_of_One, New_S_Array), NewWay = [ [ C, D ] ] , stage(NLen, NLen, C, D , New_S_Array, NewWay); write('end of search').[/pre] [b]run[/b] забирает список из stones , и передаёт его слову stage (этап), само играя роль первого (предварительного) этапа. [b]stage([color=#BF00FF]Start_Len[/color], [color=#8080BF]Len[/color], [color=#BF0040]PosX, PosY,[/color] [color=#FF00FF]S_Array[/color], Way)[/b] получает
[b][color=#BF00FF]Start_Len[/color][/b] – стартовая длина – длина, с которой начали [b][color=#8080BF]Len[/color][/b] – длина, с помощью которой допрыгнули до данного места [b][color=#BF0040]PosX, PosY[/color] – данное место [color=#FF00FF]S_Array[/color][/b] – оставшиеся непройденными камни [b]Way[/b] – путь.
stage совершает 2 попытки: end_possible и если нет, то след. stage
[b]end_possible[/b](Len, PosX, PosY ) – возможно ли с этого камня прыгнуть на берег и, если это слово получает удачу: [b]print_result[/b](EndWay, Start_Len) – печатать результат, в последнее слово (это функция на самом деле) передаются [b]EndWay[/b] – окончательный вариант пути и [b]Start_Len[/b] – длина, с которой начали если этот [b]end_possible[/b] терпит провал (не получается допрыгнуть до берега), вызывается [b]jump_possible[/b](Len, PosX, PosY , S_Array, TEMP, ResArray) который возвращает список доступных для данной длины предыдущего прыжка камней т.е. мы уже не пробуем допрыгнуть до берега, а пытаемся найти другой каменъ. [b]TEMP[/b] – служебный список, [b]ResArray[/b] – список доступных камней, то, ради чего вызывается слово. При вызове [b]ResArray[/b] – неопределён и получает своё значение из TEMP в конце перебора. следующие за вызовом [b]jump_possible[/b] строки подготавливают следующий этап – новый вызов [b]stage[/b] со «следующими» данными.
[pre][b]jump_possible(Len, PosX, PosY , S_Array, [], ResArray), [color=#BF00FF]one_of_array(ResArray, One),[/color] One = [ NLen , C , D ] , Part_of_One = [ C , D ] , [color=#BF0040]same_one_of_array(S_Array, Part_of_One, New_S_Array),[/color] [color=#804080]NewWay = [ [ C, D ] | Way ] [/color], stage(Start_Len, NLen, C, D , New_S_Array, NewWay)[/b][/pre] [b][color=#BF00FF]one_of_array(ResArray, One)[/color][/b] изымает один из камней из ResArray – ведь это список доступных и этот список нужно перебрать по одному. [b][color=#BF0040]same_one_of_array(S_Array, Part_of_One, New_S_Array)[/color][/b], - изымает такой же камень из S_Array – ведь, когда мы на него прыгнем, он станет «пройденным» и не будет смысла на него вновь прыгать [b][color=#804080]NewWay = [ [ C, D ] | Way ][/color][/b] - этот камень добавляется в путь. новый рекурсивный вызов stage (получается – следующий этап) получает [b]Start_Len[/b] – стартовую длину – неизменной [b]Nlen[/b] – длину, которая на новом этапе будет предыдущей – из списка, сформированного jump_possible – это тоже список списков, в кот. входит и длина. чтобы не вычислять ещё лишний раз [b]C, D [/b] - координаты нового камня [b]New_S_Array[/b], - список непройденных камней без этого последнего камушка [b]NewWay[/b] – путь с этим последним камнем
если мы взглянем на «слово» [b]run[/b], то увидим, что от «слова» [b]stage[/b] оно отличается только отсутствием попытки закончить перебор [b]end_possible[/b] и наличием факта получения условий.
Фактически ветвление (перебор) осуществляет [b]one_of_array[/b] – получив список камней доступных при данной длине из данного пункта, оно (слово) выдаёт по одному все доступные; для каждого этапа (для каждого вызова [b]stage[/b]) формируется свой список [b]ResArray[/b], который для других этапов не важен и с ним работает только слово [b]one_of_array[/b]
[pre]one_of_array(ResArray, One):- ResArray = [ C | D ] , One = C ; ResArray = [ C | D ] , one_of_array( D, One, F).[/pre] получив ResArray, он выдаёт много раз [b]One[/b] – один камень
в конце каждой успешной попытки находится fail, чтобы "попросить" ещё одну успешную попытку
К сожалению, при большом количестве камней полный перебор очень долог. При небольшом - нет. Список, который "путь" в конце печатается так как сформирован - т.е. последние прыжки - слева.
|
|
|
|
Добавлено: Ср апр 13, 2011 20:43 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
Задача о кенгуру на прологе вот такое условие тут всё симметрично, но симметрия нарушена камушками, которые выделены в красный
Задача о кенгуру на прологе вот такое условие [img]http://s47.radikal.ru/i116/1104/8f/8ddeb5039f3c.png[/img] тут всё симметрично, но симметрия нарушена камушками, которые выделены в красный
|
|
|
|
Добавлено: Ср апр 13, 2011 20:42 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
если найду способ подкрасить текст - прокомментирую просто полный перебор, результаты откладываются в 2 списка
run_with_symbols( List , Symbols , Result, [[ Temp_value , [ _ , _ ] , _]] , Rresult, []) ,
синим - результат хороший, красным - результат который хуже Rresult = Rest result то, что не осталось в списке Result после сравнения
подумаю, как раскрасить
если найду способ подкрасить текст - прокомментирую просто полный перебор, результаты откладываются в 2 списка
run_with_symbols( List , Symbols , [color=#8040BF]Result[/color], [color=#8000FF][b][[ Temp_value , [ _ , _ ] , _]][/b][/color] , [color=#FF0000]Rresult[/color], [color=#BF0000][b][][/b][/color]) ,
синим - результат хороший, красным - результат который хуже Rresult = Rest result то, что не осталось в списке Result после сравнения
подумаю, как раскрасить
|
|
|
|
Добавлено: Вт фев 08, 2011 20:11 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
спасибо а не могли бы вы рассказать про свой алгоритм?
спасибо а не могли бы вы рассказать про свой алгоритм?
|
|
|
|
Добавлено: Вт фев 08, 2011 19:59 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
Да. это решение более изящное Моё могло б похвастать в сравнении с этим только более информативным выводом (это нужно было для проверки решений задачи на форте)
Да. это решение более изящное :) :idea:
Моё могло б похвастать в сравнении с этим только более информативным выводом :) (это нужно было для проверки решений задачи на форте)
|
|
|
|
Добавлено: Вт фев 08, 2011 19:14 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
вот по-моему решение попроще (SWI-Prolog) входная строка задается атомом, which_char/1 -- для печати сразу всех решений which_char/2 -- для перебора по одному :- dynamic pair/3.
which_char(S) :- setof(C, which_char(S, C), Cs), repeat, ( member(X,Cs), print(X), nl, fail; true ). which_char(S, C) :-
cleanup, name(S, L), collect_pairs(L), min_max(L, Code), name(C, [Code]).
cleanup :- retractall(pair(_,_,_)).
min_max(L, Code) :- maxes(L, Ms), min(Ms, Code).
maxes(L, Ms) :- setof( (C, M), ( member(C, L), max(C, M) ), Ms ).
max(C, M) :- max(C, M, 0). max(C, M, N) :- pair(X, Y, K), X \= C, Y \= C, K > N, !, max(C, M, K). max(_, M, M).
min([T| L], Code) :- min(L, T, (Code, _)). min([], M, M). min([ (C, N) | L ], (C1, N1), M) :- N = N1, % (проверка на равенство -- для поиска всех решений) ( min( L, (C1, N1), M ) ; min( L, (C, N), M )). min([ (C, N) | L ], (_, N1), M) :- N < N1, !, min( L, (C, N), M ). min([ _ | L ], T, M) :- min(L, T, M).
collect_pairs([X, Y| L]) :-
pair(X, Y, N), !, N1 is N + 1, retract(pair(X, Y, N)), assert(pair(X, Y, N1)), collect_pairs([Y| L]).
collect_pairs([X, Y| L]) :-
assert(pair(X, Y, 0)), collect_pairs([Y| L]).
collect_pairs(_).
вот по-моему решение попроще (SWI-Prolog) входная строка задается атомом, [color=#0040BF]which_char/1[/color] -- для печати сразу всех решений [color=#0040BF]which_char/2[/color] -- для перебора по одному
[pre]:- dynamic pair/3.
which_char(S) :- setof(C, which_char(S, C), Cs), repeat, ( member(X,Cs), print(X), nl, fail; true ). which_char(S, C) :-
cleanup, name(S, L), collect_pairs(L), min_max(L, Code), name(C, [Code]).
cleanup :- retractall(pair(_,_,_)).
min_max(L, Code) :- maxes(L, Ms), min(Ms, Code).
maxes(L, Ms) :- setof( (C, M), ( member(C, L), max(C, M) ), Ms ).
max(C, M) :- max(C, M, 0). max(C, M, N) :- pair(X, Y, K), X \= C, Y \= C, K > N, !, max(C, M, K). max(_, M, M).
min([T| L], Code) :- min(L, T, (Code, _)). min([], M, M). min([ (C, N) | L ], (C1, N1), M) :- N = N1, [color=#008000]% (проверка на равенство -- для поиска [b]всех[/b] решений)[/color] ( min( L, (C1, N1), M ) ; min( L, (C, N), M )). min([ (C, N) | L ], (_, N1), M) :- N < N1, !, min( L, (C, N), M ). min([ _ | L ], T, M) :- min(L, T, M).
collect_pairs([X, Y| L]) :-
pair(X, Y, N), !, N1 is N + 1, retract(pair(X, Y, N)), assert(pair(X, Y, N1)), collect_pairs([Y| L]).
collect_pairs([X, Y| L]) :-
assert(pair(X, Y, 0)), collect_pairs([Y| L]).
collect_pairs(_).[/pre]
|
|
|
|
Добавлено: Вт фев 08, 2011 17:35 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
Хм, я не знаю, как комментировать? Вообще, например member в SWI или GNU Prolog это встроенный предикат и в исходном тексте он там есть. так же как reverse и append Да, это всё хорошо, несомненно. Это решение было для того, чтобы можно было запустить и проверить правильность решения задачи на Forth или Euphoria a не для того. чтобы демонстрировать возможности Prolog'a В любом случае я рад, что Prolog стал предметом обсуждения.
Хм, я не знаю, как комментировать? Вообще, например member в SWI или GNU Prolog это встроенный предикат и в исходном тексте он там есть. так же как reverse и append
Да, это всё хорошо, несомненно.
Это решение было для того, чтобы можно было запустить и проверить правильность решения задачи на Forth или Euphoria a не для того. чтобы демонстрировать возможности Prolog'a
В любом случае я рад, что Prolog стал предметом обсуждения. :)
|
|
|
|
Добавлено: Сб фев 05, 2011 16:58 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
Вот первый пример сопоставление списка списков с простым списком можно применить для получения возможных комбинаций последовательноси входных символов. Вызов предиката p([X,_],[1,2,3,4]) для инициализации значений путем сопоставления даст результаты Код: p([X,_],[1,2,3,4]). X = [] ; X = [1] ; X = [1, 2] ; X = [1, 2, 3] ; X = [1, 2, 3, 4] ; false. Дальше можно начальный список повернуть на один элемент влево (взять из последнего примера предикат shiftl) и повторить получения значений. Для удобства еще операторы bagof и findall существуют. И представление данных - возможные наборы разделителй и число их появлений связать термом вида список/число вхождений.
Вот первый пример сопоставление списка списков с простым списком можно применить для получения возможных комбинаций последовательноси входных символов. Вызов предиката p([X,_],[1,2,3,4]) для инициализации значений путем сопоставления даст результаты [code]p([X,_],[1,2,3,4]). X = [] ; X = [1] ; X = [1, 2] ; X = [1, 2, 3] ; X = [1, 2, 3, 4] ; false.[/code] Дальше можно начальный список повернуть на один элемент влево (взять из последнего примера предикат shiftl) и повторить получения значений. Для удобства еще операторы bagof и findall существуют. И представление данных - возможные наборы разделителй и число их появлений связать термом вида [b]список/число вхождений[/b].
|
|
|
|
Добавлено: Сб фев 05, 2011 15:43 |
|
|
|
|
|
Заголовок сообщения: |
Re: Решение задачи на Prolog'e |
|
|
вопрос писал(а): Интересно, к чему это подсказки? Ну может программа попроще станет, чем она в самом первом посту темы Просто мне лень в чужом коде копаться когда нет алгоритма оформленного отдельно. Иногда неясно что хочет автор особенно обращаю внимание на множестов отсечений !. применение точек с запятой в Прологе приводит к непониманию особенно больших последовательностей преобразований, - лучше лишнее определение написать, скорость от этог не изменится
[quote="вопрос"]Интересно, к чему это подсказки?[/quote] Ну может программа попроще станет, чем она в самом первом посту темы :shuffle;
Просто мне лень в чужом коде копаться когда нет алгоритма оформленного отдельно. Иногда неясно что хочет автор особенно обращаю внимание на множестов отсечений !. применение точек с запятой в Прологе приводит к непониманию особенно больших последовательностей преобразований, - лучше лишнее определение написать, скорость от этог не изменится
|
|
|
|
Добавлено: Сб фев 05, 2011 14:50 |
|
|
|
|