Show how to modify the PRINT-STATIONS procedure to print out the stations in increasing order of station number. (Hint: Use recursion.)
It's very easy. See my implementation
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).
-
j = n时,r(i,j) = 1 = 2^(n-n) 成立
-
假设当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))
-
综上所述, 等式成立
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.
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.
It's simple. When we calculate f(n),we just need f(n-1).so we just alloc f1[2] and f2[2].
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.
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.