Question

我读到Cormen动态节目,等等算法书籍。以下为书本:

我们拥有汽车工厂,有两条长线,称为第1线和线 2. 结论我们必须确定最快的时间,以获得一切帮助。

最终目标是确定最快的时间,以便通过工厂全方位获得粉碎。混乱必须完全通过第1行或第2行的“n”站,然后从工厂撤出。由于这些途径的加快是整个工厂最快的通道,我们已经做到了。

Fn = min(f1[n] + x1, f2[n]+x2) ---------------- Eq1

Above x1 and x2 final additional time for comming out from line 1 and line 2

我一直在重复。考虑如下:Eq2。

f1[j]  = e1 + a1,1                                    if j = 1
             min(f1[j-1] + a1,j, f2[j-1] + t2,j-1 + a1,j  if j >= 2

f2[j]  = e2 + a2,1                                    if j = 1
             min(f2[j-1] + a2,j, f1[j-1] + t1,j-1 + a2,j  if j >= 2

允许Ri(j)在一次收回算法中注明出处的次数。

R1(n)=R2(n)=1

从上表2看,我们

R1(j) = R2(j) = R1(j+1) + R2(j+1)  for j = 1, 2, ...n-1

My question is how author came with R(n) =1 because usally we have base case as 0 rather than n, here then how we will write recursive functions in code for example C code?

另一个问题是,提交人是如何带R1(j)和R2(j)的?

感谢一切帮助。

Answer 1

If you solve the problem in a recursive way, what would you do? You d start calculating F(n). F(n) would recursively call f1(n-1) and f2(n-1) until getting to the leaves (f1(0), f2(0)), right?

So, that s the reason the number of references to F(n) in the recursive solution is 1, because you d need to compute f1(n) and f2(n) only once. This is not true to f1(n-1), which is referenced when you compute f1(n) and when you compute f2(n).

Now, how did he come up with R1(j) = R2(j) = R1(j+1) + R2(j+1)? well, computing it in a recursive way, every time you need f1(i), you have to compute f1(j), f2(j), for every j in the interval [0, i) -- AKA for every j smaller than i. In other words, the value of f1,2(i) depends on the value of f1,2(0..i-1), so every time you compute a f_(i), you re computing EVERY f1,2(1..i-1) - (because it depends on their value).

由于这个原因,你对e_(一)的计算次数取决于有多少1 210人“伪造他”。

希望是明确的。

友情链接