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

資訊專欄INFORMATION COLUMN

編程小結(jié)

scwang90 / 3228人閱讀

摘要:給定數(shù)組,取個(gè)數(shù),和為,有哪些種取法遞歸解法遞歸優(yōu)化,計(jì)算過(guò)程中去重思路一的做法,存在大量的重復(fù),實(shí)際上對(duì)循環(huán)做一點(diǎn)修改,就可以在過(guò)程中避免重復(fù)迭代砝碼問(wèn)題給一組砝碼,給一個(gè)重量,問(wèn)用該組砝碼能否稱出該重量。

給定數(shù)組arr,取n個(gè)數(shù),和為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)])
遞歸優(yōu)化,計(jì)算過(guò)程中去重

思路一的做法,存在大量的重復(fù),實(shí)際上對(duì) for 循環(huán)做一點(diǎn)修改,就可以在過(guò)程中避免重復(fù)

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
砝碼問(wèn)題

給一組砝碼,給一個(gè)重量,問(wèn)用該組砝碼能否稱出該重量。例如,一組砝碼 [1,3],一個(gè)重量 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計(jì)算最少步數(shù)

給一個(gè)數(shù),只能從1開始,+1或者*2,問(wèn)最少多少步可以達(dá)到這個(gè)數(shù)

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 的方法,步數(shù)始終是 Math.ceil(x/2)
    // 用 *2 后 +1 的方法,主要是考慮當(dāng) 2^(n+1) > x > 2^n 時(shí),從 2^n 到 x 需要進(jìn)行多少次 +1
}

let result = main(15)
debugger
斐波那契數(shù)列 傳統(tǒng)遞歸方法
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))
迭代優(yōu)化
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))
遞歸優(yōu)化一
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))
遞歸優(yōu)化二
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))
一點(diǎn)感悟

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

求 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)

每遞歸調(diào)用一次,都自下而上計(jì)算一次

遞歸的關(guān)鍵還是在于如何劃分子問(wèn)題,確定子問(wèn)題與父問(wèn)題之間的關(guān)系

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/93561.html

相關(guān)文章

  • 編程模型(范式)小結(jié)

    摘要:參考鏈接面向?qū)ο缶幊棠P同F(xiàn)在的很多編程語(yǔ)言基本都具有面向?qū)ο蟮乃枷耄热绲鹊龋嫦驅(qū)ο蟮闹饕枷雽?duì)象,類,繼承,封裝,多態(tài)比較容易理解,這里就不多多描述了。 前言 在我們的日常日發(fā)和學(xué)習(xí)生活中會(huì)常常遇到一些名詞,比如 命令式編程模型,聲明式編程模型,xxx語(yǔ)言是面向?qū)ο蟮牡鹊龋@個(gè)編程模型到處可見,但是始終搞不清是什么?什么語(yǔ)言又是什么編程模型,當(dāng)你新接觸一門語(yǔ)言的時(shí)候,有些問(wèn)題是需...

    miya 評(píng)論0 收藏0
  • javascript函數(shù)式編程入門小結(jié)

    摘要:前言最近花了不少時(shí)間接觸學(xué)習(xí)的函數(shù)式的編程方式,而后為了加深理解,又去折騰。不過(guò)幸運(yùn)的是,天生具備了函數(shù)式編程的基本元素,所以學(xué)習(xí)的起點(diǎn)不會(huì)太低。初接觸第一個(gè)實(shí)例,函數(shù)式編程是如何做一個(gè)番茄炒雞蛋的。 前言 最近花了不少時(shí)間接觸學(xué)習(xí)javascript的函數(shù)式的編程方式,而后為了加深理解,又去折騰haskell。 不同于人們比較熟悉的命令式編程,如面向?qū)ο缶幊蹋╫op),函數(shù)式編程(f...

    includecmath 評(píng)論0 收藏0
  • Javascript函數(shù)式編程小結(jié)

    摘要:源起函數(shù)式編程近幾年非常流行經(jīng)常可以在網(wǎng)上看到別人討論相關(guān)話題我機(jī)緣巧合之下在上看到有人提到一個(gè)講函數(shù)式編程的視頻看過(guò)之后突然茅塞頓開瞬間把之前零碎的關(guān)于函數(shù)式編程的知識(shí)一下子都聯(lián)系了起來(lái)于是自己希望趁有空把這些知識(shí)總結(jié)一下這樣既可以回顧下 源起 函數(shù)式編程近幾年非常流行,經(jīng)常可以在網(wǎng)上看到別人討論相關(guān)話題. 我機(jī)緣巧合之下在github上看到有人提到一個(gè)講js函數(shù)式編程的視頻,看過(guò)之...

    zengdongbao 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

scwang90

|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<