Вот у меня тут вопросик есть , кто может , пусть поможет мне пожалуйста - я буду очень блогадарен ему Вопрос такой: Написать программу которая вычисляет количество комбинации расположить N ферзей на шахматной доске NXN (6<=N<=13) так чтобы не одна ферзь не угражала другой. этот вопрос надо решить с помощью рекурсии и минимизировать время как можно больше. Я решил этот вопрос но время вычисления моей програмы когда N=13 превышает секунду , а мне надо добится результата за меньше чем за секунду. Я понял что можно уменьшить на 50% количество проверяемых комбинаций и это я сделал . но этого не достаточно , мне нужно у меньшить количество ещё раз на 50% как то помощью симетрии и так далее.... кто знает решения буду очень блогадарен ему.
Гость
22.01.2006 22:17
Будем гадать на кофейной гуще? Как можно помочь, если неизвестно, ЧТО именно сделано?
Можно и без всяких отражений и поворотов за секунду получить результат, а можно и с этим со всем не уложиться...
Pavel_25
22.01.2006 22:21
смотри... я использовал только отражения и я хочу узнать каким образом я могу улучшить свою программу.
Гость
22.01.2006 22:24
Да как можно улучшать, если не знаешь, что???
Ты бы показал, что сделал, посмотрим.
Pavel_25
22.01.2006 22: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; 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
22.01.2006 22:51
Я не понял, чем не устраивает тот вариант, что есть у нас в FAQ? Очень быстро работает, по крайней мере, не медленнее чем приведенный, зачем опять изобретать велосипед? Есть же готовый.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.