IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Путешествие коня .
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


Есть такая задача: Написать программу реализующую передвижение коня по всем 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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


Нужна оптимизация более глубокого характера, например использование массивов ходов или правила Варнсдорфа. Вопрос в том как это сделать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Вариант обхода методом Варнсдорфа:
FAQ: Переборные алгоритмы
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


Цитата(volvo @ 12.03.2006 14:36) *

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

Мне не очень понятен ход решения задачи(Pascal изучаю 5 месецев), непонятно как его в мою прогу вставить?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 16.04.2025 2:57
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name