| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Ход конём [D6, WinXP]

Страницы:   < 1 2 3 >

Ezhik ©   (2004-10-12 01:31:00) 

Уважаемые мастера, я в отчаянии. Пишу широкоизвестную прогу "Ход конём"(есть поле 10*10, и надо начиная с любой клетки порйти все 100 ходов побывав в каждой из них единажды). Алгоритм я понимаю и все казалось бы прозрачно (рекурсия), но что-то не то.:( Уже 2-а дня сижу за отладкой, надпись на клавише ф7 уже стерлась :). Через ф7, я наблюдаю, что все идеально, вродеб-то. Умоляю, посмотрите что в этом алгоритме не так... Спасибо за внимание

var
 Hodu: array of array of byte; //сюда пишем сделаные ходы
 Masiv: array[1..10,1..10] of Boolean; //Помечаем ечейку занетой
 VariantListXXX: array of byte; //
 VariantListYYY: array of byte; //списки возможных ходов
 Variantu: array[1..100,1..2] of byte; //пишем число вариантов ходов и под каким вариантом мы зашли в даный момент
 x,y,FreeCount,move_num: integer;

x:=0;
y:=0;

procedure Recors();
var
i,a,b: byte;
begin
 CheckHodCount(x,y); //проверяем число возможных ходов
 if FreeCount <> 0 then
 begin
   SetLength(Hodu,move_num+1,2);

   Masiv[x,y]:= True;
   Hodu[move_num,0]:= x;
   Hodu[move_num,1]:= y;
                                       
   Variantu[move_num+1,1]:= FreeCount;
   Inc(move_num);

   if move_num >= 100 then begin ShowMessage('100!!!'); draw; exit end;

   X:= VariantListXXX[Variantu[move_num,2]]; //первый раз мы берём из списка возможных ходов первый, при неудаче - 2-й, и т.д.
   Y:= VariantListYYY[Variantu[move_num,2]];

//    Form1.Caption:= Inttostr(move_num);
   Recors;
 end
 else
 begin
//  ShowMessage('000');
   repeat
     a:= Variantu[move_num,1];
     b:= Variantu[move_num,2];
     Masiv[(Hodu[move_num-1,0]),(Hodu[move_num-1,1])]:= False;
     if a <= b+1 then
     begin                      
       Variantu[move_num,1]:=0;
       Variantu[move_num,2]:=0;
     end;
     inc(move_num,-1);
   until a > b+1;

   x:= Hodu[move_num,0];
   y:= Hodu[move_num,1];
   Variantu[move_num+1,2]:= Variantu[move_num+1,2] + 1;
   Recors
 end;
end;

CheckHodCount(x,y); - это порцедура мне возврашает число вариантов ходовю

---

wnew   (2004-10-12 04:48:00) [41]

Стандартная задача по программированию. Смотри по этой ссылке http://www.gymnasium-odenthal.de/download/iflk_abi03_material/_pdfs/Klausur_LK_12_1_N.pdfчетвёртую страницу в PDF-файле. Или скачай этот исходник http://www.salvator.net/salmat/info/springer.zip

---

Defunct   (2004-10-12 04:30:00) [42]

[2]
хотя вру 94 клеточки покрыло, но ждать пришлось очень долго.
Возможно покроет и 100.. правда 8^100 вариантов, кто вам дал такое задание?

---

Defunct   (2004-10-12 04:08:00) [43]

Если ходить можно только бугвой Г, то задача не имеет решения, невозможно покрыть даже 90 клеточек не говоря уж о всех 100:

unit Unitxx;

interface

uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, StdCtrls, Grids;

type
 TForm3 = class(TForm)
   SG: TStringGrid;
   Button1: TButton;
   procedure Button1Click(Sender: TObject);
 private
   { Private declarations }
 public
   { Public declarations }
   function Move(Location:TPoint; Direction: Word;  History:Integer):Integer;
 end;

var
 Form3: TForm3;

implementation

{$R *.dfm}

const d_ur = $FE01;  // вверх на 2, вправо на 1
     d_ul = $FEFF;  // вверх на 2, влево на 1
     d_dr = $0201;  // вниз на 2,  вправо на 1
     d_dl = $02FF;  // вниз на 2,  влево на 1
     d_ru = $FF02;  // вверх на 1, вправо на 2
     d_lu = $FFFE;  // вверх на 1, влево на 2
     d_rd = $0102;  // вниз на 1,  вправо на 2
     d_ld = $01FE;  // вниз на 1,  влево на 2

     AllDirections : Array[1..8] of word =
     (d_ur, d_ul, d_dr, d_dl, d_ru, d_lu, d_rd, d_ld);

function InBound(var Location: TPoint; Direction: Word):Boolean;
Var XD, YD: Integer;
Begin
 XD := Byte(Direction And $FF);
 If XD> 127 Then XD := XD or $FFFFFF00;
 YD := Byte(Direction Shr 8);
 If YD> 127 Then YD := YD or $FFFFFF00;

 Location.X := Location.X + XD;
 Location.Y := Location.Y + YD;

 Result := (Location.X>=0) And (Location.Y>=0) And
           (Location.X<=9) And (Location.Y<=9);
End;

function TForm3.Move(Location:TPoint; Direction: Word;  History:Integer):Integer;
Var NH : Integer;
   I  : Integer;
Begin
 Result := History;
 If History>90 Then ShowMessage('Found');
{ выполнение движения }
 If InBound(Location, Direction) Then
 Begin
   Inc(History);
   If SG.Cells[Location.X, Location.Y] <> 'P' Then
   Begin
     SG.Cells[Location.X, Location.Y] := 'P';

     For I:=1 To 8 Do
     Begin
       NH := Move(Location, AllDirections[i], History);
       If NH > Result Then Result := NH;
     End;

     SG.Cells[Location.X, Location.Y] := 'c';
     Button1.Caption := IntToStr( Result );
     Application.ProcessMessages;
   End

 End;

End;

procedure TForm3.Button1Click(Sender: TObject);
Var P:TPoint;
   S: Integer;
begin
 P.X := 5;
 P.Y := 5;
 S := 0;
 Move(P, d_rd, S);
end;

end.

Советую уточнить условие.

---

Defunct   (2004-10-12 02:01:00) [44]

можно уточнить: ходить можно только буквой Г?

---

Страницы:   < 1 2 3 >

Наверх