11.Javascript高级算法

Javascript数据结构与算法 评论

11 高级算法

本章将探讨两个高级主题：动态规划和贪心算法 。

11.1 动态规划

使用递归去解决问题虽然简洁，但效率不高 。包括 JavaScript 在内的众多语言，不能高效地将递归代码解释为机器代码，尽管写出来的程序简洁，但是执行效率低下 。

以下以计算斐波那契数列为例进行说明。

斐波那契数列定义如下：

1
0 1 1 2 3 5 8 13 21 34 ……

斐波那契数列除了前两项外，其他值都是前两项的和。使用递归计算斐波那契数列程序如下：

1
2
3
4
5
6
7
8
function recurFib(n) {
  if (n < 2) {
    return n
  } else {
    return recurFib(n - 1) + recurFib(n - 2)
  }
}
console.log('recurFib(30):', recurFib(30)) // 832040

这里我们请求的是第30位的斐波那契数是什么，这个还能计算出来，我们如果改成50的话，我的浏览器直接就崩溃了。

为什么会这样子？ 这是因为我们使用了递归，而递归的效率是很低了，存在了大量的重复运算，我们以获取第5位的斐波那契数列为例。

递归程序样式

从这个图中我们可以看到，我们要计算斐波那契数列第5位是啥，我们计算了2次第3位是啥，计算了3次第2位是啥……，我们的程序中存在了大量重复运算。这就是递归效率低的原因。

如果编译器可以将已经计算的值记录下来，函数的执行效率就不会如此差。我们可以使用动态规划的技巧来设计一个效率更高的算法 。

程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function dynFib(n) {
  let valArr = new Array(n)
  for (let i = 0; i <= n; i++) {
    valArr[i] = 0
  }
  if (n === 0) {
    return 0
  }
  if (n === 1 || n === 2) {
    return 1
  } else {
    valArr[1] = 1
    valArr[2] = 1
    for (let i = 3; i <= n; i++) {
      valArr[i] = valArr[i - 1] + valArr[i - 2]
    }
    return valArr[n - 1]
  }
}
console.log('dynFib(50):', dynFib(50));

这时候我们再计算斐波那契数列第50位是啥的时候，浏览器就不会卡死了。

使用for循环计算斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
function iterFib(n) {
  let last = 1
  let nextLast = 1
  let result = 1
  for (let i = 2; i < n; i++) {
    result = last + nextLast
    nextLast = last
    last = result
  }
  return result
}
console.log('iterFib(50):', iterFib(50))

11.2 寻找最长公共子串

另一个适合使用动态规划去解决的问题是寻找两个字符串的最长公共子串。例如，在单词“raven”和“havoc”中，最长的公共子串是“av”。寻找最长公共子串常用于遗传学中，用于使用核苷酸中碱基的首字母对 DNA 分子进行描述

动态规划是更适合解决这个问题的方案。这个算法使用一个二维数组存储两个字符串相同位置的字符比较结果。初始化时，该数组的每一个元素被设置为 0。每次在这两个数组的相同位置发现了匹配，就将数组对应行和列的元素加 1，否则保持为 0 。

程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 寻找最长公共子串
function lcs(word1, word2) {
  // 公共子串的长途
  let max = 0;
  // 公共子串结束的索引
  let index = 0
  let lcsArr = new Array(word1.length + 1)
  for (let i = 0; i <= word1.length; i++) {
    lcsArr[i] = new Array(word2.length + 1)
    for (j = 0; j <= word2.length; j++) {
      lcsArr[i][j] = 0
    }
  }

  for (let i = 0; i <= word1.length; i++) {
    for (let j = 0; j <= word2.length; j++) {
      if (i === 0 || j === 0) {
        lcsArr[i][j] = 0
      } else {
        if (word1[i - 1] === word2[j - 1]) {
          lcsArr[i][j] = lcsArr[i - 1][j - 1] + 1
        } else {
          lcsArr[i][j] = 0
        }
      }
      if (max < lcsArr[i][j]) {
        max = lcsArr[i][j]
        index = i
      }

    }
  }
  let str = ''
  if (max === 0) {
    return str
  } else {
    for (let i = index - max; i <= max; i++) {
      str += word2[i]
    }
    return str
  }
}

看到这个程序，不得不感叹，有些人真是太聪明了，竟然能写出这么巧的程序。

测试：

1
2
console.log('lcs("abbcc","dbbcc"):', lcs("abbcc", "dbbcc"))
// lcs("abbcc","dbbcc"): bbcc

测试正常，说明我们的程序没有问题。

11.3 背包问题

假设有个保险箱里面有 5 件物品，它们的尺寸分别是 3、 4、 7、 8、 9，而它们的价值分别是 4、 5、 10、 11、 13。我们有个背包，容积是16，我们要从保险箱挑选一些东西放进背包，我们该怎样装才能使背包的价值最大呢？

使用递归程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 各个物品的价值
var value = [4, 5, 10, 11, 13]
// 各个物品的体积
var size = [3, 4, 7, 8, 9]
// 背包容积
var capacity = 16
// 数组大小
var n = 5

function bag(capacity, size, value, n) {
  if (n === 0 || capacity === 0) {
    return 0
  }
  // 如果某一个物品的体积已经大于容积了，那这个物品肯定就不行，则从下一个物品开始判断
  if (size[n - 1] > capacity) {
    return bag(capacity, size, value, n - 1)
  } else {
    // 比较放入这个物品跟不放入这个物品，哪一种情况下背包的价值最大
    let add = value[n - 1] + bag(capacity - size[n - 1], size, value, n - 1);
    let unAdd = bag(capacity, size, value, n - 1);
    return Math.max(add, unAdd)
  }
}

测试：

1
2
console.log(bag(capacity, size, value, n))
// 23

// 使用动态规划方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function dBag(capacity, size, value, n) {
  let k = []
  for (let i = 0; i <= capacity + 1; i++) {
    k[i] = []
  }
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= capacity; j++) {
      if (i === 0 || j === 0) {
        k[i][j] = 0
      } else if (size[i - 1] <= j) {
        k[i][j] = Math.max(value[i - 1] + k[i - 1][j - size[i - 1]], k[i - 1][j])
      } else {
        k[i][j] = k[i - 1][j]
      }
    }
  }
  return k[n][capacity]
}
let result = dBag(capacity, size, value, n)
console.log('result:', result); 
// 23

这程序实在是太高深了，这是怎么想的呢？黑人问号脸.jpg。反正莫名其妙问题就解决了，为啥要这样子，我想了很久都没明白，有明天的人请指教下。

11.4 贪心算法

贪心算法的一个经典案例是找零问题。你从商店购买了一些商品，找零 63 美分，店员要怎样给你这些零钱呢？如果店员根据贪心算法来找零的话，他会给你两个 25 美分、一个10 美分和三个 1 美分。在没有使用 50 美分的情况下这是最少的硬币数量。

程序实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function makeChange(origAmt) {
  let result = []
  if (origAmt % 25 < origAmt) {
    result[0] = parseInt(origAmt / 25)
    origAmt = origAmt % 25
  }
  if (origAmt % 10 < origAmt) {
    result[1] = parseInt(origAmt / 10)
    origAmt = origAmt % 10
  }
  if (origAmt % 5 < origAmt) {
    result[2] = parseInt(origAmt / 5)
    origAmt = origAmt % 5
  }
  result[3] = origAmt
  return result
}

function showChange(coins) {
  if (coins[0] > 0) {
    console.log("25 美分的数量 - " + coins[0] + " - " + coins[0] * 25);
  }
  if (coins[1] > 0) {
    console.log("10 美分的数量 - " + coins[1] + " - " + coins[1] * 10);
  }
  if (coins[2] > 0) {
    console.log("5 美分的数量 - " + coins[2] + " - " + coins[2] * 5);
  }
  if (coins[3] > 0) {
    console.log("1 美分的数量 - " + coins[3] + " - " + coins[3] * 1);
  }
}
let origAmt = 63;
showChange(makeChange(origAmt));
// 打印结果
25 美分的数量 - 2 - 50
10 美分的数量 - 1 - 10
1 美分的数量 - 3 - 3

自此本章就完了，数据结构与算法的javascript的部分也讲解完了。读这本书用了好几个月，大概98%的都能看懂，目前就一个归并排序和一个背包问题，看不懂。留着以后慢慢想吧。

再次长出一口气，终于完了，虽然我只是做笔记，敲敲别人的代码，但是还是深深的体会到了看完一本书是多么不容易的一件事。学习之路真是艰难且长远。加油，向大神进军。

锅锅复锅锅

中国贫困人口，特别需要关爱人群，微信guo330504。