為什麼我要放棄javaScript資料結構與演算法（第十一章）—— 演算法模式

摘要： 本章將會學習遞迴、動態規劃和貪心演算法。 第十一章 演算法模式 遞迴 遞迴是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞迴通常涉及函式呼叫自身。 遞迴函式是像下面能夠直接呼叫自身的方式或函式 function recursiveFunction(so...

本章將會學習遞迴、動態規劃和貪心演算法。

第十一章 演算法模式

遞迴

遞迴是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞迴通常涉及函式呼叫自身。

遞迴函式是像下面能夠直接呼叫自身的方式或函式

function recursiveFunction(someParam){
recursiveFunction(someParam);
}

能夠像下面這樣間接呼叫自身的函式，也是遞迴函式

function recursiveFunction1(someParam){
recursiveFunction2(someParam);
}
function recursiveFunction2(someParam){
recursiveFunction1(someParam);
}

假設現在必須要執行 recursiveFunction ,結果是什麼?單單上述情況而言，它會一直執行下去。因此，每個遞迴函式都必須有邊界條件，即一個不再遞迴呼叫的條件（停止點），以防無限遞迴。

JavaScript 呼叫棧大小的限制

如果忘記加上用以停止函式遞迴呼叫的邊界條件，會發生什麼呢？遞歸併不會無限執行下去，瀏覽器會丟擲錯誤，也就是所謂的棧溢位錯誤（stack Overflow error）

每個瀏覽器都有自己的上限，可以用一下程式碼測試。

var i = 0;
function recursiveFn(){
i++;
recursiveFn();
}
try{
recursiveFn(); 
}catch(e){
console.log('i='+i+' error:'+e);
}
// 谷歌：i=15706 error:RangeError: Maximum call stack size exceeded
// 360：i=31470 error:RangeError: Maximum call stack size exceeded
// 火狐：i=40687 error:InternalError: too much recursion

根據作業系統和瀏覽器的不同，具體的數值也會有所不同，但區別不大。

ES6 有尾呼叫優化（tail call optimazation）。如果函式內最後一個操作是呼叫函式，會通過“跳轉指令（jump）”而不是“子程式呼叫（subroutine call ）”來控制。也就是說，ES6中，這裡的程式碼會一直執行下去。所以，具有停止遞迴的邊界條件很重要。

ofollow,noindex" target="_blank">尾呼叫 點選看看，阮一峰老師的。

斐波那契數列

斐波那契數列的定義如下：

• 1 和 2 的斐波那契數是1
• n（n>2）的斐波那契數是（n-1）加上（n-2）的斐波那契數。

實現

function fibonacci(num){
if(num === 1 || num ===2){
return 1;
}
return arguments.callee(num - 1) + arguments.callee(num - 2);
}

讓我們試著找出6的斐波那契數，其會產生如下函式呼叫

我們也可以用非遞迴的方法實現

function fib(num){
var n1 = 1,
n2 = 1,
n = 1;
for(var i = 3; i <= num; i++){
n = n1 + n2;
n1 = n2;
n2 = n;
}
return n;
}

為什麼要用遞迴？是因為更快嗎？其實並不，反而更慢。遞迴的好處在於更容易理解，並且它所需的程式碼量更少。然後在ES6中，因為有尾呼叫，可以加快遞迴的速度。總而言之，我們用遞迴，通常是因為它更容易解決問題。

動態規劃

動態規劃（Dynamic Programming,DP）是一種將複雜問題分解成更小的子問題來解決的優化技術。與分而治之不同的是，動態規劃是將問題分解成相互依賴的子問題。

用動態規劃解決問題，要遵循三個步驟：

1. 實現子問題。
2. 實現要反覆執行來解決子問題的部分
3. 識別並求解出邊界條件

可以用動態規劃解決一些著名的問題如下：

• 揹包問題 ：給出一組專案，各自有值和容量，目標是要找出總值最大的專案的集合。這個問題的限制是，總容量必須小於等於“揹包”的容量。
• 最長公共子序列 ：找出一組序列的最長公共子序列（可由另一序列刪除元素但不改變）
• 矩陣鏈相乘 ：給出一系列矩陣，目標是找到這些矩陣相乘的最高效辦法（計算次數儘可能少）。相乘操作不會進行，解決方案是找到這些矩陣各自相乘的順序。
• 硬幣找零 ：給出面額為d1...dn的一定數量的硬幣和要找零的錢數，找出有多少種找零的方法。
• 圖的全源最短路徑 ：對所有頂點對（u,v），找出頂點u到頂點v的最短路徑。

最少硬幣找零問題

最少硬幣找零問題是硬幣問題的一個變種。硬幣找零問題是給出要找零的錢數，以及可以用的硬幣面額d1...dn 及其數量，找出有多少種找零方法。最少硬幣找零問題是要給出要找零的錢數以及可用的硬幣面額d1...dn及其數量，找出所需的最少硬幣個數。

例如，美國有一下面額（硬幣）：d ₁ =1,d ₂ =5,d ₃ =10,d ₄ =25

如果要找36美分的零錢，我麼可以用1個25美分，1個10美分和一個便士（1美分）

如何將這個解答轉化成演算法？

最少硬幣找零的解決方案是找到n所需的最小硬幣數。但要做到這一點，首先得找到對每個x<n的解。然後，我們將解建立在更小的值的基礎上。

function MinCoinChange(coins){
var coins = coins; // 零錢的面額
var cache = {}; // 快取
this.makeChange = function(amount){ // 遞迴函式
var me = this;
if(!amount){ // 若金額總額小於0則返回空陣列
return [];
}
if(cache[amount]){ // 若快取中已有該計算結果，則直接返回 
return cache[amount];
}
var min = [],newMin,newAmount; 
for(var i = 0; i < coins.length; i++){
var coin = coins[i];
newAmount = amount - coin;
if(newAmount >= 0){
newMin = me.makeChange(newAmount);
}
if(newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)){
min = [coin].concat(newMin);
console.log('new Min '+ min + 'for '+ amount);
}
}
return (cache[amount] = min);
}
this.getCache = function(){
console.log(cache);
}
}

測試

const minCoinChange = new MinCoinChange([1,5,10,25]);
console.log(minCoinChange.makeChange(36));
/*
new Min 1,1,1,1,1for 5
new Min 5for 5
new Min 1,5for 6
new Min 1,1,5for 7
new Min 1,1,1,5for 8
new Min 1,1,1,1,5for 9
new Min 1,1,1,1,1,5for 10
new Min 5,5for 10
new Min 10for 10
new Min 1,10for 11
new Min 1,1,10for 12
new Min 1,1,1,10for 13
new Min 1,1,1,1,10for 14
new Min 1,1,1,1,1,10for 15
new Min 5,10for 15
new Min 1,5,10for 16
new Min 1,1,5,10for 17
new Min 1,1,1,5,10for 18
new Min 1,1,1,1,5,10for 19
new Min 1,1,1,1,1,5,10for 20
new Min 5,5,10for 20
new Min 10,10for 20
new Min 1,10,10for 21
new Min 1,1,10,10for 22
new Min 1,1,1,10,10for 23
new Min 1,1,1,1,10,10for 24
new Min 1,1,1,1,1,10,10for 25
new Min 5,10,10for 25
new Min 25for 25
new Min 1,25for 26
new Min 1,1,25for 27
new Min 1,1,1,25for 28
new Min 1,1,1,1,25for 29
new Min 1,1,1,1,1,25for 30
new Min 5,25for 30
new Min 1,5,25for 31
new Min 1,1,5,25for 32
new Min 1,1,1,5,25for 33
new Min 1,1,1,1,5,25for 34
new Min 1,1,1,1,1,5,25for 35
new Min 5,5,25for 35
new Min 10,25for 35
new Min 1,10,25for 36 
(3) [1, 10, 25]
*/
minCoinChange.getCache();
// {1: Array(1), 2: Array(2), 3: Array(3), 4: Array(4), 5: Array(1), 6: Array(2), 7: Array(3), 8: Array(4), 9: Array(5), 10: Array(1), 11: Array(2), 12: Array(3), 13: Array(4), 14: Array(5), 15: Array(2), 16: Array(3), 17: Array(4), 18: Array(5), 19: Array(6), 20: Array(2), 21: Array(3), 22: Array(4), 23: Array(5), 24: Array(6), 25: Array(1), 26: Array(2), 27: Array(3), 28: Array(4), 29: Array(5), 30: Array(2), 31: Array(3), 32: Array(4), 33: Array(5), 34: Array(6), 35: Array(2), 36: Array(3)}

const minCoinChange1 = new MinCoinChange([1,3,4]);
console.log(minCoinChange1.makeChange(6));
/*
 new Min 1for 1
 new Min 1,1for 2
 new Min 1,1,1for 3
 new Min 3for 3
 new Min 1,3for 4
 new Min 4for 4
 new Min 1,4for 5
 new Min 1,1,4for 6
 new Min 3,3for 6
 (2) [3, 3]
*/
minCoinChange1.getCache();// {1: Array(1), 2: Array(2), 3: Array(1), 4: Array(1), 5: Array(2), 6: Array(2)}

揹包問題

揹包問題是一個組合優化問題。它可以描述如下：給定一個固定大小、能夠攜帶W的揹包，以及一組有價值和重量的物品，找出一個最佳解決方案，使得裝入揹包的物品總重量不超過W，且總價值最大。

下面是一個例子：

物品	重量	價值
1	2	3
2	3	4
3	4	5

考慮揹包能夠攜帶的重量只有5。對於這個例子，我們可以說最佳解決方案就是往揹包裡裝入物品1和物品2，這樣，總重量為5，總價值為7。

揹包演算法：

function knapSack(capacity,weights,values,n){
var i,w,a,b,kS = [];
for(i = 0; i <= n; i++){
kS[i] = [];
}
for(i = 0; i <= n; i++){
for(w = 0; w <= capacity; w++){
if(i == 0 || w == 0){
kS[i][w] = 0;
}else if(weights[i-1] <= w){
a = values[i - 1] + kS[i - 1][w - weights[i-1]];
b = kS[i-1][w];
kS[i][w] = (a > b) ? a : b;
}else{
kS[i][w] = kS[i-1][w];
}
}
}
return kS[n][capacity];
}

工作原理

ks[n+1][capacity+1]

測試

var values = [3,4,5],
weights = [2,3,4],
capacity = 5,
n = values.length;
console.log(knapSack(capacity,weights,values,n)); // 7

上面的演算法只輸出揹包攜帶物品價值的最大值，而不列出實際的物品。我們可以增加下面的附加函式來找出構成解決方案的物品：

function findValues(n,capacity,kS,weights,values){
var i = n, k = capacity;
console.log('解決方案包含以下物品： ');
while( i > 0 && k > 0 ){
if(kS[i][k] !== kS[i-1][k]){
console.log('物品' + i + '，重量：' + weights[i-1] + '，價值：'+values[i - 1] );
i--;
k = k - kS[i][k];
}else{
i--;
}
}
}

輸出結果：

解決方案包含以下物品： 
物品2，重量：3，價值：4
物品1，重量：2，價值：3

最長公共子序列

另一個經常被當做程式設計挑戰問題的動態最長公共子序列（LCS）:找出兩個字串序列的最長子序列的長度。最長子序列是指，在兩個字串序列中以相同順序出現，但不要求連續（非字串子串）的字串序列。

考慮如下的例子：

字串	元素
字串1	a	c	b	a	e	d
字串2	a	b	c	a	d	f

LCS:長度為4的‘’acad“

下面的演算法

function lcs(wordX,wordY){
var m = wordX.length,
n = wordY.length,
l = [],
solution = [],
i, j, a, b;
for(i = 0; i <= m; ++i){
l[i] = [];
solution[i] = [];
for(j = 0; j <= n; ++j){
l[i][j] = 0;
solution[i][j] = '0';
}
}
for(i = 0; i <= m; i++){
for(j = 0; j <= n; j++){
if(i == 0 || j == 0){
l[i][j] = 0;
}else if(wordX[i-1] == wordY[j-1]){
l[i][j] = l[i-1][j-1] + 1;
solution[i][j] = 'diagonal';

}else{
a = l[i-1][i];
b = l[i][j-1];
l[i][j] = a > b ? a : b;
solution[i][j] = l[i][j] == l[i-1][j] ? 'top' : 'left';
}
}
}
printSolution(solution,l,wordX,wordY,m,n);
return l[m][n];
}

function printSolution(solution,l,wordX,wordY,m,n){
var a = m,
b = n,
i,
j,
x = solution[a][b],
answer = '';
while(x !== '0'){
if(solution[a][b] === 'diagonal'){
answer = wordX[a-1] + answer;
a--;
b--;
}else if(solution[a][b] === 'left'){
b--;
}else if(solution[a][b] === 'top'){
a--;
}
x = solution[a][b];
}
console.log('lcs:' + answer);
}

矩陣鏈相乘（未完成）

貪心演算法（未完成）

最少硬幣找零問題

揹包問題

函數語言程式設計簡介

藉助ES6的能力，JavaScript 也能夠進行函數語言程式設計

函數語言程式設計和指令式程式設計

以函式式方式進行開發並不簡單。

假如我們想列印一個數組中所有的元素。我們可以用指令式程式設計，宣告的函式如下:

var printArray = function(array){
for(var i = 0; i < array.length; i++){
console.log(array[i]);
}
}
printArray([1,2,3,4,5]);

在上面的程式碼中，我們迭代陣列，列印每一項。

現在，我們試著將這個例子轉換成函數語言程式設計。在函數語言程式設計中，我們關注的重點是需要描述什麼，而不是如何描述

var forEach = function(array,action){
for(var i = 0; i < array.length; i++){
action(array[i]);
}
}

接著我們需要建立另一個元素負責把陣列元素列印到控制檯的函式（考慮為回撥函式），如下

var logItem = function(item){
console.log(item);
}

最後，像下面這樣使用函式

forEach([1,2,3,4,5],logItem);

幾點需要注意：

• 主要目標是描述資料，已經要對資料應用的轉換
• 程式執行順序的重要性很低，而在指令式程式設計中，步驟和順序是非常重要的
• 函式和資料結合是函數語言程式設計的核心
• 在函數語言程式設計中，我們可以使用和濫用函式和遞迴，而在指令式程式設計中，則使用迴圈、賦值、條件和函式。

另外一個例子，考慮我們要找陣列中最小的值。用指令式程式設計完成這個任務，只要迭代陣列，檢查當前的最小值是否大於陣列元素，如果是，就更行最小值。

var findMinArray = function(array){
var minValue = array[0];
for(var i = 1; i < array.length; i++){
if(minValue > array[i]){
minValue = array[i];
}
}
return minValue;
}
console.log(findMinArray([8,6,4,5,9])); // 4

用函數語言程式設計完成相同的任務，可以使用Math.in 函式，傳入所有要比較的陣列元素。我們可以像下面的例子裡這樣，使用ES2015 的解構操作符（...）,把陣列轉換成單個元素：

const min_ = function(array){
return Math.min(...array);
}
console.log(min_([8,6,4,5,9])); // 4

使用箭頭函式，簡化程式碼

const min_ = arr => Math.min(...arr);

JavaScript函式式工具箱——map、filter 和 reduce

map、filter和reduce函式是函數語言程式設計的基礎

我們可以使用map函式 ，把一個數據集合轉換成對映成另一個數據集合。先看一個指令式程式設計的例子：

var daysOfWeek = [
{ name: 'Monday', value: 1 },
{ name: 'Tuseday', value: 2 },
{ name: 'Webnesday', value: 7 },
]
var daysOfWeekValues_ = [];
for(var i = 0; i < daysOfWeek.length; i++ ){
daysOfWeekValues_.push(daysOfWeek[i].value);
}

再以函數語言程式設計來考慮同樣的例子，程式碼如下：

var daysOfWeekValues = daysOfWeek.map(function(day){
return day.value;
})
console.log(daysOfWeekValues);

我們可以使用 filter 函式過濾一個集合的值。來看一個例子

var positiveNumbers_ = function(array){
var positive = [];
for(var i = 0; i < array.length; i++){
if(array[i] >= 0){
positive.push(array[i]);
}
}
return positive;
}
console.log(positiveNumbers_([-1,1,2,-2])); // (2) [1, 2]

改成函式式

var positiveNumbers = function(array){
return array.filter(function(num){
return num >= 0;
});
}
console.log(positiveNumbers([-1,1,2,-2])); // (2) [1, 2]

也可以使用reduce函式，把一個集合歸納成一個約定的值。比如，對一個數組中的值求和：

var sumValues = function(array){
var total = array[0];
for(var i = 1; i < array.length; i++){
total += array[i];
}
return total;
}
console.log(sumValues([1,2,3,4,5])); // 15

上面的程式碼也可以寫成這樣的：

var sum_ = function(array){
return array.reduce(function(a,b){
return a + b;
});
}
console.log(sum_([1,2,3,4,5])); // 15

再看另外一個例子，考慮我們需要寫一個函式，把幾個陣列連線起來。為此，可以建立另外一個數組，用於存放其他陣列的元素。我們可以執行以下命令式的程式碼

var mergeArrays = function(arrays){
var count = arrays.length,
newArray = [],
k = 0;
for(var i = 0; i < count; i++){
for(var j = 0; j < arrays[i].length; j++){
newArray[k++] = arrays[i][j];
}
}
return newArray;
}
console.log(mergeArrays([[1,2,3],[4,5],[6]])); // (6) [1, 2, 3, 4, 5, 6]

在這個例子，我們聲明瞭變數，還使用了迴圈。現在，我們用JavaScript 函數語言程式設計把上面的程式碼重寫如下：

var mergeArraysConcat = function(arrays){
return arrays.reduce(function(p,n){
return p.concat(n);
});
}
console.log(mergeArraysConcat([[1,2,3],[4,5],[6]])); // (6) [1, 2, 3, 4, 5, 6]

箭頭函式簡寫

const mergeArrays = (...arrays) => [].concat(...arrays);
console.log(mergeArrays([1,2,3],[4,5],[6])); // (6) [1, 2, 3, 4, 5, 6]

小結

在本章中，你瞭解了更多的遞迴的知識，已經它幫助我們解決一些動態規劃問題。我們介紹了最著名的動態規劃問題，如最少硬幣找零、揹包問題、最長公共子序列和矩陣鏈相乘(後面補)。

還學習了貪心演算法，已經如何用貪心演算法解決最少硬幣找零和揹包問題。

還學習了函數語言程式設計，並通過一些例子瞭解瞭如何以這種正規化使用JavaScript 的功能。

書籍連結： 學習JavaScript資料結構與演算法