Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Вт мар 19, 2024 12:06

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Задача про Fферзей
СообщениеДобавлено: Ср июн 13, 2018 21:40 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
На шахматной доске размещены 8 ферзей. Считая, что ферзь ходит по прямой линии в любую сторону (по вертикали, горизонтали и диагонали), определить, является ли размещение каждого из ферзей безопасным для остальных ферзей (т.е. ни один ферзь не может взять другого ферзя). Если это не так, определить, можно ли удалить с доски одного ферзя, чтобы размещение остальных стало безопасным.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про Fферзей
СообщениеДобавлено: Чт июн 14, 2018 09:15 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1285
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Эм, на работу нужен фортер?
А это проверка мыслительных способностей?

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про Fферзей
СообщениеДобавлено: Чт июн 14, 2018 14:29 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Victor__v писал(а):
Эм, на работу нужен фортер?
А это проверка мыслительных способностей?

Это задачи с прошедшей "внутренней" студенческой олимпиады. Студенты в целом справились...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про Fферзей
СообщениеДобавлено: Вт сен 04, 2018 20:01 
Не в сети

Зарегистрирован: Чт июл 12, 2018 02:33
Сообщения: 7
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Код:
CREATE MARKS 46 ALLOT
: MINIT MARKS 46 ERASE ;
: MARK? ( i -- flag ) MARKS + DUP C@ -1 ROT C! ;
: HOR? ( hor vert -- flag ) DROP MARK? ;
: VERT? ( hor vert -- flag ) NIP 8 + MARK? ;
: DIAG1? ( hor vert -- flag ) + 16 + MARK? ;
: DIAG2? ( hor vert -- flag ) 7 SWAP - + 31 + MARK? ;
: >COORD ( addr - hor vert ) DUP C@ [CHAR] A - SWAP 1+ C@ [CHAR] 1 - ;
: OVERLAP? ( addr -- flag )
   >COORD 2DUP HOR? >R 2DUP VERT? >R 2DUP DIAG1? >R DIAG2? R> OR 2R> OR OR ;
: SAFE? ( addr u -- flag )
   MINIT 0 ROT ROT 1+ 3 / 0 ?DO DUP OVERLAP? ROT OR SWAP 3 + LOOP DROP 0= ;

S" A7 B4 C2 D8 E6 F1 G3 H5" SAFE? .
S" D5 B7" SAFE? .

Слово SAFE? возвращает TRUE, если размещение каждого из ферзей является безопасным для остальных ферзей. Работает в spf4 и в gforth.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про Fферзей
СообщениеДобавлено: Вт сен 11, 2018 22:50 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Работает в spf4
Код:
: safe? { \ [ 16 ] x [ 16 ] y sx sy sd sn sm -- true|xy|false  }
8 0 DO 10 /MOD 2DUP x I + C! y I + C! x I + 8 + C! y I + 8 + C! LOOP
BEGIN
0 TO sx 0 TO sy 0 TO sd
7 sn - sm + sm DO 8 sn - sm + I 1+ DO x J + C@ x I + C@ = IF 1 TO sx LEAVE THEN LOOP LOOP
7 sn - sm + sm DO 8 sn - sm + I 1+ DO y J + C@ y I + C@ = IF 1 TO sy LEAVE THEN LOOP LOOP
7 sn - sm + sm DO 8 sn - sm + I 1+ DO x J + C@ x I + C@ - ABS J y + C@ I y + C@ - ABS =
IF 1 TO sd LEAVE THEN LOOP LOOP
sx sy sd OR OR TO sn
sm 1+ TO sm
sn 0= sm 16 > OR
UNTIL
sm 16 >
IF   FALSE
ELSE sm 1-
     IF   sm 2- x + C@ 10 * sm 2- y + C@ +
     ELSE TRUE
     THEN
THEN
;

13 25 32 48 56 64 77 81 safe? \ 8 безопасны
13 23 32 48 56 64 77 81 safe? \ 7 безопасны, если убрать 1-го
13 22 32 48 56 65 77 81 safe? \ невозможно сделать безопасными 7, если убрав 1-го

log
Код:
Ok ( 4294967295(-1) 23 0 )

TRUE - 8 ферзей не угрожают друг другу,
Число ( 23 ) 2 - координата по горизонтали, 3 - координата по вертикали для ферзя, которого нужно убрать, чтобы
оставшиеся 7 ферзей не угрожали друг другу,
FALSE - нельзя убрав только 1-го ферзя сделать позицию оставшихся 7 ферзей безопасной
ПС. Число позиций c 8-мю ферзями, когда убрав 1-го ферзя остальные 7 ферзей не угрожают друг другу 92*8*56=41216

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


Последний раз редактировалось chess Чт янв 30, 2020 21:53, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про Fферзей
СообщениеДобавлено: Чт сен 13, 2018 23:14 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Гораздо проще найти решение для нахождения всех безопасных позиций (92 штуки).
Код:
CREATE i 8 ALLOT
: Do 9 1 DLIT, POSTPONE DO POSTPONE I ; IMMEDIATE
: i!  i + C! ;
: y.  i OVER [CHAR] a + EMIT + C@ . ;
: ferzi
Do 0 i! Do 1 i! Do 2 i! Do 3 i! Do 4 i! Do 5 i! Do 6 i! Do 7 i!
       7 0 DO 8 I 1+ DO J i + C@ I i + C@ = LOOP LOOP 27 0 DO OR LOOP
       7 0 DO 8 I 1+ DO I J - J i + C@  I i + C@  - ABS = LOOP LOOP 28 0 DO OR LOOP 0=
       IF 8 0 DO I y. LOOP CR THEN
LOOP LOOP LOOP LOOP LOOP LOOP LOOP LOOP
;
ferzi


log
Код:
a1 b5 c8 d6 e3 f7 g2 h4
a1 b6 c8 d3 e7 f4 g2 h5
a1 b7 c4 d6 e8 f2 g5 h3
a1 b7 c5 d8 e2 f4 g6 h3
a2 b4 c6 d8 e3 f1 g7 h5
a2 b5 c7 d1 e3 f8 g6 h4
a2 b5 c7 d4 e1 f8 g6 h3
a2 b6 c1 d7 e4 f8 g3 h5
a2 b6 c8 d3 e1 f4 g7 h5
a2 b7 c3 d6 e8 f5 g1 h4
a2 b7 c5 d8 e1 f4 g6 h3
a2 b8 c6 d1 e3 f5 g7 h4
a3 b1 c7 d5 e8 f2 g4 h6
a3 b5 c2 d8 e1 f7 g4 h6
a3 b5 c2 d8 e6 f4 g7 h1
a3 b5 c7 d1 e4 f2 g8 h6
a3 b5 c8 d4 e1 f7 g2 h6
a3 b6 c2 d5 e8 f1 g7 h4
a3 b6 c2 d7 e1 f4 g8 h5
a3 b6 c2 d7 e5 f1 g8 h4
a3 b6 c4 d1 e8 f5 g7 h2
a3 b6 c4 d2 e8 f5 g7 h1
a3 b6 c8 d1 e4 f7 g5 h2
a3 b6 c8 d1 e5 f7 g2 h4
a3 b6 c8 d2 e4 f1 g7 h5
a3 b7 c2 d8 e5 f1 g4 h6
a3 b7 c2 d8 e6 f4 g1 h5
a3 b8 c4 d7 e1 f6 g2 h5
a4 b1 c5 d8 e2 f7 g3 h6
a4 b1 c5 d8 e6 f3 g7 h2
a4 b2 c5 d8 e6 f1 g3 h7
a4 b2 c7 d3 e6 f8 g1 h5
a4 b2 c7 d3 e6 f8 g5 h1
a4 b2 c7 d5 e1 f8 g6 h3
a4 b2 c8 d5 e7 f1 g3 h6
a4 b2 c8 d6 e1 f3 g5 h7
a4 b6 c1 d5 e2 f8 g3 h7
a4 b6 c8 d2 e7 f1 g3 h5
a4 b6 c8 d3 e1 f7 g5 h2
a4 b7 c1 d8 e5 f2 g6 h3
a4 b7 c3 d8 e2 f5 g1 h6
a4 b7 c5 d2 e6 f1 g3 h8
a4 b7 c5 d3 e1 f6 g8 h2
a4 b8 c1 d3 e6 f2 g7 h5
a4 b8 c1 d5 e7 f2 g6 h3
a4 b8 c5 d3 e1 f7 g2 h6
a5 b1 c4 d6 e8 f2 g7 h3
a5 b1 c8 d4 e2 f7 g3 h6
a5 b1 c8 d6 e3 f7 g2 h4
a5 b2 c4 d6 e8 f3 g1 h7
a5 b2 c4 d7 e3 f8 g6 h1
a5 b2 c6 d1 e7 f4 g8 h3
a5 b2 c8 d1 e4 f7 g3 h6
a5 b3 c1 d6 e8 f2 g4 h7
a5 b3 c1 d7 e2 f8 g6 h4
a5 b3 c8 d4 e7 f1 g6 h2
a5 b7 c1 d3 e8 f6 g4 h2
a5 b7 c1 d4 e2 f8 g6 h3
a5 b7 c2 d4 e8 f1 g3 h6
a5 b7 c2 d6 e3 f1 g4 h8
a5 b7 c2 d6 e3 f1 g8 h4
a5 b7 c4 d1 e3 f8 g6 h2
a5 b8 c4 d1 e3 f6 g2 h7
a5 b8 c4 d1 e7 f2 g6 h3
a6 b1 c5 d2 e8 f3 g7 h4
a6 b2 c7 d1 e3 f5 g8 h4
a6 b2 c7 d1 e4 f8 g5 h3
a6 b3 c1 d7 e5 f8 g2 h4
a6 b3 c1 d8 e4 f2 g7 h5
a6 b3 c1 d8 e5 f2 g4 h7
a6 b3 c5 d7 e1 f4 g2 h8
a6 b3 c5 d8 e1 f4 g2 h7
a6 b3 c7 d2 e4 f8 g1 h5
a6 b3 c7 d2 e8 f5 g1 h4
a6 b3 c7 d4 e1 f8 g2 h5
a6 b4 c1 d5 e8 f2 g7 h3
a6 b4 c2 d8 e5 f7 g1 h3
a6 b4 c7 d1 e3 f5 g2 h8
a6 b4 c7 d1 e8 f2 g5 h3
a6 b8 c2 d4 e1 f7 g5 h3
a7 b1 c3 d8 e6 f4 g2 h5
a7 b2 c4 d1 e8 f5 g3 h6
a7 b2 c6 d3 e1 f4 g8 h5
a7 b3 c1 d6 e8 f5 g2 h4
a7 b3 c8 d2 e5 f1 g6 h4
a7 b4 c2 d5 e8 f1 g3 h6
a7 b4 c2 d8 e6 f1 g3 h5
a7 b5 c3 d1 e6 f8 g2 h4
a8 b2 c4 d1 e7 f5 g3 h6
a8 b2 c5 d3 e1 f7 g4 h6
a8 b3 c1 d6 e2 f5 g7 h4
a8 b4 c1 d3 e6 f2 g7 h5

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про Fферзей
СообщениеДобавлено: Пт сен 14, 2018 11:15 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Генерация всех перестановок не отвечает на второй интересный вопрос - "можно ли удалить с доски одного ферзя, чтобы размещение остальных стало безопасным". Это уже ближе к вопросам проектирования, когда надо определить, что добавить в программу (или убрать из требований), чтобы проблема решилась с минимальными усилиями.

Ну и интересно, почему бектрекинга среди решений не видно :)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про Fферзей
СообщениеДобавлено: Пт сен 14, 2018 12:18 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1285
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Hishnik писал(а):
Ну и интересно, почему бектрекинга среди решений не видно :)


Наверно потому что его :shuffle; единственный "адепт" на форуме только начал его изучать :P

_________________
Цель: сделать 64-битную Нову под Винду


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

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


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

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


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

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