Помощь - Поиск - Пользователи - Календарь
Полная версия: N ферзей
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Pavel_25
Вот у меня тут вопросик есть , кто может , пусть поможет мне пожалуйста - я буду очень блогадарен ему
Вопрос такой:
Написать программу которая вычисляет количество комбинации расположить N ферзей на шахматной доске
NXN (6<=N<=13) так чтобы не одна ферзь не угражала другой. этот вопрос надо решить с помощью рекурсии и минимизировать время как можно больше. Я решил этот вопрос но время вычисления моей програмы когда N=13 превышает секунду , а мне надо добится результата за меньше чем за секунду.
Я понял что можно уменьшить на 50% количество проверяемых комбинаций и это я сделал . но этого не достаточно , мне нужно у меньшить количество ещё раз на 50% как то помощью симетрии и так далее....
кто знает решения буду очень блогадарен ему.
Гость
Будем гадать на кофейной гуще?
Как можно помочь, если неизвестно, ЧТО именно сделано?

Можно и без всяких отражений и поворотов за секунду получить результат, а можно и с этим со всем не уложиться...
Pavel_25
смотри... я использовал только отражения и я хочу узнать каким образом я могу улучшить свою программу.
Гость
Да как можно улучшать, если не знаешь, что???

Ты бы показал, что сделал, посмотрим.
Pavel_25
хорошо... Щас покажу.....

Program checker;
Type
arrqueen=Array[1..13] Of Byte;
diag=Array[1..25,1..2] of Boolean;
arr=Array[1..13] of Boolean;
Var fin, fout: text;
N,I:Byte;
Max:Longint;
Queen:arrqueen;
diagonal:diag;
rowok:arr;
Procedure placequeen(Column,N:Byte; diagonal:diag; rowok:arr; Var max:Longint);
Var
I:Byte;
Begin
If column>N Then Max:=Max+1
Else
begin
For I:=1 To N do
if (rowok[I]) And (diagonal[N+I-Column,1]) And (diagonal[I+Column-1,2]) Then
begin
rowok[I]:=False;
diagonal[N+I-Column,1]:=False; diagonal[I+Column-1,2]:=False;
placequeen(column+1,n,diagonal,rowok,Max);
rowok[I]:=True;
diagonal[N+I-Column,1]:=True; diagonal[I+Column-1,2]:=True;
end;
end;
End;
Begin
Assign(fin, 'checker.in'); Reset(fin);
Assign(fout, 'checker.out'); Rewrite(fout);
Readln(fin, N);
For I:=1 to N do rowok[I]:=True;
For I:=1 to 2*N-1 do
begin
diagonal[I,1]:=True; diagonal[I,2]:=True;
end;
Max:=0;
pqueen(1,N,queen,diagonal,rowok,Max);
Max:=0;
For I:=1 To N div 2 do
begin
rowok[I]:=False;
diagonal[N+I-1,1]:=False; diagonal[I,2]:=False;
placequeen(2,N,diagonal,rowok,Max);
rowok[I]:=True;
diagonal[N+I-1,1]:=True; diagonal[I,2]:=True;
end;
If N mod 2<>0 Then
begin
I:=N div 2+1;
rowok[I]:=False;
diagonal[N+I-1,1]:=False; diagonal[I,2]:=False;
For I:=1 To N div 2-1 do
begin
rowok[I]:=False;
diagonal[N+I-2,1]:=False; diagonal[I+1,2]:=False;
placequeen(3,n,diagonal,rowok,Max);
rowok[I]:=True;
diagonal[N+I-2,1]:=True; diagonal[I+1,2]:=True;
end;
end;
Writeln(fout, 2*Max);
Close(fout);
End.


Ответ нужно предостачить в файле.
volvo
Я не понял, чем не устраивает тот вариант, что есть у нас в FAQ? Очень быстро работает, по крайней мере, не медленнее чем приведенный, зачем опять изобретать велосипед? Есть же готовый.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.