Difference between revisions of "Basic Pascal Tutorial/Chapter 4/Solution"

From Free Pascal wiki
Jump to navigationJump to search
Line 1: Line 1:
 
4Ga - Solution to Towers of Hanoi (author: Tao Yue, state: unchanged)
 
4Ga - Solution to Towers of Hanoi (author: Tao Yue, state: unchanged)
 +
<delphi>
 +
(* Author:    Tao Yue
 +
  Date:      13 July 2000
 +
  Description:
 +
      Solves the Towers of Hanoi
 +
  Version:
 +
      1.0 - original version
 +
*)
  
−
<font color="#000000">  1:</font> <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">Author:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">Tao</font><font color="#cc0000"> </font><font color="#cc0000">Yue</font>
+
program TowersofHanoi;
−
<font color="#000000">  2:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">Date:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">13</font><font color="#cc0000"> </font><font color="#cc0000">July</font><font color="#cc0000"> </font><font color="#cc0000">2000</font>
+
 
−
<font color="#000000">  3:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">Description:</font>
+
var
−
<font color="#000000">  4:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">Solves</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">Towers</font><font color="#cc0000"> </font><font color="#cc0000">of</font><font color="#cc0000"> </font><font color="#cc0000">Hanoi</font>
+
  numdiscs : integer;
−
<font color="#990066">  5:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">Version:</font>
+
 
−
<font color="#000000">  6:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">1.0</font><font color="#cc0000"> </font><font color="#cc0000">-</font><font color="#cc0000"> </font><font color="#cc0000">original</font><font color="#cc0000"> </font><font color="#cc0000">version</font>
+
(********************************************************)
−
<font color="#000000">  7:</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
+
 
−
<font color="#000000">  8:</font>
+
procedure DoTowers (NumDiscs, OrigPeg, NewPeg, TempPeg : integer);
−
<font color="#000000">  9:</font> <font color="#006699"><strong>program</strong></font> TowersofHanoi<font color="#000000"><strong>;</strong></font>
+
(* Explanation of variables:
−
<font color="#990066">  10:</font>
+
      Number of discs -- number of discs on OrigPeg
−
<font color="#000000">  11:</font> <font color="#006699"><strong>var</strong></font>
+
      OrigPeg -- peg number of the tower
−
<font color="#000000">  12:</font>  numdiscs <font color="#000000"><strong>:</strong></font> <font color="#0099ff"><strong>integer</strong></font><font color="#000000"><strong>;</strong></font>
+
      NewPeg -- peg number to move the tower to
−
<font color="#000000">  13:</font>
+
      TempPeg -- peg to use for temporary storage
−
<font color="#000000">  14:</font> <font color="#cc0000">(*</font><font color="#cc0000">******************************************************</font><font color="#cc0000">*)</font>
+
*)
−
<font color="#990066">  15:</font>
+
 
−
<font color="#000000">  16:</font> <font color="#006699"><strong>procedure</strong></font> DoTowers <font color="#000000"><strong>(</strong></font>NumDiscs<font color="#000000"><strong>,</strong></font> OrigPeg<font color="#000000"><strong>,</strong></font> NewPeg<font color="#000000"><strong>,</strong></font> TempPeg <font color="#000000"><strong>:</strong></font> <font color="#0099ff"><strong>integer</strong></font><font color="#000000"><strong>)</strong></font><font color="#000000"><strong>;</strong></font>
+
begin
−
<font color="#000000">  17:</font> <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">Explanation</font><font color="#cc0000"> </font><font color="#cc0000">of</font><font color="#cc0000"> </font><font color="#cc0000">variables:</font>
+
  (* Take care of the base case -- one disc *)
−
<font color="#000000">  18:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">Number</font><font color="#cc0000"> </font><font color="#cc0000">of</font><font color="#cc0000"> </font><font color="#cc0000">discs</font><font color="#cc0000"> </font><font color="#cc0000">--</font><font color="#cc0000"> </font><font color="#cc0000">number</font><font color="#cc0000"> </font><font color="#cc0000">of</font><font color="#cc0000"> </font><font color="#cc0000">discs</font><font color="#cc0000"> </font><font color="#cc0000">on</font><font color="#cc0000"> </font><font color="#cc0000">OrigPeg</font>
+
  if NumDiscs = 1 then
−
<font color="#000000">  19:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">OrigPeg</font><font color="#cc0000"> </font><font color="#cc0000">--</font><font color="#cc0000"> </font><font color="#cc0000">peg</font><font color="#cc0000"> </font><font color="#cc0000">number</font><font color="#cc0000"> </font><font color="#cc0000">of</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">tower</font>
+
      writeln (OrigPeg, ' ---> ', NewPeg)
−
<font color="#990066">  20:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">NewPeg</font><font color="#cc0000"> </font><font color="#cc0000">--</font><font color="#cc0000"> </font><font color="#cc0000">peg</font><font color="#cc0000"> </font><font color="#cc0000">number</font><font color="#cc0000"> </font><font color="#cc0000">to</font><font color="#cc0000"> </font><font color="#cc0000">move</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">tower</font><font color="#cc0000"> </font><font color="#cc0000">to</font>
+
  (* Take care of all other cases *)
−
<font color="#000000">  21:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">TempPeg</font><font color="#cc0000"> </font><font color="#cc0000">--</font><font color="#cc0000"> </font><font color="#cc0000">peg</font><font color="#cc0000"> </font><font color="#cc0000">to</font><font color="#cc0000"> </font><font color="#cc0000">use</font><font color="#cc0000"> </font><font color="#cc0000">for</font><font color="#cc0000"> </font><font color="#cc0000">temporary</font><font color="#cc0000"> </font><font color="#cc0000">storage</font>
+
  else
−
<font color="#000000">  22:</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
+
      begin
−
<font color="#000000">  23:</font>
+
        (* First, move all discs except the bottom disc
−
<font color="#000000">  24:</font> <font color="#006699"><strong>begin</strong></font>
+
            to TempPeg, using NewPeg as the temporary peg
−
<font color="#990066">  25:</font>  <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">Take</font><font color="#cc0000"> </font><font color="#cc0000">care</font><font color="#cc0000"> </font><font color="#cc0000">of</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">base</font><font color="#cc0000"> </font><font color="#cc0000">case</font><font color="#cc0000"> </font><font color="#cc0000">--</font><font color="#cc0000"> </font><font color="#cc0000">one</font><font color="#cc0000"> </font><font color="#cc0000">disc</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
+
            for this transfer *)
−
<font color="#000000">  26:</font>  <font color="#006699"><strong>if</strong></font> NumDiscs <font color="#000000"><strong>=</strong></font> <font color="#ff0000">1</font> <font color="#006699"><strong>then</strong></font>
+
        DoTowers (NumDiscs-1, OrigPeg, TempPeg, NewPeg);
−
<font color="#000000">  27:</font>    writeln <font color="#000000"><strong>(</strong></font>OrigPeg<font color="#000000"><strong>,</strong></font> <font color="#ff00cc">'</font><font color="#ff00cc"> </font><font color="#ff00cc">---&gt;</font><font color="#ff00cc"> </font><font color="#ff00cc">'</font><font color="#000000"><strong>,</strong></font> NewPeg<font color="#000000"><strong>)</strong></font>
+
        (* Now, move the bottommost disc from OrigPeg
−
<font color="#000000">  28:</font>  <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">Take</font><font color="#cc0000"> </font><font color="#cc0000">care</font><font color="#cc0000"> </font><font color="#cc0000">of</font><font color="#cc0000"> </font><font color="#cc0000">all</font><font color="#cc0000"> </font><font color="#cc0000">other</font><font color="#cc0000"> </font><font color="#cc0000">cases</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
+
            to NewPeg *)
−
<font color="#000000">  29:</font>  <font color="#006699"><strong>else</strong></font>
+
        writeln (OrigPeg, ' ---> ', NewPeg);
−
<font color="#990066">  30:</font>  <font color="#006699"><strong>begin</strong></font>
+
        (* Finally, move the discs which are currently on
−
<font color="#000000">  31:</font>    <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">First,</font><font color="#cc0000"> </font><font color="#cc0000">move</font><font color="#cc0000"> </font><font color="#cc0000">all</font><font color="#cc0000"> </font><font color="#cc0000">discs</font><font color="#cc0000"> </font><font color="#cc0000">except</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">bottom</font><font color="#cc0000"> </font><font color="#cc0000">disc</font>
+
            TempPeg to NewPeg, using OrigPeg as the temporary
−
<font color="#000000">  32:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">to</font><font color="#cc0000"> </font><font color="#cc0000">TempPeg,</font><font color="#cc0000"> </font><font color="#cc0000">using</font><font color="#cc0000"> </font><font color="#cc0000">NewPeg</font><font color="#cc0000"> </font><font color="#cc0000">as</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">temporary</font><font color="#cc0000"> </font><font color="#cc0000">peg</font>
+
            peg for this transfer *)
−
<font color="#000000">  33:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">for</font><font color="#cc0000"> </font><font color="#cc0000">this</font><font color="#cc0000"> </font><font color="#cc0000">transfer</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
+
        DoTowers (NumDiscs-1, TempPeg, NewPeg, OrigPeg)
−
<font color="#000000">  34:</font>    DoTowers <font color="#000000"><strong>(</strong></font>NumDiscs<font color="#000000"><strong>-</strong></font><font color="#ff0000">1</font><font color="#000000"><strong>,</strong></font> OrigPeg<font color="#000000"><strong>,</strong></font> TempPeg<font color="#000000"><strong>,</strong></font> NewPeg<font color="#000000"><strong>)</strong></font><font color="#000000"><strong>;</strong></font>
+
      end
−
<font color="#990066">  35:</font>    <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">Now,</font><font color="#cc0000"> </font><font color="#cc0000">move</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">bottommost</font><font color="#cc0000"> </font><font color="#cc0000">disc</font><font color="#cc0000"> </font><font color="#cc0000">from</font><font color="#cc0000"> </font><font color="#cc0000">OrigPeg</font>
+
end;
−
<font color="#000000">  36:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">to</font><font color="#cc0000"> </font><font color="#cc0000">NewPeg</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
+
 
−
<font color="#000000">  37:</font>    writeln <font color="#000000"><strong>(</strong></font>OrigPeg<font color="#000000"><strong>,</strong></font> <font color="#ff00cc">'</font><font color="#ff00cc"> </font><font color="#ff00cc">---&gt;</font><font color="#ff00cc"> </font><font color="#ff00cc">'</font><font color="#000000"><strong>,</strong></font> NewPeg<font color="#000000"><strong>)</strong></font><font color="#000000"><strong>;</strong></font>
+
(********************************************************)
−
<font color="#000000">  38:</font>    <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">Finally,</font><font color="#cc0000"> </font><font color="#cc0000">move</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">discs</font><font color="#cc0000"> </font><font color="#cc0000">which</font><font color="#cc0000"> </font><font color="#cc0000">are</font><font color="#cc0000"> </font><font color="#cc0000">currently</font><font color="#cc0000"> </font><font color="#cc0000">on</font>
+
 
−
<font color="#000000">  39:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">TempPeg</font><font color="#cc0000"> </font><font color="#cc0000">to</font><font color="#cc0000"> </font><font color="#cc0000">NewPeg,</font><font color="#cc0000"> </font><font color="#cc0000">using</font><font color="#cc0000"> </font><font color="#cc0000">OrigPeg</font><font color="#cc0000"> </font><font color="#cc0000">as</font><font color="#cc0000"> </font><font color="#cc0000">the</font><font color="#cc0000"> </font><font color="#cc0000">temporary</font>
+
 
−
<font color="#990066">  40:</font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000"> </font><font color="#cc0000">peg</font><font color="#cc0000"> </font><font color="#cc0000">for</font><font color="#cc0000"> </font><font color="#cc0000">this</font><font color="#cc0000"> </font><font color="#cc0000">transfer</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
+
begin    (* Main *)
−
<font color="#000000">  41:</font>    DoTowers <font color="#000000"><strong>(</strong></font>NumDiscs<font color="#000000"><strong>-</strong></font><font color="#ff0000">1</font><font color="#000000"><strong>,</strong></font> TempPeg<font color="#000000"><strong>,</strong></font> NewPeg<font color="#000000"><strong>,</strong></font> OrigPeg<font color="#000000"><strong>)</strong></font>
+
  write ('Please enter the number of discs in the tower ===> ');
−
<font color="#000000">  42:</font>  <font color="#006699"><strong>end</strong></font>
+
  readln (numdiscs);
−
<font color="#000000">  43:</font> <font color="#006699"><strong>end</strong></font><font color="#000000"><strong>;</strong></font>
+
  writeln;
−
<font color="#000000">  44:</font>
+
  DoTowers (numdiscs, 1, 3, 2)
−
<font color="#990066">  45:</font> <font color="#cc0000">(*</font><font color="#cc0000">******************************************************</font><font color="#cc0000">*)</font>
+
end.    (* Main *)
−
<font color="#000000">  46:</font>
+
</delphi>
−
<font color="#000000">  47:</font>
 
−
<font color="#000000">  48:</font> <font color="#006699"><strong>begin</strong></font>   <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">Main</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
 
−
<font color="#000000">  49:</font>  <font color="#009966"><strong>write</strong></font> <font color="#000000"><strong>(</strong></font><font color="#ff00cc">'</font><font color="#ff00cc">Please</font><font color="#ff00cc"> </font><font color="#ff00cc">enter</font><font color="#ff00cc"> </font><font color="#ff00cc">the</font><font color="#ff00cc"> </font><font color="#ff00cc">number</font><font color="#ff00cc"> </font><font color="#ff00cc">of</font><font color="#ff00cc"> </font><font color="#ff00cc">discs</font><font color="#ff00cc"> </font><font color="#ff00cc">in</font><font color="#ff00cc"> </font><font color="#ff00cc">the</font><font color="#ff00cc"> </font><font color="#ff00cc">tower</font><font color="#ff00cc"> </font><font color="#ff00cc">===&gt;</font><font color="#ff00cc"> </font><font color="#ff00cc">'</font><font color="#000000"><strong>)</strong></font><font color="#000000"><strong>;</strong></font>
 
−
<font color="#990066">  50:</font>  readln <font color="#000000"><strong>(</strong></font>numdiscs<font color="#000000"><strong>)</strong></font><font color="#000000"><strong>;</strong></font>
 
−
<font color="#000000">  51:</font>  writeln<font color="#000000"><strong>;</strong></font>
 
−
<font color="#000000">  52:</font>  DoTowers <font color="#000000"><strong>(</strong></font>numdiscs<font color="#000000"><strong>,</strong></font> <font color="#ff0000">1</font><font color="#000000"><strong>,</strong></font> <font color="#ff0000">3</font><font color="#000000"><strong>,</strong></font> <font color="#ff0000">2</font><font color="#000000"><strong>)</strong></font>
 
−
<font color="#000000">  53:</font> <font color="#006699"><strong>end</strong></font><font color="#000000"><strong>.</strong></font>     <font color="#cc0000">(*</font><font color="#cc0000"> </font><font color="#cc0000">Main</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
 
  
 
{|style=color-backgroud="white" cellspacing="20"
 
{|style=color-backgroud="white" cellspacing="20"

Revision as of 17:46, 5 January 2010

4Ga - Solution to Towers of Hanoi (author: Tao Yue, state: unchanged) <delphi> (* Author: Tao Yue 

  Date:      13 July 2000
  Description:
     Solves the Towers of Hanoi
  Version:
     1.0 - original version
  • )

program TowersofHanoi;

var 

  numdiscs : integer;

(********************************************************)

procedure DoTowers (NumDiscs, OrigPeg, NewPeg, TempPeg : integer); (* Explanation of variables: 

     Number of discs -- number of discs on OrigPeg
     OrigPeg -- peg number of the tower
     NewPeg -- peg number to move the tower to
     TempPeg -- peg to use for temporary storage
  • )

begin 

  (* Take care of the base case -- one disc *)
  if NumDiscs = 1 then
     writeln (OrigPeg, ' ---> ', NewPeg)
  (* Take care of all other cases *)
  else
     begin
        (* First, move all discs except the bottom disc
           to TempPeg, using NewPeg as the temporary peg
           for this transfer *)
        DoTowers (NumDiscs-1, OrigPeg, TempPeg, NewPeg);
        (* Now, move the bottommost disc from OrigPeg
           to NewPeg *)
        writeln (OrigPeg, ' ---> ', NewPeg);
        (* Finally, move the discs which are currently on
           TempPeg to NewPeg, using OrigPeg as the temporary
           peg for this transfer *)
        DoTowers (NumDiscs-1, TempPeg, NewPeg, OrigPeg)
     end

end;

(********************************************************)


begin (* Main *) 

  write ('Please enter the number of discs in the tower ===> ');
  readln (numdiscs);
  writeln;
  DoTowers (numdiscs, 1, 3, 2)

end. (* Main *) </delphi>

previous contents next
Retrieved from "http://wiki.freepascal.org/index.php?title=Basic_Pascal_Tutorial/Chapter_4/Solution&oldid=40200"