Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 18:45

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Вт фев 08, 2011 20:11 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
если найду способ подкрасить текст - прокомментирую
просто полный перебор, результаты откладываются в 2 списка


run_with_symbols( List , Symbols , Result, [[ Temp_value , [ _ , _ ] , _]] , Rresult, []) ,

синим - результат хороший, красным - результат который хуже Rresult = Rest result
то, что не осталось в списке Result после сравнения

подумаю, как раскрасить


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Ср апр 13, 2011 20:42 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Задача о кенгуру на прологе
вот такое условие
Изображение
тут всё симметрично, но симметрия нарушена камушками, которые выделены в красный


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Ср апр 13, 2011 20:43 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
решение задачи на Прологе для 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_array

one_of_array(ResArray, One):- 
ResArray = [ C | D ] , One = C
;
ResArray = [ C | D ] ,
one_of_array( D, One, F).

получив ResArray, он выдаёт много раз One – один камень

в конце каждой успешной попытки находится fail, чтобы "попросить" ещё одну успешную попытку

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Ср апр 13, 2011 21:52 
Не в сети

Зарегистрирован: Вт фев 08, 2011 07:15
Сообщения: 18
Откуда: Беларусь
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
непонятно как пользоваться вашей прогой. по запросу runwx(15.6) получил кучу сообщений вроде "for start-length 17.3367 the way is [[19, 25], [19, 17]]" -- как это понимать? Как узнать путь для конкретной длины прыжка? И еще: у вас предполагается что кенгуру идет снизу вверх или слева направо?

как только разберусь с этим проверю и выложу своё решение на питоне

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Ср апр 13, 2011 22:40 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
: 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"


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Ср апр 13, 2011 22:57 
Не в сети

Зарегистрирован: Вт фев 08, 2011 07:15
Сообщения: 18
Откуда: Беларусь
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
вопрос писал(а):
Кстати, почему runwx(15.6) , старт с первой горизонтали должен быть целым
runwx(15)

под 15.6 я подразумевал ограничение максимальной длины прыжка. а почему он должен быть целым?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Ср апр 13, 2011 23:03 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
таково условие задачи (иначе её нельзя было бы решить в целых числах, но не только) - камни - в узлах решётки
runwx(15) подразумевает "стартовать с Х = 15, У = 0"
У = 0 - это берег, У = 25 - другой берег, а Х - в узлах решётки

runwithx


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Чт апр 14, 2011 18:03 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Кстати, да. Пролог на то и 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
Добавив эти слова в код, можно уменьшить макс. длину


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Чт апр 14, 2011 18:08 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Запросив 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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB