Помощь - Поиск - Пользователи - Календарь
Полная версия: Путешествие коня .
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
strangerfx
12.03.2006 17:09
Есть такая задача: Написать программу реализующую передвижение коня по всем 64 клеткам шахматной доски.
Мое решение такое:
Код
Program lab;
uses crt;
var  mas:array[1..8,1..8] of integer;
     i,j:integer;
     v:byte;

procedure pg;
var e:integer;
begin
   gotoxy(15,4);
   write(#201);
   for e:=1 to 51 do write(#205);
   writeln(#187);
   for e:=1 to 17 do
   begin
      gotoxy(15,wherey);
      write(#186);
      gotoxy(67,wherey);
      writeln(#186);
   end;
   gotoxy(15,wherey);
   write(#200);
   for e:=1 to 51 do write(#205);
   writeln(#188);
end;

procedure a(y:integer;x:integer;n:byte);
var i,j:integer;
begin
   if (x+1>0) and (x+1<9) and (y-2>0) and (y-2<9) and (mas[y-2,x+1]=0)
   then
   begin
       mas[y-2,x+1]:=n;
       a(y-2,x+1,n+1);
       mas[y-2,x+1]:=0;
   end;
   if (x+2>0) and (x+2<9) and (y-1>0) and (y-1<9) and (mas[y-1,x+2]=0)
   then
   begin
       mas[y-1,x+2]:=n;
       a(y-1,x+2,n+1);
       mas[y-1,x+2]:=0;
   end;
        if (x+2>0) and (x+2<9) and (y+1>0) and (y+1<9) and (mas[y+1,x+2]=0)
   then
   begin
       mas[y+1,x+2]:=n;
       a(y+1,x+2,n+1);
       mas[y+1,x+2]:=0;
   end;
   if (x+1>0) and (x+1<9) and (y+2>0) and (y+2<9) and (mas[y+2,x+1]=0)
   then
   begin
       mas[y+2,x+1]:=n;
       a(y+2,x+1,n+1);
       mas[y+2,x+1]:=0;
   end;
   if (x-1>0) and (x-1<9) and (y+2>0) and (y+2<9) and (mas[y+2,x-1]=0)
   then
   begin
       mas[y+2,x-1]:=n;
       a(y+2,x-1,n+1);
       mas[y+2,x-1]:=0;
   end;
   if (x-2>0) and (x-2<9) and (y+1>0) and (y+1<9) and (mas[y+1,x-2]=0)
   then
   begin
       mas[y+1,x-2]:=n;
       a(y+1,x-2,n+1);
       mas[y+1,x-2]:=0;
   end;
   if (x-2>0) and (x-2<9) and (y-1>0) and (y-1<9) and (mas[y-1,x-2]=0)
   then
   begin
       mas[y-1,x-2]:=n;
       a(y-1,x-2,n+1);
       mas[y-1,x-2]:=0;
   end;
   if (x-1>0) and (x-1<9) and (y-2>0) and (y-2<9) and (mas[y-2,x-1]=0)
   then
   begin
       mas[y-2,x-1]:=n;
       a(y-2,x-1,n+1);
       mas[y-2,x-1]:=0;
   end;
if n=65 then
   begin
     repeat
      clrscr;
      pg;
      gotoxy(17,5);
      write('‚ўҐ¤ЁвҐ ®ЇаҐ«Ґ«с­­го жЁдаг ¤«п ўлЇ®«­Ґ­Ёп Є®¬ ­¤л:');
      gotoxy(17,7);
      write('1:','„«п ўлў®¤  аҐ§г«мв в ':47);
      gotoxy(17,9);
      write('2:','„«п ўл室 ':47);
      gotoxy(17,11);
      write('‚ў®¤->: ');
      {$I-}
      readln(v);
      {$I+}
      if IOResult<>0 then begin
                            clrscr;
                            writeln('ЌҐЄ®а४в­л© ўў®¤,ўўҐ¤ЁвҐ зЁб«® гЄ § ­­®Ґ ў ¬Ґ­о');
                            writeln('„«п Їа®¤®«¦Ґ­Ёп а Ў®вл ­ ¦¬ЁвҐ Enter');
                            readln;
                          end
                     else begin
                            case v of
                                    1:begin
                                          clrscr;
                                          writeln('ђҐ§г«мв в');
                                          writeln('=======================');
                                          for i:=1 to 8 do
                                                      begin
                                                        for j:=1 to 8 do write(mas[i,j]:2,' ');
                                                        writeln;
                                                      end;
                                          writeln('=======================');
                                          readln;
                                          clrscr;
                                      end;
                                 2: halt;
                               end;
                             end;
     until IOResult<>0;
    end;
end;

begin
   fillchar(mas,sizeof(mas),0);
   repeat
      clrscr;
      pg;
      gotoxy(17,5);
      write('‚ўҐ¤ЁвҐ ®ЇаҐ«Ґ«с­­го жЁдаг ¤«п ўлЇ®«­Ґ­Ёп Є®¬ ­¤л:');
      gotoxy(17,7);
      write('1:','„«п агз­®Ј® ўў®¤  ­ з «м­ле Є®®а¤Ё­ в':47);
      gotoxy(17,9);
      write('2:','„«п  ўв®¬ вЁзҐбЄ®Ј® § ¤ ­Ёп Є®®а¤Ё­ в':47);
      gotoxy(17,11);
      write('3:','„«п ўл室 ':47);
      gotoxy(17,13);
      write('‚ў®¤->: ');
      {$I-}
      readln(v);
      {$I+}
      if IOResult<>0 then begin
                            clrscr;
                            writeln('ЌҐЄ®а४в­л© ўў®¤,ўўҐ¤ЁвҐ зЁб«® гЄ § ­­®Ґ ў ¬Ґ­о');
                            writeln('„«п Їа®¤®«¦Ґ­Ёп а Ў®вл ­ ¦¬ЁвҐ Enter');
                            readln;
                          end
                     else begin
                            case v of
                                    1: begin
                                         clrscr;
                                         writeln('‚ўҐ¤ЁвҐ ­ з «м­лҐ Є®®а¤Ё­ вл');
                                         write('y->: ');
                                         readln(i);
                                         write('x->: ');
                                         readln(j);
                                         clrscr;
                                         mas[i,j]:=1;
                                         a(i,j,2);
                                       end;
                                    2: begin
                                         clrscr;
                                         randomize;
                                         i:=random(7)+1;
                                         j:=random(7)+1;
                                         mas[i,j]:=1;
                                         a(i,j,2);
                                       end;
                                    3: exit;
                                   end;


   end;
   until IOResult<>0;
end.

Нужно оптимизировать код для повышения скорости работы программы.

Тегами [CОDE][/CОDE] пользуйся...
volvo
12.03.2006 18:08
procedure a(y:integer;x:integer;n:byte);
var
  i,j:integer;
  Tx, Ty: integer;
begin

  if (mas[y-2,x+1]=0) then begin
     Tx := x+1; Ty := y-2;
     if (Tx>0) and (Tx<9) and (Ty>0) and (Ty<9) then begin
       mas[Ty,Tx]:=n;
       a(Ty,Tx,n+1);
       mas[Ty,Tx]:=0;
     end;
   end;

   if (mas[y-1,x+2]=0) then begin
     Tx := x+2; Ty := y-1;
     if (Tx>0) and (Tx<9) and (Ty>0) and (Ty<9) then begin
       mas[Ty,Tx]:=n;
       a(Ty,Tx,n+1);
       mas[Ty,Tx]:=0;
     end;
   end;

   if (mas[y+1,x+2]=0) then begin
     Tx := x+2; Ty := y+1;
     if (Tx>0) and (Tx<9) and (Ty>0) and (Ty<9) then begin
       mas[Ty,Tx]:=n;
       a(Ty,Tx,n+1);
       mas[Ty,Tx]:=0;
     end;
   end;

   if (mas[y+2,x+1]=0) then begin
     Tx := x+1; Ty := y+2;
     if (Tx>0) and (Tx<9) and (Ty>0) and (Ty<9) then begin
       mas[Ty,Tx]:=n;
       a(Ty,Tx,n+1);
       mas[Ty,Tx]:=0;
     end;
   end;

   if (mas[y+2,x-1]=0) then begin
     Tx := x-1; Ty := y+2;
     if (Tx>0) and (Tx<9) and (Ty>0) and (Ty<9) then begin
       mas[Ty,Tx]:=n;
       a(Ty,Tx,n+1);
       mas[Ty,Tx]:=0;
     end;
   end;

   if (mas[y+1,x-2]=0) then begin
     Tx := x-2; Ty := y+1;
     if (Tx>0) and (Tx<9) and (Ty>0) and (Ty<9) then begin
       mas[Ty,Tx]:=n;
       a(Ty,Tx,n+1);
       mas[Ty,Tx]:=0;
     end;
   end;

   if (mas[y-1,x-2]=0) then begin
     Tx := x-2; Ty := y-1;
     if (Tx>0) and (Tx<9) and (Ty>0) and (Ty<9) then begin
       mas[Ty,Tx]:=n;
       a(Ty,Tx,n+1);
       mas[Ty,Tx]:=0;
     end;
   end;

   if (mas[y-2,x-1]=0) then begin
     Tx := x-1; Ty := y-2;
     if (Tx>0) and (Tx<9) and (Ty>0) and (Ty<9) then begin
       mas[Ty,Tx]:=n;
       a(Ty,Tx,n+1);
       mas[Ty,Tx]:=0;
     end;
   end;
...

Вот это нехитрое действие уменьшает время выполнения самой рекурсивной процедуры с 280 ms до 203 ms...
strangerfx
12.03.2006 18:25
Нужна оптимизация более глубокого характера, например использование массивов ходов или правила Варнсдорфа. Вопрос в том как это сделать?
volvo
12.03.2006 18:36
Вариант обхода методом Варнсдорфа:
FAQ: Переборные алгоритмы
strangerfx
12.03.2006 18:56
Цитата(volvo @ 12.03.2006 14:36) *

Вариант обхода методом Варнсдорфа:
FAQ: Переборные алгоритмы

Мне не очень понятен ход решения задачи(Pascal изучаю 5 месецев), непонятно как его в мою прогу вставить?
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.