|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rustam Gadeyev 2:5008/14 19 Oct 2001 18:12:36
To : Evgeny Sharandin
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
18 Окт 01 12:17, Evgeny Sharandin wrote Rustam Gadeyev:
ES> Семь раз отмерь...
ES> описать. Вывод программы, учитывающий это, в рекурсивном варианте,
ES> работает почти в 2 раза быстрее.
Рекурсия всегда короче, но не быстрее. Поэтому я внес непринципиальные изменения
в свою программку, ведь BP7 не оптимизирует использование переменных.
И размер 14 мой вариант вычисляет на 30% быстрее, чем твой рекурсивный вариант.
Переписанный алгоритм один в один на BC3.1 считает еще быстрее, а вот WC10.0
почему-то медленнее (/5 /oilr /s). Видимо оптимизировать уже нечего.
Процессор P3-450. В прошлый раз я ошибся, у меня был Cel-550.
old BP7 14 27.73, 13 4.63
ES BP7 14 23.43, 13 3.89
RG BP7 14 18.51, 13 3.24
RG BC3.1 14 11.75, 13 1.92
RG WC10 14 12.58, 13 2.08
Так что теперь я думаю сильно быстрее сделать уже нельзя.
//--- 8pherz.pas ---\\
uses crt; {written by Rustam G. 19.10.2001}
const num=13; {BP7.0 P3-450: 14 18.51, 13 3.24}
var
a:array[1..num] of byte; {позиции ферзей}
p,d1,d2:array[0..num*2] of boolean;
kol:longint;
i,j:byte;
procedure work;
var t,n:word;
begin
n:=1;a[n]:=1;kol:=0;t:=a[n];
while true do
begin
{если сюда можно поставить ферзя}
if p[t] and d1[t+n-1] and d2[num-t+n] then
begin
if n=num then {если встал последний ферзь, комбинация достигнута }
begin
kol:=kol+1;
{вывод на экран}
{удалить этот комментарий для вывода на экран
clrscr;
a[n]:=t;
for i:=1 to num do
for j:=1 to num do
begin
gotoxy(j*2,i);
if a[j]=i then write(j) else write('* ');
end;
if readkey=#27 then exit;{по позициям}
end else
begin {если это не последний ферзь, попробуем поставить еще}
p[t]:=false; {запрет горизонтали и диагоналей}
d1[t+n-1]:=false; d2[num-t+n]:=false;
a[n]:=t;
inc(n); {к следующему ферзю}
t:=1; {начиная с позиции 1}
continue; {летим пробовать поставить еще один ферзь}
end;
end;
{идем на новую позицию}
while true do
begin
if t<num then
begin
inc(t);
break {еще есть позиции для перебора в столбце}
end
else {этот столбик уже весь перебрали}
begin
dec(n); {отступаем}
if n<1 then exit; {больше некуда?}
t:=a[n];
p[t]:=true; {разрешить горизонталь и диагонали}
d1[t+n-1]:=true; d2[num-t+n]:=true;
end;
end;
end;
end;
begin
for i:=0 to num*2 do
begin
p[i]:=true;
d1[i]:=true;
d2[i]:=true;
end;
work;
writeln;
writeln(kol,' вариантов');
end.
\\--- 8pherz.pas ---//
Good Bye.
--- ---
* Origin: Ulan-Ude. Buryatia. (2:5008/14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
