170 Intermediate C Programming
12.2 One-Way Streets
A B
C
D
E
F
FIGURE 12.3: A city’s streets form a grid, and are either east–west bound or north–south
bound. A car can move only east or north.
A city has severe traffic congestions during rush hours so the city government considers
adopting a rule: During rush hours, cars can move only east or north. All streets run either
east–west or north–south, forming a grid, as shown in Fig. 12.3.
Assume we had the location of a car’s origin and destination. How many ways can the
destination be reached by driving? This example may seem artificial but it is actually a
reasonable simplification of the one-way streets in the downtown districts of many cities.
These cities generally have one-way streets that run in opposite directions, so that cars can
move west and south as well. Nonetheless, the simplification is useful for analyzing traffic
patterns.
Fig. 12.3 marks three pairs of origins and destinations: A → B, C → D, and E → F.
How many turning options does a driver have going from one origin to their corresponding
destination? For the first two pairs A → B and C → D, the driver has only one option: not
to turn at all. This is shown in Fig. 12.4 (a) and (b). There are more options for E → F.
At E, the driver can go eastbound first or northbound first, as indicated by the two arrows
in Fig. 12.4 (c). The question is the number of different paths a driver can make between
the origin and the destination.
A B
C
D
E
F
(a)
A B
C
D
E
F
(b)
A B
C
D
E
F
(c)
FIGURE 12.4: (a) A driver cannot turn anywhere when traversing from A to B. (b)
Likewise, a driver cannot turn anywhere when traversing from C to D. (c) There are some
turning options when traversing from E to F. At E, the driver can go northbound first or
eastbound first, as indicated by the two arrows.
This question can be answered using the four steps for solving the recursive problem:
1. Identify the argument (or arguments) of a problem. Suppose E is at the intersection
of (x1, y1) and F is at the intersection of (x2, y2). The distance between them can be
expressed as (∆x, ∆y) = (x2 − x1, y2 − y1).
Recursion 171
2. Express the solution based on the arguments. Let f(∆x, ∆y) express the number of
unique paths.
3. Determine the simple case(s) when the solutions are “obvious”. If ∆x < 0, the desti-
nation is at the west side of the origin and there is no solution. Similarly, there is no
solution if ∆y < 0. If ∆x > 0 and ∆y = 0 (the case A → B), then there is precisely
one solution. Likewise, if ∆x = 0 and ∆y > 0 (the case C → D), there is also precisely
one solution. These are the simple cases whose answers can be found easily. A special
case occurs when ∆x = ∆y = 0. This means that the destination is the same as the
origin. It can be defined as no solution or one solution depending on what the reader
prefers. Our solution considers that there is one solution for ∆x = ∆y = 0.
f(∆x, ∆y) =
0 if ∆x < 0 or ∆y < 0
1 if ∆x = 0 and ∆y ≥ 0
1 if ∆x ≥ 0 and ∆y = 0.
(12.4)
4. Derive the relationships between the complex case(s) and the simpler case(s). When
∆x > 0 and ∆y > 0 (the case E → F), then the driver has two options at the origin
(i.e., E): Either the driver goes north first or east first. If the driver heads north, then
the new origin is at (x1, y1 + 1). There are f(∆x, ∆y − 1) possible paths from this
point. If the driver goes east first, then the new origin is at (x1 + 1, y1). Similarly,
there are f (∆x−1, ∆y) possible paths from this point. These are the only two possible
options at position E and they are exclusive. Therefore, when ∆x > 0 and ∆y > 0,
the solution can expressed as f (∆x, ∆y) = f (∆x, ∆y − 1) + f (∆x − 1, ∆y).
f(∆x, ∆y) =
0 if ∆x < 0 or ∆y < 0
1 if ∆x = 0 and ∆y ≥ 0
1 if ∆x ≥ 0 and ∆y = 0
f(∆x, ∆y − 1) + f (∆x − 1, ∆y) if ∆x > 0 and ∆y > 0
(12.5)
12.3 The Tower of Hanoi
A B C
(a)
⇒
A B C
(b)
FIGURE 12.5: The Tower of Hanoi. (a) Some disks are on pole A and the goal is to move
all the disks to pole B, as shown in (b). A larger disk can never be placed on top of a smaller
disk. A third pole, C, can be used when necessary.
Some disks of different sizes are stacked on a single pole. The disks are arranged so that
smaller disks are above larger disks. The problem is to move the disks from one pole to
172 Intermediate C Programming
A B C
(a)
⇒
A B C
(b)
FIGURE 12.6: Moving one disk from A to B requires only one step.
A B C
⇒
A B C
⇓
A B C
⇐
A B C
FIGURE 12.7: Moving two disks from A to B requires three steps.
another pole. Only one disk can be moved each time. A larger disk cannot be placed above
a smaller disk. The third pole can be used for “temporary storage”. Fig. 12.5 illustrates the
problem. If there are n disks, how many steps are needed to move them to the second pole?
First consider moving only one disk from A to B. This is the simplest case and that disk
can be moved directly from A to B as shown in Fig. 12.6.
Moving two disks requires more work. It is illegal to move the smaller disk to B and then
move the larger disk to B. Doing so would place the larger disk above the smaller disk and
violates the rules. Instead, it is necessary to move the smaller disk “somewhere else”, i.e.,
C, before moving the larger disk to B. Then, move the larger disk from A to B and move
the smaller disk from C to B. The steps are illustrated in Fig. 12.7. As illustrated, when
there are two disks, the problem can be solved in three steps. Can you think of a solution
that requires fewer steps for two disks?
Fig. 12.8 illustrates how to move three disks. The first three steps and the last three
steps are somewhat similar. The first three steps move the top two disks from A to C. The
last three steps move the top two disks from C to B. Between these steps is the fourth step,
which is to move the largest disk from A to B.
What is the general strategy for moving n disks? If there is only one disk (i.e., n is one),
the problem can be solved easily. Otherwise, the solution is divided into three parts:
1. Move the first n − 1 disks from A to C.
2. Move the largest disk from A to B.
3. Move the first n − 1 disks from C to B.
Now we put the steps together to solve the problem using recursion. The four-step
approach for solving this problem is listed below:
1. Identify the argument (or arguments) of a problem.
The number n is naturally the argument for the problem.
Recursion 173
A B C
⇒
A B C
⇓
A B C
⇐
A B C
⇓
A B C
⇒
A B C
⇓
A B C
⇐
A B C
FIGURE 12.8: Moving three disks from A to B requires seven steps.
2. Express the solution based on the arguments.
Let f(n) be the answer: how many steps are needed to move n disks from A to B.
3. Determine the simple case(s) when the solutions are “obvious”.
If n is one, only one step is sufficient; thus, f(1) is 1.
4. Derive the relationships between the complex case(s) and the simpler case(s).
When n is greater than one, the problem can be divided into three parts:
(a) Move n − 1 disks to pole C, which requires f(n − 1) steps.
(b) Move the largest disk to pole B, which requires 1 step.
(c) Move n − 1 disks from pole C to pole B, which requires f (n − 1) steps.
The following formula expresses the steps:
f(n) =
(
1 if n is 1
f(n − 1) + 1 + f (n − 1) = 2f(n − 1) + 1 if n ≥ 2
(12.6)
This is a recursive form, meaning that the formula is defined in terms of itself. This
works because the formula always references “smaller” versions of itself, until it gets to the
trivial case (n is 1). For example, notice how f(n) appears on one side of the = sign, and
f(n − 1) appears on the other side. Thus, when we expand f (n), we will need to expand
f(n − 1) and then f (n − 2), etc., until we reach f(1), which equals 1.
174 Intermediate C Programming
In this case it possible to find a closed form formula: f (n) is expressed without f(n − 1)
appearing on the right side of the = sign.
f(n) = 2f(n − 1) + 1
= 4f(n − 2) + 2 + 1
= 8f(n − 3) + 4 + 2 + 1
= 16f(n − 4) + 8 + 4 + 2 + 1
= 2
k
f(n − k) + 2
k−1
+ 2
k−2
+ ... + 4 + 2 + 1
= 2
n−1
f(1) + 2
n−2
+ 2
n−3
+ ... + 4 + 2 + 1, when k = n − 1
= 2
n−1
+ 2
n−2
+ 2
n−3
+ ... + 4 + 2 + 1, because f(1) = 1
= 2
n
− 1
(12.7)
It is not always possible, or easy, to find closed form formulas for recursive equations.
Usually this requires a working knowledge of various series. Proving the answer is correct
requires mathematical induction.
12.4 Calculating Integer Partitions
A positive integer can be expressed as the sum of a sequence of positive integers. An
integer partition creates such a sequence of integers. For example, 5 can be broken into
the sum of 1 + 2 + 2 or 2 + 3. These two partitions use different numbers, and thus
are considered unique integer partitions. The order of the number in the partition is also
important. Thus, 1 + 2 + 2 and 2 + 1 + 2 are considered different integer partitions because
1 appears in different positions. Below are some example integer partitions:
1 = 1 2 = 1 + 1 3 = 1 + 1 + 1 4 = 1 + 1 + 1 + 1
= 2 = 1 + 2 = 1 + 1 + 2
= 2 + 1 = 1 + 2 + 1
= 3 = 1 + 3
= 2 + 1 + 1
= 2 + 2
= 3 + 1
= 4
This question wants to answer the number of different partitions for a positive integer
n. This problem can be solved by using the four-step approach solving recursive problems:
1. Identify the argument (or arguments) of a problem.
The number n is naturally the argument for the problem.
2. Express the solution based on the arguments.
Let f(n) be the number of different partitions for integer n.
3. Determine the simple case(s) when the solutions are “obvious”.
When n is 1, there is only one way to partition the number: itself. When n is 2, there
are two ways: 1 + 1 and 2. Thus, f (1) = 1 and f(2) = 2.
4. Derive the relationships between the complex case(s) and the simpler case(s).
When n is larger than 2, the solution selects the first number. It must be an integer
between 1 and n inclusively. After selecting the first number, we have to partition
the remaining portion of the number. Thus for each of the n possibilities for the first
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.