|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgeny Sharandin 2:5020/755.12 18 Oct 2001 12:17:00
To : Rustam Gadeyev
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
Привет Rustam!
11 октября 2001 года (а было тогда 21:36)
Rustam Gadeyev в своем письме к All писал:
RG> друг друга ферзей на шахматной доске за 45 минут. Что-то меня задело
RG> такое долгое время счета и где-то за полчаса родил программу, которая
RG> идет ниже в письме. Эти 92 позиции на доске 8х8 без вывода на экран
RG> считаются на P3-450 0.11сек, а 14х14 считаются 22.5сек. Вопрос: можно
RG> ли сделать лучше? :)
Можно. Hапример, поступить самым тупым образом и сменить bp/tmt/fpk на gpc
;))). А на сколько можно? Hу на порядок, как минимум.
RG> Пусть я давно уже не студент, но написать нетривиальную программку за
RG> полчаса мне не слабо.
Семь раз отмерь...
Вот пример вывода твоей (таймер добавлен и исправлено объявление переменной под
счетчик найденных вариантов) после компиляции BP и при ее запуске на iP-233
92 вариантов 0.00 Sec
352 вариантов 0.06 Sec
724 вариантов 0.06 Sec
2680 вариантов 0.33 Sec
14200 вариантов 1.92 Sec
73712 вариантов 11.15 Sec
365596 вариантов 68.71 Sec
RG> if p[a[n]] and d1[a[n]+n-1] and d2[num-a[n]+n] then
Ух, какие сложности с проверками! Зачем такие навороты с индексацией массивов?
Все можно упростить, если вспомнить, что номер горизонтали однозначно
определяет позицию ферзя (станет просто p[n]). Дополнительно можно выкинуть по
одному действию из диагональных массивов если просто по другому их описать.
Вывод программы, учитывающий это, в рекурсивном варианте, работает почти в 2
раза быстрее.
92 вариантов 0.00 Sec
352 вариантов 0.00 Sec
724 вариантов 0.00 Sec
2680 вариантов 0.22 Sec
14200 вариантов 1.15 Sec
73712 вариантов 6.48 Sec
365596 вариантов 39.88 Sec
program queens;
uses timer;
Const N=14;
var
v : array [1..N] of byte;
h : array [1..N] of boolean;
d1 : array [2..2*N] of boolean;
d2 : array [-N..N] of boolean;
i : integer;
Num: longint;
procedure Find(i: byte);
var j: byte;
begin
for j:=1 to N do begin
if h[j] and d1[i+j] and d2[i-j] then begin
> Так проще сравнение делать ;)
v[i]:=j; {Hаступаем сюда, можно выкинуть если вывод не нужен}
h[j]:=false; {Запрещаем диагонали и горизонталь}
d1[i+j]:=false; d2[i-j]:=false;
if i=N then begin
{сюда печать вставить}
inc(Num)
end else Find(i+1); {Ищем дальше}
h[j]:=true; {Откат}
d1[i+j]:=true; d2[i-j]:=true;
end;
end;
end;
begin
time1;
Num:=0;
for i:=1 to N do h[i]:=true;
for i:=2 to 2*N do D1[i]:=true;
for i:=-N+1 to N-1 do D2[i]:=true;
Find(1);
writeln(Num,' вариантов', time2*1e-3:7:2,' Sec');
end.
Далеко не оптимум. Можно еще упростить и вообще исключить неоднократные
вычисления i+j и i-j, процесс занятия клетки и отката перенести в ветку else
оператора сравнения if i=N, может еще чего по мелочам. Выигрыш будет, думаю,
соизмерим с тем, что уже получен - лень заниматься.
Почти в 2 раза уже есть, как еще уже написал. Смена BP на spb или GPC еще раза
в 2 пришпорит. Пусть будет, в сумме, в 4 раза (чего жадничать-то?). А если
учесть симметрию, то для доски 8х8, в пределе, можно еще сократить время до
12/92. Короче, ускорение на порядок - это очень скромно.
С уважением, Evgeny 18 октября 2001 года
---
* Origin: LID (2:5020/755.12)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
8 мирных ферзей 
