Dopcn's Blog

life and work

递归、动态规划和迭代

Posted at — Nov 2, 2015

每一个计算机程序都是现实中或者精神中的某一个过程的一个模型 SICP 序 在这一层次的课程里,最基本的材料并不是特定的程序设计语言语法,不是有效计算某种功能的巧妙算法,也不是算法的数学分析或者计算的本质,而是一些能够用于控制大型软件系统的智力复杂性的技术 SICP 前言

计算机程序中对象可以大体分为两类:数据和过程。数据是那些需要去操作的东西,过程则是具体操作的指令。要求解复合过程的结果需要先得到子过程的结果,求子过程的结果需要得到子过程的子过程的结果,一次类推直到某一层子过程是最基本的表达式得到求值结果,这就是递归。

递归的简单应用,欧几里得算法求最大公约数

func gcd(x x: Int, y: Int) -> Int {
    if y == 0 {
        return x
    } else {
        return gcd(x: y, y: x%y)
    }
}

Fibonacci 数列求值

Fibonacci 数列的定义本身就是递归的,可以很自然的写成:

func fib1(n: Int) -> Int {
    switch n {
    case 0: return 0
    case 1: return 1
    default: return fib1(n-1) + fib1(n-2)
    }
}

这个方法在求解的过程中所需的步数随着n的增加增长阶是O(2^n),仔细观察递归过程中同样的值重复计算了很多次,于是可以优化在计算过程中把结果保留下来,这种做法被归类为 Dynamic Programming 方法,没想到的是中文翻译居然是动态规划

func fib2(n: Int) -> Int {
    var tmpArray = [0, 1]
    func fib2Inside(m: Int) -> Int {
        if m >= tmpArray.count {
            tmpArray.append(fib2Inside(m-1) + fib2Inside(m-2))
        }
        return tmpArray[m]
    }
    return fib2Inside(n)
}

在递归中有一类尾递归,可能也可以叫伪递归,是在递归的过程中保留全部状态,其实就是一种迭代,这种计算方式要快于一般的递归。如果递归解决的思路是从后往前的,那么迭代刚好相反是从前往后

func fib3(n: Int) -> Int {
    func fibIter(a: Int, b: Int, count: Int) -> Int {
        if count == 0 {
            return b
        } else {
            return fibIter(a+b, b: a, count: count-1)
        }
    }
    return fibIter(1, b: 0, count: n)
}

func fib4(n: Int) -> Int {
    guard n > 1 else {
        return n
    }
    var count = n, x = 0, y = 1
    repeat {
        (x, y) = (y, x+y)
        count--
    } while count > 1
    return y
}

使用迭代的方式计算,计算步数相对于n的增长阶是O(n),如果要继续精简这个计算过程发现每次迭代的变化都是一样的,那么将两次迭代的过程合为一次,那么所需步骤数就可以减半,最后得到时间复杂度为 O(logn) 的方法。

func fib5(n: Int) -> Int {
    guard n > 1 else {
        return n
    }
    var count = n+1, x = 0 , y = 1
    if count % 2 != 0 {
        (x, y) = (y, x+y)
        count--
    }
    var countHalf = count/2
    repeat {
        (x, y) = (x+y, x+2*y)
        countHalf--
    } while countHalf > 1
    return y
}

零钱组合问题

给定一个金额 N,计算有多少种不同的零钱组合方式。这个问题应用递归就没有上一个那么直观,但只需要找出分解问题并且子问题和问题本身是同一类问题的方式。将换算组合个数分为两部分,没有一种面值的组合个数加上至少有一张这种面值的组合个数

func cc1(amount: Int, denomination: Array<Int>) -> Int {
    if amount < 0 || denomination.count == 0 { return 0 }
    if amount == 0 { return 1 }
    var deno = denomination
    deno.removeLast()
    return cc1(amount - denomination[denomination.count-1], denomination: denomination) + cc1(amount, denomination: deno)
}

在 Dynamic Programming 的思想下优化,用一个表的行列代表金额数和不同面值个数,在表中存储计算过的个数

func cc2(amount: Int, denomination: Array<Int>) -> Int {
    var table = Array(count: amount+1, repeatedValue: Array(count: denomination.count+1, repeatedValue: -1))
    var i = 0, j = 0
    while j < denomination.count+1 {
        table[0][j] = 1
        j++
    }
    while i < amount+1 {
        table[i][0] = 0
        i++
    }
    func cc2Inside(amount2: Int, denomination2: Array<Int>) -> Int {
        if amount2 < 0 {
            return 0
        }
        if table[amount2][denomination2.count] == -1 {
            var deno = denomination2
            deno.removeLast()
            table[amount2][denomination2.count] = cc2Inside(amount2-denomination2[denomination2.count-1], denomination2: denomination2) + cc2Inside(amount2, denomination2: deno)
        }
        return table[amount2][denomination2.count]
    }
    return cc2Inside(amount, denomination2: denomination)
}

这个问题也可以迭代,但是我是没能想出来,搜到的一种做法是

func cc3(amount: Int, denomination: Array<Int>) -> Int {
    var table = Array(count: amount+1, repeatedValue: 0)
    table[0] = 1
    for(var i=0; i<denomination.count; i++) {
        for(var j=denomination[i]; j<=amount; j++) {
            table[j] += table[j-denomination[i]]
        }
    }
    return table[amount]
}

显然相比之下递归的代码更容易读懂