Вот у меня тут вопросик есть , кто может , пусть поможет мне пожалуйста - я буду очень блогадарен ему Вопрос такой: Написать программу которая вычисляет количество комбинации расположить N ферзей на шахматной доске NXN (6<=N<=13) так чтобы не одна ферзь не угражала другой. этот вопрос надо решить с помощью рекурсии и минимизировать время как можно больше. Я решил этот вопрос но время вычисления моей програмы когда N=13 превышает секунду , а мне надо добится результата за меньше чем за секунду. Я понял что можно уменьшить на 50% количество проверяемых комбинаций и это я сделал . но этого не достаточно , мне нужно у меньшить количество ещё раз на 50% как то помощью симетрии и так далее.... кто знает решения буду очень блогадарен ему.
Гость
22.01.2006 18:17
Будем гадать на кофейной гуще? Как можно помочь, если неизвестно, ЧТО именно сделано?
Можно и без всяких отражений и поворотов за секунду получить результат, а можно и с этим со всем не уложиться...
Pavel_25
22.01.2006 18:21
смотри... я использовал только отражения и я хочу узнать каким образом я могу улучшить свою программу.
Гость
22.01.2006 18:24
Да как можно улучшать, если не знаешь, что???
Ты бы показал, что сделал, посмотрим.
Pavel_25
22.01.2006 18:37
хорошо... Щас покажу.....
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;
BeginIf column>N Then Max:=Max+1ElsebeginFor I:=1To N doif (rowok[I]) And (diagonal[N+I-Column,1]) And (diagonal[I+Column-1,2]) Thenbegin
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:=1to N do rowok[I]:=True;
For I:=1to2*N-1dobegin
diagonal[I,1]:=True; diagonal[I,2]:=True;
end;
Max:=0;
pqueen(1,N,queen,diagonal,rowok,Max);
Max:=0;
For I:=1To N div2dobegin
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 mod2<>0Thenbegin
I:=N div2+1;
rowok[I]:=False;
diagonal[N+I-1,1]:=False; diagonal[I,2]:=False;
For I:=1To N div2-1dobegin
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
22.01.2006 18:51
Я не понял, чем не устраивает тот вариант, что есть у нас в FAQ? Очень быстро работает, по крайней мере, не медленнее чем приведенный, зачем опять изобретать велосипед? Есть же готовый.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.