|
|
(7 intermediate revisions by 6 users not shown) |
Line 1: |
Line 1: |
| + | {{Basic Pascal Tutorial/Chapter 4/Solution}} |
| + | {{TYNavigator|Chapter 4/Programming Assignment|Chapter 5/Enumerated types}} |
| + | |
| 4Ga - Solution to Towers of Hanoi (author: Tao Yue, state: unchanged) | | 4Ga - Solution to Towers of Hanoi (author: Tao Yue, state: unchanged) |
| + | <syntaxhighlight lang=pascal> |
| + | (* 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; |
| + | |
| + | (********************************************************) |
| + | |
| | | |
− | <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>
| + | begin (* Main *) |
− | <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>
| + | write ('Please enter the number of discs in the tower ===> '); |
− | <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>
| + | readln (numdiscs); |
− | <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>
| + | writeln; |
− | <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>
| + | DoTowers (numdiscs, 1, 3, 2) |
− | <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>
| + | end. (* Main *) |
− | <font color="#000000"> 7:</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
| + | </syntaxhighlight> |
− | <font color="#000000"> 8:</font>
| |
− | <font color="#000000"> 9:</font> <font color="#006699"><strong>program</strong></font> TowersofHanoi<font color="#000000"><strong>;</strong></font>
| |
− | <font color="#990066"> 10:</font>
| |
− | <font color="#000000"> 11:</font> <font color="#006699"><strong>var</strong></font>
| |
− | <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>
| |
− | <font color="#000000"> 13:</font>
| |
− | <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>
| |
− | <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>
| |
− | <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>
| |
− | <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>
| |
− | <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>
| |
− | <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>
| |
− | <font color="#000000"> 22:</font><font color="#cc0000"> </font><font color="#cc0000">*)</font>
| |
− | <font color="#000000"> 23:</font>
| |
− | <font color="#000000"> 24:</font> <font color="#006699"><strong>begin</strong></font>
| |
− | <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>
| |
− | <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>
| |
− | <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">---></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"> 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>
| |
− | <font color="#000000"> 29:</font> <font color="#006699"><strong>else</strong></font>
| |
− | <font color="#990066"> 30:</font> <font color="#006699"><strong>begin</strong></font>
| |
− | <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>
| |
− | <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>
| |
− | <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>
| |
− | <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>
| |
− | <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>
| |
− | <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">---></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>
| |
− | <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>
| |
− | <font color="#000000"> 42:</font> <font color="#006699"><strong>end</strong></font>
| |
− | <font color="#000000"> 43:</font> <font color="#006699"><strong>end</strong></font><font color="#000000"><strong>;</strong></font>
| |
− | <font color="#000000"> 44:</font>
| |
− | <font color="#990066"> 45:</font> <font color="#cc0000">(*</font><font color="#cc0000">******************************************************</font><font color="#cc0000">*)</font>
| |
− | <font color="#000000"> 46:</font>
| |
− | <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">===></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" | + | {{TYNavigator|Chapter 4/Programming Assignment|Chapter 5/Enumerated types}} |
− | |[[Programming_Assignment_4|previous]]
| |
− | |[[Contents|contents]]
| |
− | |[[Enumerated_types|next]]
| |
− | |} | |