cdat

一本全面剖析C++数据结构算法的书籍

Since @n@ = 60 in the Tower of Brahma,
it will take the Brahman priests quite a few years to finish their task.
From the solution to the above recurrence, we also obtain @t(n)@ =
\(*H(@2 sup n@).
.pp
While the output from ?P{hanoi} is enough for us to manually move the
disks, it isn't adequate if we wish to animate the move sequence
on a computer display.  Another deficiency is that it doesn't explicitly
specify the label of the disk that is to be moved.  So, if we make an error in
following the move sequence output by ?P{hanoi}, this error may not be detected till several moves later.  To rectify these deficiencies, we may store the state
of the three towers in memory.  This state information is easily displayed
on a computer screen for animation purposes and is also useful to output the
label of the disk being moved.
.pp
Since disks are removed from each tower in a last in first out manner,
each tower may be represented as a stack.  The three towers together contain
exactly @n@ disks at any time.  So, using linked stacks,
we can get by with space for @n@ elements.  If formula-based stacks are used,
towers 1 and 2 must have a capacity of @n@ disks each
while tower 3 must have a capacity of @n^-^1@.
So, space for a total of @3n^-^1@ disks is needed.
As our earlier analysis has shown, the complexity of the Towers of Hanoi
problem is exponential in @n@.  So, using a reasonable
amount of computer time, the problem can be solved only for
small values of @n@ (say @n@ \(<= 30).  For these small values of @n@,
the difference in space required by the formula-based and
linked representations is sufficiently small that either may be used.
.pp
The code of ?P{hanoi2} uses formula-based stacks.
@TowersOfHanoi(n)@ is just a preprocessor for the recursive function
@Hanoi::TowersOfHanoi@ which is modeled after the function of
?P{hanoi}.  The preprocessor creates the three stacks @S[1^:^3]@
that will store the states of the three towers.
The disks are
numbered 1 (smallest) through @n@ (largest).
As a result, each stack is of type \fBint\fR.
The preprocessor returns 0 in case enough space is not
available to create these three stacks.
When enough space is available, it invokes @Hanoi::TowersOfHanoi@
and returns 1 after the necessary moves have been successfully output.
.KF
.nf
.hl
.ft CW
class Hanoi {
public:
   void TowersOfHanoi(int n, int x, int y, int z);
   Stack<int> *S[4];
};

void Hanoi::TowersOfHanoi(int n, int x, int y, int z)
{//Move the top n disks from tower x to tower y
//Use tower z for intermediate storage
int i;
if (n > 0) {
   TowersOfHanoi(n-1, x, z, y);
   (*S[x]) - i;  (*S[y]) + i;
   cout << "Move disk " << i << " from tower " << x
	<< " to tower " << y << endl;
   TowersOfHanoi(n-1, z, y, x);}
}

int TowersOfHanoi(int n)
{//preprocessor for Hanoi::TowersOfHanoi
Hanoi X;
X.S[1] = new Stack<int> (n);
X.S[2] = new Stack<int> (n);
X.S[3] = new Stack<int> (n - 1);
if (!X.S[2] || !X.S[3]) return 0;
for (int i = n; i > 0; i--) //initialize
   (*X.S[1]) + i; //add disk i to tower 1
X.TowersOfHanoi(n, 1, 2, 3);
return 1;
}
.ft R
.hl
\fB?P{hanoi2}:\fR Towers of Hanoi using stacks
.fi
.KE
.NH 3
Rearranging Railroard Cars
.LP
.sp
A freight train has @n@ railroard cars.  Each is to be
left at a different station.  Assume that the @n@ stations are numbered
1 through @n@ and that the freight train visits these in the
order @n@ through 1.   The railroad cars are labeled by their
destination.  To facilitate removal of the railroad cars from the
train it is necessary to reorder the cars so that they are
in the order 1 through @n@ front-to-back.  When the cars are
in this order, the last car is detached at each station.
The rearrangement of cars is done at a shunting yard which is
comprised of an \fIinput track\fR, an \fIoutput track\fR, and
@k@ holding tracks that lie between the input and output tracks.
?F{shunt}(a) shows a shunting yard with @k@ = 3 holding
tracks @H1@, @H2@, and @H3@.
The @n@ cars of the freight train begin in the input track
and are to end up in the output track in the order 1 through @n@
right-to-left.
In ?F{shunt}(a), we have @n@ = 9 and the cars are initially in the
order 5, 8, 1, 7, 4, 2, 9, 6, 3 back-to-front.  ?F{shunt}(b)
shows the cars rearranged in the desired order.
.KF
.hl
.PS
boxwid = 0.25i; boxht = boxwid;
x = 0.9i
y = .25i
h = 0.5i
A:[
A:Here
line thick 10 from A to A+(2*x+2*y,0)
line thick 10 from A+(x,0) to A+(x,-h)
line thick 10 from A+(x+y,0) to A+(x+y,-h)
line thick 10 from A+(x+2*y,0) to A+(x+2*y,-h)
"[581742963]" at A+(x/2,.2)
"input track" at A+(x/2,-0.2)
"output track" at A+(3/2*x+2*y,-0.2)
"@H1@" at A+(x,-h-0.2)
"@H2@" at A+(x+y,-h-0.2)
"@H3@" at A+(x+2*y,-h-0.2)
]
"(a) Initial" at last [].s-(0,.5)
B:[
A:Here
line thick 10 from A to A+(2*x+2*y,0)
line thick 10 from A+(x,0) to A+(x,-h)
line thick 10 from A+(x+y,0) to A+(x+y,-h)
line thick 10 from A+(x+2*y,0) to A+(x+2*y,-h)
"[987654321]" at A+(3/2*x+2*y,.2)
"@H1@" at A+(x,-h-0.2)
"@H2@" at A+(x+y,-h-0.2)
"@H3@" at A+(x+2*y,-h-0.2)
] with .nw at A.ne+(0.4,0)
"(b) Final" at last [].s-(0,.5)
.PE
.hl
\fB?F{shunt}:\fR A three track example
.KE
.pp
To rearrange the cars, we examine the cars on the input track
front-to-back.  If the car being examined is the next
one in the output arrangement, it is moved directly to the
output track.  If not, it is moved to a holding track and left there
until it is time to place it in the output.
The holding tracks operate in a LIFO manner as cars enter and leave
these from the top of the track.
When rearranging cars, the following moves are permitted:
.US
.np
A car may be moved from the front (i.e., right end)
of the input track to the top
of one of the holding tracks or to the left end of the output track.
.np
A car may be moved from the top of a holding track to the left end of the output track.
.US
.pp
\fIAll other moves are forbidden\fR.
Consider the input arrangement of ?F{shunt}(a).  Car 3 is at the front.
This cannot be output yet as it is to be preceded by cars 1 and 2.
So, it is detached and moved to the holding track @H1@.
The next car, car 6, is also to be moved to a holding track.
If it is moved to @H1@, the rearrangement
cannot be completed as car 3 will be below car 6.  However,
car 3 is to be output before car 6 and so must leave @H1@ before car 6
does.
So, car 6 is put into @H2@.
The next car, car 9 is put into @H3@ as putting it into either @H1@
or @H2@ will make it impossible to complete the rearrangement.
\fINotice that whenever the car labels in a holding track are not
in increasing order top-to-bottom, the rearrangement cannot be completed\fR.
The current state of the holding tracks is shown in ?F{tracks}(a).
.KF
.hl
.PS
boxwid = 0.25i; boxht = boxwid;
d = .25i
s = 0.1i
A:[
A:box shade 5
box "3" at A
B:box shade 5 with .w at A.e+(d,0)
box "6" at B
C:box shade 5 with .w at B.e+(d,0)
box "9" at C
"@H1@" at A.s-(0,0.2)
"@H2@" at B.s-(0,0.2)
"@H3@" at C.s-(0,0.2)
]
"(a)" at last [].s-(0,.5)
B:[
A:box shade 5
box "3" at A
B:box shade 5 with .w at A.e+(d,0)
box "6" at B
C:box shade 5 with .w at B.e+(d,0)
box "9" at C
D: box shade 10 with .b at A.t+(0,s)
"2" at D
E: box shade 10 with .b at B.t+(0,s)
"4" at E
F: box shade 10 with .b at C.t+(0,s)
"7" at F
"@H1@" at A.s-(0,0.2)
"@H2@" at B.s-(0,0.2)
"@H3@" at C.s-(0,0.2)
] with .sw at A.se+(1,0)
"(b)" at last [].s-(0,.5)
.PE
.hl
\fB?F{tracks}:\fR Track states
.KE
.pp
Car 2 is considered next.  While it can be moved into any of the holding tracks
while satisfying the requirement that car labels in any holding track be
in increasing order, moving it to @H1@ is preferred.  If it is moved to
@H3@, then we have no place to move cars 7 and 8.  If we move it to @H2@,
then the next car, car 4, will have to be moved to @H3@ and we will have
no place for cars 5, 7, and 8.  \fIThe least restrictions on future
car placement arises when the new car @u@ is moved to the holding track
which has at its top a car with smallest label @v@ such that @v@ > @u@\fR.
We shall use this \fIassignment rule\fR to select the holding track.
.pp
When car 4 is considered, the cars at the top of the three holding tracks
are 2, 6, and 9.  Using our assignment rule, car 4 is moved to @H2@.
Car 7 is then moved to @H3@.
?F{tracks}(b) shows the current state of the holding tracks.
The next car, car 1, is moved to the output track.
It is now time to move car 2 from @H1@ to the output track.
Next, car 3 is moved from @H1@ and then car 4 moved from @H2@.
No other cars can be moved to the output at this time.
.pp
The next input car, car 8, is moved to @H1@.  Then car 5 is moved from
the input track to the output track.  Following this, car 6 is moved from @H2@.
Then car 7 is moved from @H3@, car 8 from @H1@, and car 9 from @H3@.
.pp
While three holding tracks are sufficient to rearrange the cars from
the initial ordering of ?P{shunt}(a), more tracks are needed for other
initial arrangements.  For example, the initial arrangement
1, @n@, @n^-^1@, @...@, 2 requires @n^-^1@ holding tracks.
.pp
To implement the above rearrangement scheme, we use @k@ linked stacks
to represent the @k@ holding tracks.  Linked stacks are used rather than
formula-based ones as by doing so, the space required is that
for only @n^-^1@ elements.
Function @Railroard@ (?P{rail1}) outputs a sequence of move that
results in rearranging @n@ cars with initial ordering @p[1^:^n]@.
It attempts to do this using at most @k@ holding tracks.  In case it fails
for lack of tracks, it returns 0.  If failure is due to lack of memory,
it returns @-@1.  On success, it returns 1.
.KF
.nf
.hl
.ft CW
int Railroad(int *p, int n, int k)
{//k track rearrangement of car order p[1:n]
//initialize holding tracks
LinkedStack<int> *H;
H = new LinkedStack<int> [k + 1];
if (!H) return -1;
//rearrange
int NowOut = 1, minH = n+1, minS;
for (int i = 1; i <= n; i++) {
   if (p[i] == NowOut) {
      cout << "Move car " << p[i] <<
        " from input to output" << endl;
      NowOut++;
      while (minH == NowOut) {
         Output(minH, minS, H, k, n);
	 NowOut++;}}
   else {//move to a holding track
      int x = Hold(p[i], minH, minS, H, k, n);
      if (x < 1) return x;}
   }
return 1;
}
.ft R
.hl
\fB?P{rail1}:\fR Railroad car rearrangement program
.fi
.KE
.pp
Function @Railroad@ begins by initializing the linked stack array @H@.
@H[i]@ represents holding track @i@, @1~<=~i~<=~k@.  @NowOut@ is the label
of the car that is to go to the output track next; @minH@ is the smallest
label in any of the holding tracks, and @minS@ is the holding track
(or stack) that contains the car with label @minH@.
The \fBfor\fR loop maintains the invariant \fIat the start of this loop,
the car with label @NowOut@ is not in a holding track\fR.
.pp
In iteration @i@ of the \fBfor\fR loop, car @p[i]@ is moved from the
input track.  This car is to move to the output track
only if @p[i]@ equals @NowOut@.  If car @p[i]@ is moved to the output track,
@NowOut@ increases by one and it may be possible to move one or more of
the cars in the holding tracks out.  This is done in the \fBwhile\fR
loop.
If car @p[i]@ cannot be moved to the output, then no car can be so moved.
Consequently, @p[i]@ is added to a holding track using the stated
track assignment rule.
.pp
The functions @Output@ and @Hold@ utilized by @Railroad@ are given
in Programs ?p{rail.o} and ?p{rail.h} respectively.
@Output@ outputs instructions to move a car from a holding track
to the output track.  It also updates @minH@ and @minS@.
The function @Hold@ puts car @c@ into a holding track using the track
assignment rule.  It also outputs instructions to move the car
to the chosen holding track and updates @minH@ and @minS@
if necessary.
.KF
.nf
.hl
.ft CW
void Output(int& minH, int& minS,
        LinkedStack<int> *H, int k, int n)
{//move from hold to output
int x;
H[minS] - x;
cout << "Move car " << minH << " from holding track "
     << minS << " to output" << endl;
minH = n + 2;
for (int i = 1; i <= k; i++)
   if (H[i].Top(x) && x < minH) {
      minH = x; minS = i;}
}
.ft R
.hl
\fB?P{rail.o}:\fR @Output@ function used in ?P{rail1}
.fi
.KE
.KF
.nf
.hl