編程小結

scwang90 發布于2019-08-22 15:34 / 3233人閱讀

摘要：給定數組，取個數，和為，有哪些種取法遞歸解法遞歸優化，計算過程中去重思路一的做法，存在大量的重復，實際上對循環做一點修改，就可以在過程中避免重復迭代砝碼問題給一組砝碼，給一個重量，問用該組砝碼能否稱出該重量。

給定數組arr，取n個數，和為sum，有哪些種取法 遞歸解法

function main(arr, sum, n) {
    let result = []
    if (n === 1) {
        arr.filter(item => item === sum)
            .forEach(item2 => result.push([item2]))
        return result
    }
    for (let i = 0; i < arr.length; i++) {
        let el = arr[i]
        let subArr = arr.slice()
        subArr.splice(i, 1)
        let subResult = main(subArr, sum - el, n - 1)
        if (subResult.length > 0) {
            subResult.forEach(item3 => {
                item3.unshift(el)
                result.push(item3)
            })
        }
    }
    return result
}

let result = main([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 18, 3)
let result2 = result.map(item => item.sort().join(","))
console.log([...new Set(result2)])

遞歸優化，計算過程中去重

思路一的做法，存在大量的重復，實際上對 for 循環做一點修改，就可以在過程中避免重復

function main(arr, n, sum) {
    if (n === 1) {
        return arr.includes(sum) ? [
            [sum]
        ] : []
    }

    let result = []
    for (let i = 0; i < arr.length - n; i++) {
        let arr1 = arr.slice(i + 1)
        let addend = arr[i]
        let arr2 = main(arr1, n - 1, sum - addend)
        arr2.forEach(r => {
            r.unshift(addend)
            result.push(r)
        })
    }
    return result
}

let result = main([1, 2, 3, 4, 5, 6, 7, 8, 9], 3, 15)
debugger

迭代

function main(arr, n, sum) {
    let result = []
    let step = 1
    let stack = [{
        sum: [],
        arr
    }]
    while (step < n) {
        let newStack = []
        stack.forEach(s => {
            for (let i = 0; i < s.arr.length; i++) {
                let newSum = [...s.sum, s.arr[i]]
                if (newSum.reduce((a, b) => a + b, 0) < sum) {
                    newStack.push({
                        sum: newSum,
                        arr: s.arr.slice(i + 1)
                    })
                }
            }
        })
        stack = newStack
        step++
    }
    stack.forEach(s => {
        for (let i = 0; i < s.arr.length; i++) {
            let newSum = [...s.sum, s.arr[i]]
            if (newSum.reduce((a, b) => a + b, 0) === sum) {
                result.push([...s.sum, s.arr[i]])
            }
        }
    })
    return result
}

let result = main([1, 2, 3, 4, 5, 6, 7, 8, 9], 3, 15)
debugger

砝碼問題

給一組砝碼，給一個重量，問用該組砝碼能否稱出該重量。例如，一組砝碼 [1,3]，一個重量 2，返回 true

遞歸

function main(arr, weight) {
    // 終止條件
    if (arr.length === 0) {
        return false
    }
    if (arr.length === 1) {
        return arr[0] === weight ? true : false
    }

    if (arr.includes(weight)) {
        return true
    }

    let item = arr[0]
    if (main(arr.slice(1), weight)) {
        return true
    }

    if (main(arr.slice(1), weight + item)) {
        return true
    }

    if (main(arr.slice(1), weight - item)) {
        return true
    }

    return false
}

let result = main([1, 2, 10], 6)
debugger

迭代

function main(arr, weight) {
    let stack = [0]
    let i = 0
    while (i < arr.length) {
        let stackCopy = []
        for (let j = 0; j < stack.length; j++) {
            let s = stack[j]
            if (s === weight) {
                return true
            }
            if (s + arr[i] === weight) {
                return true
            }
            if (s - arr[i] === weight) {
                return true
            }
            stackCopy.push(s + arr[i])
            stackCopy.push(s - arr[i])
            stackCopy.push(s)
        }
        stack = stackCopy
        i++
    }
    return false
}

let result = main([1, 2, 10], 3)
debugger

+1,*2計算最少步數

給一個數，只能從1開始，+1或者*2，問最少多少步可以達到這個數

function main(x) {
    let result = []
    result.push(Math.ceil(x / 2))
    // 7 => (1+1+1)*2+1 共4步
    // 12 => (1+1+1+1+1+1)*2 共6步
    let i = 1
    let count = 0
    while (i * 2 <= x) {
        i = i * 2
        count++
    }
    count = count + x - i
    result.push(count)
    return result
    // 用 +1 的方法，步數始終是 Math.ceil(x/2)
    // 用 *2 后 +1 的方法，主要是考慮當 2^(n+1) > x > 2^n 時，從 2^n 到 x 需要進行多少次 +1
}

let result = main(15)
debugger

斐波那契數列 傳統遞歸方法

function fib1(n) {
    if (n < 2) {
        return n
    }
    return fib1(n - 1) + fib1(n - 2)
}

console.log(fib1(10))

迭代

function fib2(n) {
    if (n < 2) {
        return n
    }
    let arr = [0, 1]
    for (let i = 2; i < n + 1; i++) {
        arr.push(arr[i - 1] + arr[i - 2])
    }
    return arr[n]
}

console.log(fib2(10))

迭代優化

function fib3(n) {
    if (n < 2) {
        return n
    }
    let arr = [0, 1]
    for (let i = 2; i < n; i++) {
        let sum = arr[0] + arr[1]
        arr[0] = arr[1]
        arr[1] = sum
    }
    return arr[0] + arr[1]
}

console.log(fib3(10))

遞歸優化一

function fib4(n, p, k) {
    if (n === 1) {
        return k
    }
    if (n === 0) {
        return p
    }
    return fib4(n - 1, k, p + k)
}

console.log(fib4(10, 0, 1))

遞歸優化二

function fib5(n, p, k) {
    if (n === 1) {
        return k
    }
    if (n === 0) {
        return p
    }
    return fib5(n - 2, p + k, p + k + k)
}

console.log(fib5(10, 0, 1))

一點感悟

迭代是自下而上，遞歸是自上而下

求 0,1,1,2,3,5,8,13,21,34,55 的fib4(10)

等于求 1,1,2,3,5,8,13,21,34,55 的fib4(9)

等同于求 1,2,3,5,8,13,21,34,55 的fib4(8)

每遞歸調用一次，都自下而上計算一次

遞歸的關鍵還是在于如何劃分子問題，確定子問題與父問題之間的關系

云服務器 GPU云服務器設計小結對象小結個人小結小結

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/93561.html

編程模型（范式）小結

摘要：參考鏈接面向對象編程模型現在的很多編程語言基本都具有面向對象的思想，比如等等，而面向對象的主要思想對象，類，繼承，封裝，多態比較容易理解，這里就不多多描述了。前言在我們的日常日發和學習生活中會常常遇到一些名詞，比如命令式編程模型，聲明式編程模型，xxx語言是面向對象的等等，這個編程模型到處可見，但是始終搞不清是什么？什么語言又是什么編程模型，當你新接觸一門語言的時候，有些問題是需...

miya 2019-08-15 13:30 評論0 收藏0
javascript函數式編程入門小結

摘要：前言最近花了不少時間接觸學習的函數式的編程方式，而后為了加深理解，又去折騰。不過幸運的是，天生具備了函數式編程的基本元素，所以學習的起點不會太低。初接觸第一個實例，函數式編程是如何做一個番茄炒雞蛋的。前言最近花了不少時間接觸學習javascript的函數式的編程方式，而后為了加深理解，又去折騰haskell。不同于人們比較熟悉的命令式編程，如面向對象編程（oop），函數式編程（f...

includecmath 2019-08-21 10:40 評論0 收藏0
Javascript函數式編程小結

摘要：源起函數式編程近幾年非常流行經常可以在網上看到別人討論相關話題我機緣巧合之下在上看到有人提到一個講函數式編程的視頻看過之后突然茅塞頓開瞬間把之前零碎的關于函數式編程的知識一下子都聯系了起來于是自己希望趁有空把這些知識總結一下這樣既可以回顧下源起函數式編程近幾年非常流行,經常可以在網上看到別人討論相關話題. 我機緣巧合之下在github上看到有人提到一個講js函數式編程的視頻,看過之...

zengdongbao 2019-08-21 10:54 評論0 收藏0

發表評論

登陸后可評論

0條評論

scwang90

男|高級講師

我要關注我要私信

TA的文章

啟明云端分享|ESP32在開發環境時，常遇到的問題答疑（FAQ）

閱讀 3098·2021-10-11 10:58
如何讓用戶需求進化成產品功能

閱讀 2005·2021-09-24 09:47
CSS-水平居中、垂直居中、水平垂直居中

閱讀 510·2019-08-30 14:19
vue 使用Jade模板寫html，stylus寫css

閱讀 1708·2019-08-30 13:58
Muse UI遇到的坑

閱讀 1449·2019-08-29 15:26
ajax封裝

閱讀 648·2019-08-26 13:45
vue2.0-基于elementui換膚[自定義主題]

閱讀 2145·2019-08-26 11:53
深入了解 Number 類型

閱讀 1779·2019-08-26 11:30

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

編程小結

相關文章

編程模型（范式）小結

javascript函數式編程入門小結

Javascript函數式編程小結

發表評論

0條評論

scwang90

男|高級講師

TA的文章

啟明云端分享|ESP32在開發環境時，常遇到的問題答疑（FAQ）

如何讓用戶需求進化成產品功能

CSS-水平居中、垂直居中、水平垂直居中

vue 使用Jade模板寫html，stylus寫css

Muse UI遇到的坑

ajax封裝

vue2.0-基于elementui換膚[自定義主題]

深入了解 Number 類型

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

編程小結

相關文章

發表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！