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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 58 ]  На страницу 1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: шесть коней
СообщениеДобавлено: Пн май 14, 2007 14:52 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Найти все решения для такой chess-задачки(с помощью Форта конечно):
Изображение
Поменять местами белых коней с черными, путем поочередных ходов сначала одним из белых коней, затем одним из черных коней и т.д., при этом коней нельзя ставить на клетки, которые находятся под ударом коней другого цвета.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн май 14, 2007 21:57 
Не в сети
Аватара пользователя

Зарегистрирован: Пт май 05, 2006 06:19
Сообщения: 192
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
фигасе... /me впал в задумчивость

_________________
SPF


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн май 14, 2007 22:09 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Вручную оно как-то решается быстрее, чем с помощью Форта :))

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн май 14, 2007 23:46 
Не в сети

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

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт май 15, 2007 16:55 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Ну и кто разберёт эту тарабарщину? :)
<pre>
STARTLOG

REQUIRE write-list ~ygrek/lib/list/all.f

\ Размерности
3 VALUE nx
4 VALUE ny

\ пакуем две координаты в один CELL
: xy ( x y -- p ) 16 LSHIFT OR ;
: p ( p -- x y ) DUP 16 RSHIFT SWAP 0xFFFF AND SWAP ;
: xy. SWAP . . ;

\ Пара - позиция и "история посещений"
: xy% %[ xy DUP % %[ % ]% %l ]% %l ;

\ начальные позиции
%[ 0 0 xy% 1 0 xy% 2 0 xy% ]% VALUE b
%[ 0 3 xy% 1 3 xy% 2 3 xy% ]% VALUE w

\ конечные позиции
%[ 0 0 xy % 1 0 xy % 2 0 xy % ]% VALUE w-fin
%[ 0 3 xy % 1 3 xy % 2 3 xy % ]% VALUE b-fin

\ ход игры
() VALUE bpath
() VALUE wpath

\ -----------------------------------------------------------------------

: position car ;
: position! setcar ;
: history cdar ;
: history! cdr setcar ;
: history-add >R vnode R@ history cons R> history! ;
: history-dec >R R@ history cdr R> history! ;

: position-member? LAMBDA{ position OVER = } SWAP list-find NIP NIP ;

: poswrite LAMBDA{ ." ( " p xy. ." ) " } SWAP mapcar ;
: pwrite LAMBDA{ CR DUP position p xy. ." ( " history LAMBDA{ ." [ " p xy. ." ] " } SWAP mapcar ." ) " } SWAP mapcar ;
: bwprint CR ." Black : " b pwrite CR ." White : " w pwrite ;
: tablewrite { w b -- }
ny 0 DO
CR
nx 0 DO
I J xy w member? IF ." W" ELSE
I J xy b member? IF ." B" ELSE
." ." THEN THEN
LOOP
LOOP ;
: pathwrite LAMBDA{ CR poswrite } SWAP mapcar ;
: pathwrite2 LAMBDA{ car >R car R> CR tablewrite } -ROT map2 ;

\ принадлежит игровому полю?
: valid? { x y -- ? }
y 0 < x 0 < OR IF FALSE EXIT THEN
y ny < x nx < AND ;

\ сгенерировать два числа +n и -n
: +/- ( n <--> +/-n ) PRO CONT NEGATE CONT DROP ;
: BOTH+ { a b c d -- a+c b+d } a c + b d + ;

\ сгенерировать все варианты прыжка конём
: variants=> ( x y --> x1 y1 \ <-- x1 y1 )
PRO
START{
*> 2 +/- 1 +/- <*> 1 +/- 2 +/- <*
( x y dx dy ) 2OVER 2OVER BOTH+ CONT 2DROP }EMERGE
2DROP ;

\ отсечь только те что попадают на игровое поле
: //valid PRO 2DUP valid? ONTRUE CONT ;

\ сохранить все варианты хода в список
: variants ( x y -- l ) %[ START{ variants=> //valid 2DUP xy % }EMERGE ]% ;

\ Расстояние от хотя бы одной позиции из списка l1 до клетки x y равняется одному ходу конём
: beats? ( x y l1 -- ? )
-ROT
variants { | l2 }
DUP -> l2
( l1 l2 ) \ AND lists
LAMBDA{ OVER ( a l1 ) LAMBDA{ position OVER = } SWAP list-find NIP NIP } SWAP list-find NIP NIP
l2 FREE-LIST ;

\ занята ли клетка
: free? ( x y -- ? )
xy DUP w position-member? IF DROP FALSE EXIT THEN
b position-member? 0= ;

\ отсекает все битый позиции
: //notbeats ( x y l <--> x y ) PRO >R 2DUP R> beats? 0= IF CONT THEN ;
\ отсекает все занятые позиции
: //free ( x y <--> x y ) PRO 2DUP free? ONTRUE CONT ;

\ ход одним конём
: move1 ( enemy knight --> \ <-- )
STATIC z z ! STATIC enemy enemy !
PRO
z @ position p
BACK xy z @ position! TRACKING
2RESTB
variants=>
//valid
//free
enemy @ //notbeats
2DUP xy z @ history member? ONFALSE
2DUP xy z @ position!
2DUP xy z @ history-add
z @ enemy @
CONT
enemy ! z !
z @ history-dec ;

\ ход чёрных - это либо один ход первым конём, либо вторым, либо третьим :)
: bmove PRO b list-> car w SWAP move1 CONT ;
: wmove PRO w list-> car b SWAP move1 CONT ;

\ совпала ли позиция с заданой?
: finish? LAMBDA{ position b-fin member? NOT } b list-find NIP NOT ;

\ сохранить позиции всех коней
: save-positions ( b|w -- ) %[ LAMBDA{ position % } SWAP mapcar ]% ;

\ не более n решений
: solutions=> ( n --> \ <-- )
STATIC n n ! STATIC cnt cnt 0!
PRO
START{
cnt @ n @ >= IF EXIT THEN
\ bwprint
\ KEY DROP
bmove b save-positions vnode as-list bpath cons TO bpath
BACK bpath DUP cdr TO bpath () cons FREE-LIST TRACKING
wmove w save-positions vnode as-list wpath cons TO wpath
BACK wpath DUP cdr TO wpath () cons FREE-LIST TRACKING
\ CR ." Check finish"

finish? IF CONT cnt 1+! THEN
finish? ONFALSE
\ CR ." Recurse"
DIVE
}EMERGE ;

: go 100 +{ solutions=>
CR
CR bwprint
wpath reverse \ eventually все пути в обратном порядке - для удобства - развернём перед выводом
bpath reverse
2DUP
CR pathwrite2
reverse TO bpath
reverse TO wpath
1 }+ CR " Found {n} solutions" STYPE
;

go
</pre>
Работает традиционно только на cvs-коде.
Алгоритм - тупой перебор в лоб - даже без устремления к цели - просто перебор всех ходов удовлетворяющих условиям до тех пор пока текущая позиция не совпадёт с требуемой. Параметры : размер доски, количество коней и их начальное и конечное расположение можно менять (правда ввиду тупости алгоритма результата можно ждать долго...). Находит восемь решений. Реализовано на бакфорте потому что есть удобные средства для перебора, "конкатенации" переборов, возврата.

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 16, 2007 16:58 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Ygrek совершил подвиг программиста. Браво! Я думал - никто не решит. Была применена тяжелая артиллерия - бакфорт и списки. Правда был использован тупой перебор, из-за чего время решения увеличилось, но зато решение было найдено в общем виде. Управление направлением перебора - использование набора правил выбора из многих вариантов немногих(в идеале - одного), быстрее ведущих к цели - главная проблема ИИ. В данном случае можно было бы ввести понятие расстояния между текущей позицией коней и конечной их позицией (это лежит на поверхности). И если ход уменьшает это расстояние, то его следовало бы предпочесть ходу увеличивающему расстояние, правда, при условии что позиция, которая получится после этого хода отсутствует в списке состоявшихся позиций. Сам я такие задачи могу решать лишь на уровне построения алгоритма, а реализовать на форте нет - в форте я неофит пока :)

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 16, 2007 20:08 
Не в сети

Зарегистрирован: Сб янв 27, 2007 22:00
Сообщения: 106
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Прежде чем пускать в ход тяжелую артиллерию, неплохо сначала подумать.
Задача элементарно решается методом пуговиц и нитей без всякого компьютера.
См. "Наука и жизнь", № 7, 1977.


Последний раз редактировалось yz Ср май 16, 2007 23:13, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 16, 2007 20:16 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Задача стояла решить на форте. По крайней мере я себе поставил такую задачу.
Решить на бумажке эту конкретную задачку конечно проще.
Как её решать указанным методом совершенно непонятно.

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 16, 2007 20:47 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
yz писал(а):
Прежде чем пускать в ход тяжелую артиллерию, неплохо сначала подумать.
Задача элементарно решается методом пуговиц и нитей без всякого компьютера.
См. "Наука и жизнь", № 5, 1977.

Там задача сначала приводится к удобному для восприятия человеком виду. После этого все решения легко находятся вручную.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 16, 2007 21:39 
Не в сети
Аватара пользователя

Зарегистрирован: Пт май 05, 2006 06:19
Сообщения: 192
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
/me впроцесе поиска решения
P.S. вернее в процессе отладки выбранного пути

_________________
SPF


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 16, 2007 23:26 
Не в сети

Зарегистрирован: Сб янв 27, 2007 22:00
Сообщения: 106
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
ygrek писал(а):
Всё таки как решать эту задачку методом ниток и пуговиц?
Там задача и тут задача - принципиально разные.

Краткое описание метода можно посмотреть здесь: http://stepanov.lk.net/gardner/sec/sec03.html


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт май 17, 2007 00:10 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
В этой задаче вместо одного кольца - два кольца с двумя переходами - есть два узла развилки. Вот схема :
Изображение
И есть условие на "битые поля". То есть надо следить чтобы соседние узлы не были заняты вражеским цветом. По-моему вручную даже после такого преобразования решение не очевидно и надо руками двигать и смотреть. Ну а программа просто реализует это двигание.

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт май 17, 2007 00:16 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Это что, теория графов?
:D

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт май 17, 2007 00:19 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Сначала я кстати явно строил этот граф переходов и хранил в памяти. Но что-там не задалось и переписал. Хотя так для бОльших размерностей конечно правильней.

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт май 17, 2007 10:14 
Не в сети

Зарегистрирован: Сб янв 27, 2007 22:00
Сообщения: 106
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
ygrek писал(а):
И есть условие на "битые поля". То есть надо следить чтобы соседние узлы не были заняты вражеским цветом. По-моему вручную даже после такого преобразования решение не очевидно и надо руками двигать и смотреть. Ну а программа просто реализует это двигание.

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


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

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


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

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


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

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