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

資訊專欄INFORMATION COLUMN

python-動態(tài)規(guī)劃的遞歸、非遞歸實(shí)現(xiàn)

xialong / 3355人閱讀

摘要:概要本文只是簡單的介紹動態(tài)規(guī)劃遞歸非遞歸算法實(shí)現(xiàn)案例一題目一求數(shù)組非相鄰最大和題目描述在一個數(shù)組中,找出一組不相鄰的數(shù)字,使得最后的和最大。

概要

本文只是簡單的介紹動態(tài)規(guī)劃遞歸、非遞歸算法實(shí)現(xiàn)

案例一 題目一:求數(shù)組非相鄰最大和

[題目描述]
在一個數(shù)組arr中,找出一組不相鄰的數(shù)字,使得最后的和最大。
[示例輸入]
arr=1 2 4 1 7 8 3
[示例輸出]
15

from functools import wraps
def memoDeco(func):
    """
    memoDeco主要是緩存已遍歷的節(jié)點(diǎn),減少遞歸內(nèi)存開銷
    """
    cashe={}
    @wraps(func)
    def wrapper(*args):
        if args not in cashe:
            cashe[args]=func(*args)
        return cashe[args]
    
    return wrapper

@memoDeco
def recMaxArray(array,index):
    if index==0:
        return array[0]
    elif index==1:
        return max(array[0],array[1])
    else:
        return max(recMaxArray(array,index-2)+array[index],recMaxArray(array,index-1))
    
if __name__=="__main__":
    array=(1,2,4,1,7,8,3)
    print(recMaxArray(array,len(array)-1))
非遞歸實(shí)現(xiàn)
def dpMaxArray(array):
    """
    代碼講解詳見引用一:正月點(diǎn)燈籠講解
    """
    lens=len(array)
    maxArray=[0]*(lens)
    maxArray[0]=array[0]
    maxArray[1]=max(array[0],array[1])
    for i in range(2,lens):
        maxArray[i]=max(maxArray[i-2]+array[i],maxArray[i-1])
    return maxArray[-1]

    
if __name__=="__main__":
    array=(1,2,4,1,7,8,3)
    print(dpMaxArray(array))
案例二

[題目描述]
給定一個正整數(shù)s, 判斷一個數(shù)組arr中,是否有一組數(shù)字加起來等于s。
[示例輸入]
arr=3 34 4 12 5 3
s=9
[實(shí)例輸出]
true

遞歸實(shí)現(xiàn)
from functools import wraps

#和第一題一樣,套用裝飾器可以做一個緩存節(jié)點(diǎn)作用
def memoDeco(func):
    """
    memoDeco主要是緩存已遍歷的節(jié)點(diǎn),減少遞歸內(nèi)存開銷
    """
    cashe = {}
    
    @wraps(func)
    def wrapper(*args):
        if args not in cashe:
            cashe[args] = func(*args)
        return cashe[args]
    
    return wrapper


@memoDeco
def recSubSet(arr, index, tar_num):
    if index == 0:
        return arr[0] == tar_num
    elif tar_num == 0:
        return True
    elif arr[index] > tar_num:
        return recSubSet(arr, index - 1, tar_num)
    else:
        return recSubSet(arr, index - 1, tar_num) or recSubSet(arr, index - 1, tar_num - index)


if __name__ == "__main__":
    arr = (3, 34, 4, 12, 5, 3)
    tar_num = 13
    index = len(arr) - 1
    print(recSubSet(arr, index, tar_num))
非遞歸實(shí)現(xiàn)
"""
多維數(shù)組構(gòu)建用python第三方庫numpy比較方便
代碼講解詳見引用一:正月點(diǎn)燈籠講解
"""
import numpy as np


def dpSubSet(arr, tar_num):
    subSet = np.zeros((len(arr), tar_num + 1), dtype=bool)
    subSet[:, 0] = True
    subSet[0, :] = False
    subSet[0, arr[0]] = True
    for i in range(1, len(arr)):
        for j in range(1, tar_num + 1):
            if arr[i] > j:
                subSet[i, j] = subSet[i - 1, j]
            else:
                subSet[i, j] = subSet[i - 1, j] or subSet[i - 1, j - arr[i]]
    return subSet[-1, -1]


if __name__ == "__main__":
    arr = (3, 34, 4, 12, 5, 3)
    tar_num = 13
    print(dpSubSet(arr, tar_num))
引用

1,正月點(diǎn)燈籠-動態(tài)規(guī)劃

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

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

相關(guān)文章

  • 基本算法思想:遞歸+分治+動態(tài)規(guī)劃+貪心+回溯+分支限界

    摘要:代碼實(shí)現(xiàn)見下面評論對應(yīng)代碼動態(tài)規(guī)劃基本思想和分治法基本思想有共同的地方,不同的是子問題往往不是獨(dú)立的,有事母問題要借助子問題的解來判斷,因此把已經(jīng)計(jì)算好的問題記錄在表格中,后續(xù)如果需要查詢一下,可以避免重復(fù)計(jì)算,這是動態(tài)規(guī)劃的基本思想。 作者:心葉時間:2018-05-01 19:28 本文對應(yīng)github地址:https://github.com/yelloxing/... 以上實(shí)現(xiàn)...

    EscapedDog 評論0 收藏0
  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要:這是一個簡單的遞歸函數(shù),你可以使用它來生成數(shù)列中指定序號的數(shù)值這個函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu): 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸:遞歸是很多算法都使用的一種編程方法   - 如何將問題分成基線條件和遞歸條件   - 分而治之策略解決棘手問題 ...

    wuyumin 評論0 收藏0
  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要:這是一個簡單的遞歸函數(shù),你可以使用它來生成數(shù)列中指定序號的數(shù)值這個函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu): 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸:遞歸是很多算法都使用的一種編程方法   - 如何將問題分成基線條件和遞歸條件   - 分而治之策略解決棘手問題 ...

    Carson 評論0 收藏0
  • 動態(tài)規(guī)劃法(八)最大子數(shù)組問題(maximum subarray problem)

    摘要:動態(tài)規(guī)劃法用表示最大子數(shù)組的結(jié)束下標(biāo)為的情形,則對于,有這樣就有了一個子結(jié)構(gòu),對于初始情形,遍歷就能得到這個數(shù)組,其最大者即可最大子數(shù)組的和。動態(tài)規(guī)劃法想法巧妙,運(yùn)行效率也高,但是沒有普遍的適用性。 問題簡介 ??本文將介紹計(jì)算機(jī)算法中的經(jīng)典問題——最大子數(shù)組問題(maximum subarray problem)。所謂的最大子數(shù)組問題,指的是:給定一個數(shù)組A,尋找A的和最大的非空連續(xù)...

    jzman 評論0 收藏0
  • 看動畫輕松理解「遞歸」與「動態(tài)規(guī)劃

    摘要:程序員小吳打算使用動畫的形式來幫助理解遞歸,然后通過遞歸的概念延伸至理解動態(tài)規(guī)劃算法思想。因此,分治策略一般用來解決子問題相互對立的問題,稱為標(biāo)準(zhǔn)分治,而動態(tài)規(guī)劃用來解決子問題重疊的問題。難點(diǎn)就在于找出動態(tài)規(guī)劃中的這三個概念。 在學(xué)習(xí)「數(shù)據(jù)結(jié)構(gòu)和算法」的過程中,因?yàn)槿肆?xí)慣了平鋪直敘的思維方式,所以「遞歸」與「動態(tài)規(guī)劃」這種帶循環(huán)概念(繞來繞去)的往往是相對比較難以理解的兩個抽象知識點(diǎn)。...

    cnio 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<