ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Ezhguroff                     2:5020/400     18 Feb 2002  16:48:59
 To : Yasha Davidov
 Subject : Re: 8 ферзей
 -------------------------------------------------------------------------------- 
 

 Привет! "Yasha Davidov" <yasha@davidov.ru>  сообщил(а):
 
  YD> Всё равно нужен массив с кучей бесполезной информации. Этого то я и
  YD> хотел избежать.
  YD> К тому же нужна какая-то предварительная обработка.
  YD> Пока я сделал так:
  YD> Я перебираю значения в таком порядке:
  YD> [01234567]
  YD> [01234576]
  YD> [01234657]
  YD> [01234675]
 
 Возможно, это способ ускорить поиск расстановок:
 
 Если в ферзь стоит на строке N в позиции M, то на строке N+q ферзь не может
 находиться в позициях M-q, M, M+q.
 
 Проще всего это реализовать с помощью битовых строк:
 
 Заводим три переменные - L, R и H.
 Установка ферзя в столбец Pos: L|=(1<<Pos); R|=(1<<Pos); H|=(1<<Pos)
 Проверка на допустимость установки ферзя в столбец Pos текущей строки:
 !((L|R|H)&(1<<Pos))
 Hевозможность поставить ферзя в текущую строку: (L|R|H)==0xFF
 Переход к следующей строке: L<<=1; R>>=1
 
  YD> Всё это очень похоже на простой перебор чисел. Поэтому я делаю так,
  YD> когда я нахожу перестановку, являющуюся решением я беру все её 8
  YD> отражений, и если хоть одно из этих отражений меньше, (то есть было
  YD> раньше) чем текущая доска (я могу легко это определит), то значит этот
  YD> тип доски я уже находил раньше. В противном случае это решение. Плюс я
  YD> перебираю только от [01234567] до [476543210], то есть только
  YD> половину.
  YD> Hо я думаю, что есть способ ещё проще...
 
 Очевидное решение - отсортировать массив расстановок (тем более, что у тебя
 он уже отсортирован) и определять дубли бинарным поиском (не исключая их из
 массива - это слишком медленно, а ставя флажок). Что сокращает кол-во
 операций с O(N^3) до O(N^2*log(N)) (оценка неточная, думать лень :-) ).
 
 К тому же можно представить расстановки в виде Int64 (та же битовая строка
 длинной 64 бита) и работать не с массивами, а с целыми числами.
 
 С уважением, Андрей.
 -- 
 Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.Mail.Ru (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    8 ферзей   Yasha Davidov   16 Feb 2002 00:49:38   8 ферзей   Max Alekseyev   15 Feb 2002 19:15:40   Re: 8 ферзей   Yasha Davidov   16 Feb 2002 15:16:10   8 ферзей   vitalie vrabie   23 Feb 2002 02:00:52   8 ферзей   Egorov Pavel   18 Feb 2002 00:26:48   Re: 8 ферзей   Yasha Davidov   18 Feb 2002 01:44:00   Re: 8 ферзей   Zeram Z   18 Feb 2002 13:32:29   Re: 8 ферзей   Andrew Ezhguroff   18 Feb 2002 16:48:59   8 ферзей   Egorov Pavel   19 Feb 2002 00:33:19   8 ферзей   Dan Raskovalov   21 Feb 2002 10:23:31