15.1.md

Exercises 15.1-1

---

Show how to modify the PRINT-STATIONS procedure to print out the stations in increasing order of station number. (Hint: Use recursion.)

Answer

It's very easy.see my implementation

Exercises 15.1-2

---

Use equations (15.8) and (15.9) and the substitution method to show that ri(j), the number of references made to fi[j] in a recursive algorithm, equals 2^(n - j).

Answer

1. j = n时,r(i,j) = 1 = 2^(n-n) 成立

2. 假设当j = k时, r(i,k) = 2^(n-k) <br > 当j = k -1时, r(i,k-1) = r(1,k)+r(2,k) = 2^(n-k) + 2^(n-k) = 2^(n-(k-1))

3. 综上所述, 等式成立

Exercises 15.1-3

---

Using the result of Exercise 15.1-2, show that the total number of references to all fi[j] values, or 

) , is exactly 2^(n+1) - 2.

Answer

 = 2(\sum_{j=1}^{n}2^{n-j}) = 2(2^n-1) = 2^{n+1}-1)

Exercises 15.1-4

---

Together, the tables containing fi[j] and li[j] values contain a total of 4n - 2 entries. Show how to reduce the space requirements to a total of 2n + 2 entries, while still computing f* and still being able to print all the stations on a fastest way through the factory.

Answer

It's simple.when we calculate f(n),we just need f(n-1).so we just alloc f1[2] and f2[2].

Exercises 15.1-5

---

Professor Canty conjectures that there might exist some ei, ai,j, and ti,j values for which FASTEST-WAY produces li[j] values such that l1[j] = 2 and l2[j] = 1 for some station number j. Assuming that all transfer costs ti,j are nonnegative, show that the professor is wrong.

Answer

if l1[j] = 2,then f1[j-1]>f2[j-1]+t(2,j-1) ------ @1

if l2[j] = 1,then f2[j-1]>f1[j-1]+t(1,j-1) ------ @2

we add @1 and @2,find that t(1,j-1)+t(2,j-1) < 0 wrong !!!!!!

---

Follow @louis1992 on github to help finish this task.