чОткий форум
20.03.21 © 2024 Программизд 02
 
Мобильная версия    Контакт    Правила    FAQ    Помощь
Гость
Войти | Регистрация | Профиль | Очистить
Новые сообщения | Избранное
Форумы | Участники | Статистика | Поиск
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Общение / Ну чо, будем решать задачу про расстановку ферзей. или чо
Сообщения: 57 / Страницы: 1  2  3  все  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3046
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
на первом месте в записи фигуры у нас номер строки, на втором номер столбца.
т.е. если запись фигуры (x, y)
то ось X идёт с севера на юг, а Y c запада на восток

например, item = (5, 4)
чтобы найти его диагональных соседей, надо рассмотреть все элементы, полученные от item :
1) уменьшением x и y на единицу одновременно (пройтись на северо-восток): (4, 3) (3, 2) (2, 1)
2) увеличением x на единицу и уменьшением y на единицу одновременно (пройтись на юго-запад): (6, 3) (7, 2) (8, 1)
3) аналогично пройтись на северо-запад и юго-восток

если нигде не столкнемся с существущими ферзями, то возвращаем false, иначе true.
в данном случае во втором пункте мы столкнёмся с ферзём - найдем соседа (7,2)

"нигде не столкнёмся" мы реализуем так: в процессе поиска соседей будем добавлять их в список и если в конце он окажется пустым, то вернём false

на данном этапе напишем генератор всех возможных соседей для данного item, процедура построения списка соседей будет выглядеть так:
Код
1.
2.
3.
4.
5.
6.
7.
8.
(define (neighborhoods item min max direction)
    (let ((x (car item))
          (y (cadr item))
          (x-operation (if (or (equal? direction "SE") (equal? direction "SW")) + -))
          (y-operation (if (or (equal? direction "SE") (equal? direction "NE")) + -)))
      (if (and (>= x min) (<= x max) (>= y min) (<= y max))
         (cons item (neighborhoods (list (x-operation x 1) (y-operation y 1)) min max direction))
         '())))
Изменено: 19.09.2020, 21:11 - Дырокол
Рейтинг: 0 / 0
19.09.2020, 21:04
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3047
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
заметим, что в это реализации сам item тоже попадает в соседи самому себе:
Код
1.
2.
3.
4.
> (neighborhoods '(5 4) 1 8 "NW")
'((5 4) (4 3) (3 2) (2 1))
> (neighborhoods '(5 4) 1 8 "SW")
'((5 4) (6 3) (7 2) (8 1))
поэтому подкрутим немного, удаляя его из каждого списка:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
(define (diagonal-neighborhoods item)
  (define (neighborhoods item min max direction)
    (let ((x (car item))
          (y (cadr item))
          (x-operation (if (or (equal? direction "SE") (equal? direction "SW")) + -))
          (y-operation (if (or (equal? direction "SE") (equal? direction "NE")) + -)))
      (if (and (>= x min) (<= x max) (>= y min) (<= y max))
         (cons item (neighborhoods (list (x-operation x 1) (y-operation y 1)) min max direction))
         '())))
  (append
   (remove item (neighborhoods item 1 8 "NE"))
   (remove item (neighborhoods item 1 8 "NW"))
   (remove item (neighborhoods item 1 8 "SE"))
   (remove item (neighborhoods item 1 8 "SW"))))
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
> (diagonal-neighborhoods '(5 4))
'((4 5)
  (3 6)
  (2 7)
  (1 8)
  (4 3)
  (3 2)
  (2 1)
  (6 5)
  (7 6)
  (8 7)
  (6 3)
  (7 2)
  (8 1))
Изменено: 19.09.2020, 21:16 - Дырокол
Рейтинг: 0 / 0
19.09.2020, 21:15
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3050
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
теперь, наконец, мы можем написать то, ради чего всё это затевалось - предикат diagonal-neighborhoods?

в его реализации воспользуемся абстракцией фильтра
логика следующая
предикат - это некая функция от пары сравниваемых элементов, которая пытается установить являются ли они соседями.
чтобы это сделать, она берет один из элементов, генерит для него всех возможных соседей, а потом проходит по ним фильтром, пытаясь установить, есть ли среди них другой элемент.
Код
1.
2.
3.
4.
5.
(define diagonal-neighborhoods?
  (λ (a b)
    (not (equal? nil
                (filter (λ (x) (equal? a x))
                       (diagonal-neighborhoods b))))))
проверяем:
Код
1.
2.
3.
4.
> (diagonal-neighborhoods? '(5 4) '(4 3))
#t
> (diagonal-neighborhoods? '(5 4) '(3 3))
#f
Изменено: 19.09.2020, 21:28 - Дырокол
Рейтинг: 0 / 0
19.09.2020, 21:25
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3103
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
дальше нужно написать процедуру adjoin-position, которая добавляет нового ферзя
на определенных горизонтали и вертикали к заданному множеству позиций
Код
1.
2.
(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (list (list new-row k))))
 
Рейтинг: 0 / 0
20.09.2020, 17:12
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3106
Лигафоны Рубацова Скрыть профиль Поместить в игнор-лист
Лигафоны Рубацова
Гость
На ПТ пишут что ты наркоман, но я считаю что это писк ужаса от зависти.
 
Рейтинг: 0 / 0
20.09.2020, 17:17
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3107
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
выше были использованы примитивные процедуры
append и remove

append берет в качестве аргументов два списка и составляет из их элементов один общий список:
Код
1.
2.
> (append '(1 4 9 16 25) '(1 3 5 7))
(1 4 9 16 25 1 3 5 7)
remove возвращает все элементы исходной последовательности, за исключением данного.

в принципе, если в языке их нет, то их можно реализовать так:
Код
1.
2.
3.
4.
(define (append list1 list2)
  (if (null? list1)
    list2
    (cons (car list1) (append (cdr list1) list2))))
remove можно выразить как простой фильтр:
Код
1.
2.
(define (remove item sequence)
  (filter (λ (x) (not (= x item))) sequence))
Изменено: 20.09.2020, 17:22 - Дырокол
Рейтинг: 0 / 0
20.09.2020, 17:19
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3108
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Лигафоны Рубацова  20.09.2020, 17:17
3106
На ПТ пишут что ты наркоман, но я считаю что это писк ужаса от зависти.
впереди такое время, что и мёртвые позавидуют живым
 
Рейтинг: 0 / 0
20.09.2020, 17:20
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3109
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Дырокол  18.09.2020, 15:10
2866
разберёмся с предикатом

нам нужно отфильтровать, оставляя только те, где
ферзь на k-й вертикали не бьется ни одним из остальных.

т.е. предикат должен на вход брать множество позиций и возвращать результат работы
некоторой функции сравнения, которая для этого множества позиций определяет,
находится ли ферзь с k-й вертикали в безопасности от остальных.
назовём эту функцию сравнения safe?
Код
1.
2.
3.
4.
5.
6.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
          (λ (positions) (safe? k positions))
          расширенный набор позиций)))
так, safe? мы реализовали
осталась генерация расширенного набора позиций
 
Рейтинг: 0 / 0
20.09.2020, 17:26
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3110
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
идея следующая:

надо сначала сгенерить расстановку для первого столбца:
Код
1.
(((1 1)) ((2 1)) ((3 1)) ((4 1)) ((5 1)) ((6 1)) ((7 1)) ((8 1)))
потом для каждого элемента добавить расстановку для второго столбца:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
'(((1 1) (1 2))
  ((1 1) (2 2))
  ((1 1) (3 2))
  ((1 1) (4 2))
  ((1 1) (5 2))
  ((1 1) (6 2))
  ((1 1) (7 2))
  ((1 1) (8 2)))

'(((2 1) (1 2))
  ((2 1) (2 2))
  ((2 1) (3 2))
  ((2 1) (4 2))
  ((2 1) (5 2))
  ((2 1) (6 2))
  ((2 1) (7 2))
  ((2 1) (8 2)))
...

'(((8 1) (1 2))
  ((8 1) (2 2))
  ((8 1) (3 2))
  ((8 1) (4 2))
  ((8 1) (5 2))
  ((8 1) (6 2))
  ((8 1) (7 2))
  ((8 1) (8 2)))
и так далее
Изменено: 20.09.2020, 17:51 - Дырокол
Рейтинг: 0 / 0
20.09.2020, 17:50
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3111
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
в общем, пишем генератор.

сначала напишем генератор для последовательности целых чисел от min до max:
Код
1.
2.
3.
4.
(define (enumerate-interval low high)
  (if (> low high)
    nil
    (cons low (enumerate-interval (+ low 1) high))))
Код
1.
2.
> (enumerate-interval 1 8)
(1 2 3 4 5 6 7 8)
 
Рейтинг: 0 / 0
20.09.2020, 17:53
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3112
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
потом мы можем взять эти числа за номера строк и для каждого k-го стобца генерить пары c помощью
adjoin-position, которая, напомню добавляет нового ферзя на определенных горизонтали и
вертикали к заданному множеству позиций

т.е. мы можем начать с пустого множества позиций так:
Код
1.
2.
3.
4.
> (adjoin-position 1 1 '())
'((1 1))
> (adjoin-position 2 1 '())
'((2 1))
потом применить эту функцию к предыдущему результату:
Код
1.
2.
3.
4.
5.
6.
7.
8.
> (adjoin-position 1 2 '(1 1))
'(1 1 (1 2))
> (adjoin-position 1 2 '((1 1)))
'((1 1) (1 2))
> (adjoin-position 2 2 '((1 1)))
'((1 1) (2 2))
> (adjoin-position 3 2 '((1 1)))
'((1 1) (3 2))
и так далее
 
Рейтинг: 0 / 0
20.09.2020, 18:04
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3113
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
задумаемся, что по сути при фиксированном стобце k это отображение номеров строк из множества от 1 до 8 в пары (1 k), (2 k) и так далее, причем приписанных (добавленных) к предыдущей расстановке. т.е. это отображение с параметром "номер строки", которое вызывает для каждого номера строки функцию преобразования adjoin-position.

перед тем, как продолжить, реализуем абстракцию "отображение" в общем виде.

Это процедура высшего порядка (в миру называется map).
Map берет в качестве аргументов процедуру от одного аргумента и список,
а возвращает список результатов, полученных применением процедуры к каждому элементу списка:
Код
1.
2.
3.
4.
5.
6.
(define (map proc items)
  (if (null? items)
  nil
  (cons
     (proc (car items))
     (map proc (cdr items)))))
Код
1.
2.
3.
4.
5.
(map abs (list -10 2.5 -11.6 17))
> (10 2.5 11.6 17)

(map (lambda (x) (* x x)) (list 1 2 3 4))
> (1 4 9 16)
 
Рейтинг: 0 / 0
20.09.2020, 18:12
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3115
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
т.е. наше отображение будет выглядеть так:
Код
1.
2.
3.
4.
(map (lambda (new-row)
                  (adjoin-position
                   new-row k rest-of-queens))
               (enumerate-interval 1 board-size))
теперь можно приступить к генерации:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((1 1))))
                 (enumerate-interval 1 8))
'(((1 1) (1 2))
  ((1 1) (2 2))
  ((1 1) (3 2))
  ((1 1) (4 2))
  ((1 1) (5 2))
  ((1 1) (6 2))
  ((1 1) (7 2))
  ((1 1) (8 2)))
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((2 1))))
                 (enumerate-interval 1 8))
'(((2 1) (1 2))
  ((2 1) (2 2))
  ((2 1) (3 2))
  ((2 1) (4 2))
  ((2 1) (5 2))
  ((2 1) (6 2))
  ((2 1) (7 2))
  ((2 1) (8 2)))
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((3 1))))
                 (enumerate-interval 1 8))
'(((3 1) (1 2))
  ((3 1) (2 2))
  ((3 1) (3 2))
  ((3 1) (4 2))
  ((3 1) (5 2))
  ((3 1) (6 2))
  ((3 1) (7 2))
  ((3 1) (8 2)))
 
Рейтинг: 0 / 0
20.09.2020, 18:16
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3116
Лигафоны Рубацова Скрыть профиль Поместить в игнор-лист
Лигафоны Рубацова
Гость
Это на чём, на лиспе что-ли?
 
Рейтинг: 0 / 0
20.09.2020, 18:22
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3117
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Лигафоны Рубацова  20.09.2020, 18:22
3116
Это на чём, на лиспе что-ли?
2533
 
Рейтинг: 0 / 0
20.09.2020, 18:27
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3125
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
завтра пойду погулять в места, где интернета не будет.
дня три-четыре погуляю
так что кому не терпится решать задачу дальше, могут саморедуцироваться
 
Рейтинг: 0 / 0
20.09.2020, 20:41
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3172
краник Скрыть профиль Поместить в игнор-лист
краник
Гость
Дырокол  20.09.2020, 20:41
3125
завтра пойду погулять в места, где интернета не будет.
дня три-четыре погуляю
так что кому не терпится решать задачу дальше, могут саморедуцироваться
опасайся водяных вшей
 
Рейтинг: 0 / 0
20.09.2020, 22:23
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3177
Лигафоны Рубацова Скрыть профиль Поместить в игнор-лист
Лигафоны Рубацова
Гость
Дырокол  20.09.2020, 18:27
3117
Лигафоны Рубацова  20.09.2020, 18:22
3116
Это на чём, на лиспе что-ли?
2533
OK
 
Рейтинг: 0 / 0
20.09.2020, 22:30
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3182
black lives matter Скрыть профиль Поместить в игнор-лист
black lives matter
Гость
фсе ферзи чорные, ОК
 
Рейтинг: 0 / 0
20.09.2020, 22:39
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3316
Гопник с Вантового моста Скрыть профиль Поместить в игнор-лист
Гопник с Вантового моста
Гость
Каждый лиспер должен хоть раз написать свой лисп, воистину, братия!
 
Рейтинг: 0 / 0
22.09.2020, 21:48
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3401
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
1.jpg
 
Рейтинг: 0 / 0
24.09.2020, 21:39
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3402
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
погулял
 
Рейтинг: 0 / 0
24.09.2020, 21:39
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3408
SQL
Скрыть профиль Поместить в игнор-лист
SQL
Участник
Дырокол  24.09.2020, 21:39
3402
погулял
Видел недавно на границе с абхазией вид подобный но ещё круче
 
Рейтинг: 0 / 0
24.09.2020, 21:45
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3411
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
SQL  24.09.2020, 21:45
3408
Дырокол  24.09.2020, 21:39
3402
погулял
Видел недавно на границе с абхазией вид подобный но ещё круче
круче в домбае
 
Рейтинг: 0 / 0
24.09.2020, 21:49
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3412
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
если про рф говорить
и эльбрус, но туда сложно гулять
 
Рейтинг: 0 / 0
24.09.2020, 21:49
Ответить | Цитировать | Написать  
Форумы / Общение / Ну чо, будем решать задачу про расстановку ферзей. или чо
Сообщения: 57 / Страницы: 1  2  3  все  
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые участники ...
Найденые участники ...
Читают тему (0):
Читают форум (0):
Участники онлайн (0):
Пользовательское соглашение
...
Закрыть
get settings:  1ms
get forum list:  1ms
check forum access:  0ms
check topic access:  0ms
get msg page:  1ms
>>> redirection >>>:  118ms
get settings:  1ms
get forum list:  2ms
check forum access:  0ms
check topic access:  0ms
get topic data:  1ms
get forum data:  0ms
get page posts:  45ms
track hit:  3ms
get tp. blocked users:  0ms
get online users:  2ms
check new:  4ms
others:  6ms
total:  185ms
созд. / загр.: 185ms (нв.: 4ms)
x
x
Закрыть


Просмотр
Close
Debug Console [Select Text]