练习 1.11

递归版本

直接将书本给出的定义『如果 \(n < 3\) 那么 \(f(n) = n\) ;如果 \(n \geq 3\) ,那么 \(f(n)=f(n-1) + 2f(n-2) + 3f(n-3)\) 』翻译成递归函数:

;;; 11-rec.scm

(define (f n)
    (if (< n 3)
        n
        (+ (f (- n 1))
           (* 2 (f (- n 2)))
           (* 3 (f (- n 3))))))

测试这个递归版的 f

1 ]=> (load "11-rec.scm")

;Loading "11-rec.scm"... done
;Value: f

1 ]=> (f 1)

;Value: 1

1 ]=> (f 3)

;Value: 4

1 ]=> (f 4)

;Value: 11

迭代版本

要写出函数 \(f\) 的迭代版本,关键是在于看清初始条件和之后的计算进展之间的关系,就像书本 25-26 页中,将斐波那契函数从递归改成迭代那样。

根据函数 \(f\) 的初始条件『如果 \(n < 3\) ,那么 \(f(n)=n\) 』,有等式:

\(f(0) = 0\)

\(f(1) = 1\)

\(f(2) = 2\)

另一方面, 根据条件『当 \(n \geq 3\) 时,有 \(f(n) = f(n-1)+2f(n-2)+3f(n-3)\) 』,如果继续计算下去,一个有趣的结果就会显现出来:

\(f(3) = f(2) + 2f(1) + 3f(0)\)

\(f(4) = f(3) + 2f(2) + 3f(1)\)

\(f(5) = f(4) + 2f(3) + 3f(2)\)

\(\dots\)

可以看出,当 \(n \geq 3\) 时,所有函数 \(f\) 的计算结果都可以用比当前 \(n\) 更小的三个 \(f\) 调用计算出来。

迭代版的函数定义如下:它使用 i 作为渐进下标, n 作为最大下标, abc 三个变量分别代表函数调用 \(f(i+2)\)\(f(i+1)\)\(f(i)\) ,从 \(f(0)\) 开始,一步步计算出 \(f(n)\)

;;; 11-iter.scm

(define (f n)
    (f-iter 2 1 0 0 n))

(define (f-iter a b c i n)
    (if (= i n)
        c
        (f-iter (+ a (* 2 b) (* 3 c))   ; new a
                a                       ; new b
                b                       ; new c
                (+ i 1)
                n)))

测试这个迭代版的函数:

1 ]=> (load "11-iter.scm")

;Loading "11-iter.scm"... done
;Value: f-iter

1 ]=> (f 1)

;Value: 1

1 ]=> (f 3)

;Value: 4

1 ]=> (f 4)

;Value: 11

效率对比

两个 \(f\) 函数不仅使用的计算方式不同(前一个递归计算,另一个迭代计算),而且效率方面也有很大的不同。

递归版本的函数 \(f\) 有很多多余的计算,比如说,要计算 \(f(5)\) 就得计算 \(f(4)\)\(f(3)\)\(f(2)\) ,而计算 \(f(4)\) 又要计算 \(f(3)\)\(f(2)\)\(f(1)\)

对于每个 \(f(n)\) 调用,递归版 \(f\) 函数都要执行 \(f(n-1)\)\(f(n-2)\)\(f(n-3)\) ,而 \(f(n-1)\) 的计算又重复了对 \(f(n-2)\)\(f(n-3)\) 的计算,因此,递归版本的 \(f\) 函数是一个指数级复杂度的算法(和递归版本的斐波那契数函数类似)。

另一方面,迭代版本使用三个变量储存 \(f(n-1)\)\(f(n-2)\)\(f(n-3)\) 的值,使用自底向上的计算方式进行计算,因此迭代版的函数 \(f\) 没有多余的重复计算工作,它的复杂度正比于 \(n\) ,是一个线性迭代函数。

See also

查看维基词条 Dynamic Programming 了解更多关于自底向上计算的信息。

讨论

blog comments powered by Disqus