Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 10:31

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - Решение задачи на Prolog'e
Автор Сообщение
  Заголовок сообщения:  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
Сообщение Добавлено: Чт апр 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
Добавив эти слова в код, можно уменьшить макс. длину
Сообщение Добавлено: Чт апр 14, 2011 18:03
  Заголовок сообщения:  Re: Решение задачи на Prolog'e  Ответить с цитатой
таково условие задачи (иначе её нельзя было бы решить в целых числах, но не только) - камни - в узлах решётки
runwx(15) подразумевает "стартовать с Х = 15, У = 0"
У = 0 - это берег, У = 25 - другой берег, а Х - в узлах решётки

runwithx
Сообщение Добавлено: Ср апр 13, 2011 23:03
  Заголовок сообщения:  Re: Решение задачи на Prolog'e  Ответить с цитатой
вопрос писал(а):
Кстати, почему runwx(15.6) , старт с первой горизонтали должен быть целым
runwx(15)

под 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"
Сообщение Добавлено: Ср апр 13, 2011 22:40
  Заголовок сообщения:  Re: Решение задачи на Prolog'e  Ответить с цитатой
непонятно как пользоваться вашей прогой. по запросу 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_array

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

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

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

К сожалению, при большом количестве камней полный перебор очень долог. При небольшом - нет.
Список, который "путь" в конце печатается так как сформирован - т.е. последние прыжки - слева.
Сообщение Добавлено: Ср апр 13, 2011 20:43
  Заголовок сообщения:  Re: Решение задачи на Prolog'e  Ответить с цитатой
Задача о кенгуру на прологе
вот такое условие
Изображение
тут всё симметрично, но симметрия нарушена камушками, которые выделены в красный
Сообщение Добавлено: Ср апр 13, 2011 20:42
  Заголовок сообщения:  Re: Решение задачи на Prolog'e  Ответить с цитатой
если найду способ подкрасить текст - прокомментирую
просто полный перебор, результаты откладываются в 2 списка


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

синим - результат хороший, красным - результат который хуже 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(_).
Сообщение Добавлено: Вт фев 08, 2011 17:35
  Заголовок сообщения:  Re: Решение задачи на Prolog'e  Ответить с цитатой
Хм, я не знаю, как комментировать?
Вообще, например 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 существуют. И представление данных - возможные наборы разделителй и число их появлений связать термом вида список/число вхождений.
Сообщение Добавлено: Сб фев 05, 2011 15:43
  Заголовок сообщения:  Re: Решение задачи на Prolog'e  Ответить с цитатой
вопрос писал(а):
Интересно, к чему это подсказки?

Ну может программа попроще станет, чем она в самом первом посту темы :shuffle;

Просто мне лень в чужом коде копаться когда нет алгоритма оформленного отдельно.
Иногда неясно что хочет автор особенно обращаю внимание на множестов отсечений !. применение точек с запятой в Прологе приводит к непониманию особенно больших последовательностей преобразований, - лучше лишнее определение написать, скорость от этог не изменится
Сообщение Добавлено: Сб фев 05, 2011 14:50

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


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