長沙前端培訓班分享：不重復的組成4位數求平均值。解決方案應用了動態規劃的算法思想，下面我們一起來看看什么是動態規劃吧。

       一、動態規劃動態規劃的定義 動態規劃(dynamic programming)是運籌學的一個分支，20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decisions)的優化問題時，提出了著名的最優化原理，把多階段過程轉化為-系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法-動態規劃。 動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法。

       動態規劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。

       這種做法在重復子問題的數目關于輸入的規模呈指數增長時特別有用動態規劃的步驟尋找最優子結構(狀態表示)歸納狀態轉移方程邊界初始化二、解決方案思考過程 求所有四位數的平均值，我可以把問題縮小，先把四位數的所有組合找出來 想一想，求四位數的所有組合，如果我已知三位數的所有組合，能不能幫助我更快求出四位數的所有組合。 如果這里問題不是所有四位數，是六數位或者更多，我能用同樣的函數得到答案嗎 狀態轉移方程當我們知道三位數的所有組合，就能利用規律求出四位數的所有組合，那么現在只需要求出三位數的所有組合了；求出兩位數的所有組合，就可以利用規律求出三位數的所有組合；求出一位數的所有組合，再利用規律求出兩位數的所有組合。那這里問題就被分解成了兩個 1. 一位數的所有組合是什么 2. 這個規律是什么第一個問題，相信所有人很快就能得到答案，“3”的所有組合就是[3]，“1”的所有組合就是[1]。

       第二個問題，我們來想一下思路 當問題是求出“1”所有組合，剛剛求出了答案是[1] 當問題是求出“1,3“所有組合時： 我們可以在[1]的左邊插入3，可以在[1]的右邊插入3，結果是[13,31]當問題是求出“1，3，5”的所有組合我們可以在“1，3”所有組合的基礎上來求，“13”的左邊、中間、右邊插入5，那么結果有[513,153,135]，“31”的左邊、中間、右邊插入5，所有結果是[531,351,315]，那么“1，3，5”這三個數的所有組合是[513,153,135,531,351,315]。到這里，我已經發現了規律，我要求“1350”這四位數的所有組合，我只需要求出”135“這三個數的所有組合，然后再對其每個數的每個位置插入新的數(0)即可找打所有的四位數組合了寫代碼let arr = [1, 3, 5,0]

console.log(main(arr))

// 主方法入口
function main(arr) {

let allValue = [];
for (let r of arr) {
allValue = insert(allValue, r)
// 輸出一下 每一次都會輸出當前結果
console.log(allValue)
}

// 最后計算平均數
// 加起來的數
let sum = 0
for (let num of allValue) {
sum += parseInt(num)
}
return sum / allValue.length;
}

/**
* allArr 表示插入的集合 是一個數組 表示之前已經計算出的數組合計
* insertValue表示當前插入的值
* insert([],1) // ['1']
* insert(['1'], 3) // ['31','13']
* insert(['13','31'], 5) // ['531', '351', '315', '513', '153', '135']
*/
function insert(allArr, insertValue) {
// 特殊處理為空情況
if (allArr.length == 0) return [insertValue + '']
let result = []

for (let nowValue of allArr) {
// 進行插入操作 重點 i<=nowValue.length 是可以在末尾也插入值 實際循環比nowValue的長度多一次
for (let i = 0; i <= nowValue.length; i++) {
result.push(insertStr(nowValue, i, insertValue))
}
}
return result
}
/**
* 字符串插入
* source 原字符串
* start表示插入位置
* newStr 表示插入新的字符串
* insertStr('1234',0,'5') // 51234
* insertStr('1234',3,'5') // 12354
* insertStr('1234',4,'5') // 12345
*/
function insertStr(source, start, newStr) {
return source.slice(0, start) + newStr + source.slice(start);
}

上一篇

長沙前端培訓班分享：JavaScript正則全面解析

下一篇

長沙Web前端培訓班分享：瀏覽器訪問網頁過程原理解析