Wieża Hanoi

[Featon]

Mam taki algorytm na przeniesienie n (3) krązków z palika A na B:
( tylko mi chodzi że trzeba przenieść na palik środkowy).
1.Jeśli n=1 przenieś krązek z (A-> B) i zakoncz.
2. Stosując ten sam algorytm przenieś (n-1,A,C,B) {z A na B z uzyciem C (?)}
3. Przenieś pozostały krążek (A->B)
4.Stosujac ten sam algorytm przenieś(n-1,C,B,A)

I jakoś nie działa mi ten algorytm, chyba to przyczyna mojej złej interpretacji.
Więc nie mam pojęcia jak ten algorytm ma działać, ani jak będzie wyglądała lista kroków w pascalu. Paliki mają być przedstawione jako tablice A , B , C z indeksami [0..3], krązki są liczbami od 1 do 3 (3 krążki). Na dodatek nauczyciel zasugerował ze trzeba użyć dodatkowego krązka A[o] który będzie zapisywał ilość krązków/liczb w tablicy.
Napisał jescze :
A[a[o]]-sczyt słupka
1. b[0]+1
2.A[A[0]]->B
3.A[A[0]]

[Fibik]

Należy przenieść z A na B n sztuk:
1. z A na C n-1 sztuk
2. z A na B 1 sztuka
3. z C na B n-1 sztuk

Kod: Zaznacz cały

// A = 1, B = 2, C = 3

prcedure przenies(z, na, k : Integer); // 
begin
 
 if k = 1 then begin

  writeln(char(z+64), ' -> ', char(na+64)); // przestawiam wolny (ze szczytu)

 end else begin
  przenies(z, 6-z-na, k-1); // chwilowo przenoszę na trzeci słupek: nr = 6-(z+na)
  przenies(z, na, 1); // największy jest wolny
  przenies(6-z-na, na, k-1); // teraz pozostałe z trzeciego
 end;

end;

begin

 przenies(1, 2, 3); // przenieś z A na B 3 krążki

 przenies(1, 3, 5); // przenieś z A na C 5 krążków - może będzie dobrze.

end.

[Featon]

Do zrozumienia pierwszego algorytmu i napisania programu z uzyciem tablic i A[A[0]] mam jescze trochę daleko.

Mam coś takiego. Oczywiście nie działa, to chyba związane z nieaktualnością zmiennych.

Kod: Zaznacz cały

type
 TAB=array[0..3] of byte;
const
  A:tab=(3,3,2,1);
  B:tab=(0,0,0,0);
  c:tab=(0,0,0,0);
var
n:byte;
procedure hanoi(n:byte;var A,B,C:tab);
  procedure mov(A,B:tab);
   begin
    B[0]:=B[0]+1;
    B[b[0]]:=A[A[0]] ;
    A[A[0]]:=0;
    A[0]:=A[0]-1;
   end;
  begin

   if n=1 then     mov(A,B) else
     begin
      hanoi((n-1),a,c,b);
      mov(A,B);
      hanoi((n-1),c,b,a);
     end
  end;
begin
 hanoi(3,A,B,C);
 readln;
end.

Naprawiłem! To wina tych aktualnych zmiennych, 'var' w paru miejsczach i jakoś poszło.

Kod: Zaznacz cały

program wHanoi;
uses crt;
type
 TAB=array[0..3] of byte;
const
  A:tab=(3,3,2,1);
  B:tab=(0,0,0,0);
{B[0]=0 bo trzeba dodawa† 1 za kazdym razem kiedy sie na to przenosi ,(byˆo by  za 1-razem 2)}
  c:tab=(0,0,0,0);
  n=3;   {liczba krĄzk˘w}

 {przed 'procedure' nie musi by† var!}
 procedure pisz;    {parametry globalne}
     const Krok:byte=0;
           x:byte=5;
           y:byte=2;
           czekaj=800;
     var i:byte;

      function inter(a:byte):string;
       begin
        if a=1 then inter:='         [ | ]        ' else
        if a=2 then inter:='        [  |  ]       ' else
        if a=3 then inter:='       [   |   ]      ' else
                    inter:='           |          ' ;

{itd, albo zrobi†  ' x-p '+ [' +p + '|'+p + ']'+'x-p' gdzie p jest stringiem postaci '   '
 i rosnie proporcjonalnie od wielko˜ci krĄzka}
       end;
      begin
       gotoxy(1,1);
       inc(krok);
       Writeln('Krok ', krok);
       x:=5;
       y:=10;
        for i:=n downto 1 do
         begin
           y:=y+1;
           gotoxy(x,y);
           writeln(inter(a[i]));
         end;
          x:=26;
          y:=10;
         for i:=n downto 1 do
          begin
           y:=y+1;
           gotoxy(x,y);
           writeln(inter(b[i]));
          end;
           y:=10;
         for i:=n downto 1 do
          begin
           y:=y+1;
           x:=46 ;
           gotoxy(x,y);
           writeln(inter(C[i]));
          end;
          gotoxy(1,Y+1);
          write('   /\/\/\/\/\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\');
          delay(czekaj);
          if  krok=7  then    {bonus}
          begin textbackground(red); clrscr; textcolor(white+blink);
          gotoxy(20,20); writeln('NARESCZIE  K   O  N  I  E  C  SWIATA!'); end;
      end;


 procedure hanoi(n:byte;var A,B,C:tab);
 {var!, inaczej zmienne tablicowe w hanoi wroca do stanu poczatkowego po zakonczeniu procedury}
  procedure mov(var A,B:tab);
  {var!, zmienne okre˜laja A,B aktualne w procedzurze hanoi , nie w caˆym programie!  }
   begin             {w zmiennych tablicowych o indeksie 0 przechowuje ilo˜c kraľk˘w}
    B[0]:=B[0]+1;  {nie moze by† na koäcu, bo w tablice [B[b[index=0]] nic nie wpisze}
    B[b[0]]:=A[A[0]] ;
    A[A[0]]:=0;
    A[0]:=A[0]-1;
    pisz;  {tu pisz , bo to mozna zaobserwowa† zmiany w tablicach}
   end;
  begin
      {przenosze na krazek pomocniczy wieze z n-1 krazkow,
    daje krazek 1 na docelowy i n-1 na docelowy}

   if n=1 then  mov(A,B)     {na docelowy}
   else
    begin
      hanoi((n-1),a,c,b);      {na  pomocniczy n-1}
      mov(A,B);      {samo sie nie przeniesie}
      hanoi((n-1),c,b,a);     {z pomocniczego na docelowy n-1}
     end;
  end;
    procedure kf; assembler; {ukrywaja / pokazuja kursor}
       asm
        mov ah, 01h
       mov ch, 10h
       mov cl, 00h
       int 10h
    end;
       
   procedure k; assembler;
        asm
        mov ah, 01h
        mov ch, 07h
        mov cl, 08h
        int 10h
   end;

begin
 kf;
 textbackground(0);
 clrscr;
 hanoi(3,A,B,C);
 readln;
end.

[bzykol]

a ja mam zrobić w pascalu program który będzie liczył ile ruchów trzeba wykonać na przeniesienie wieży jeśli mu się poda ilość klocków. nie mam pojęcia co i jak :/ help...

[jasny]

Wzór na ilość ruchów: 2^n-1
Pozdro dla Bzykola

[bzykol]

hehe thx Jasny myślałem że to jakoś cuś więcej roboty

[Czesio]

Generalnie to jest taki wzór rekurencyjny na minimalną ilość ruchów:
\(\displaystyle{ T_{n}=2T_{n-1}+1}\)