第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題,去搜搜看,總會(huì)有你想問(wèn)的

python中的遞歸沒(méi)有達(dá)到正確的結(jié)果

python中的遞歸沒(méi)有達(dá)到正確的結(jié)果

動(dòng)漫人物 2021-11-16 17:00:28
我有一個(gè)問(wèn)題,想要找到列表子集的總和為特定值的方式數(shù)。但是,如果我手動(dòng)運(yùn)行遞歸公式,我會(huì)得到一個(gè)與 python 代碼不同的(正確的)值。我錯(cuò)過(guò)了什么,或者為什么我得到不同的結(jié)果?假設(shè)我有一個(gè)列表b = [2,3,2,1,4],目標(biāo)值為T = 5. 然后將有 4 個(gè)子集與目標(biāo)值相加:{b[0], b[1]}{b[0], b[2], b[3]}{b[4], b[3]}{b[1], b[2]}以下代碼給出的結(jié)果為 2,但我希望它返回 4。b = [2,3,2,1,4]def subset_sum(T, idx):    if T < 0 or idx< 0:        return 0    if T == 0:        return 1    else:        return subset_sum(T, idx-1) + subset_sum(T-b[idx], idx-1) if __name__ == "__main__":    print(subset_sum(5, 4))基于@TomDalton 評(píng)論進(jìn)行編輯:我嘗試了這個(gè)并認(rèn)為這可能是因?yàn)閮蓚€(gè) if 語(yǔ)句沒(méi)有同時(shí)檢查 - 因此在 idx = 0 并且我們從值 T 中減去 b[0] 的情況下,然后在下一次迭代中它將返回 0,因?yàn)樗跈z查 T == 0 之前檢查 idx < 0。雖然我不確定我的猜測(cè)的有效性
查看完整描述

3 回答

?
慕工程0101907

TA貢獻(xiàn)1887條經(jīng)驗(yàn) 獲得超5個(gè)贊

這是帶有額外檢測(cè)的代碼,可幫助跟蹤輸出,縮進(jìn)遞歸調(diào)用。


您會(huì)注意到計(jì)數(shù)的一個(gè)嚴(yán)重問(wèn)題:當(dāng)您獲得所需的總數(shù)并到達(dá)列表末尾時(shí),您返回0而不是1。這會(huì)阻止您通過(guò)使用最終列表元素正確累積獲得正確總數(shù)的解決方案,因?yàn)樵跈z查是否獲得正確總數(shù)之前,您會(huì)重復(fù)超過(guò)列表末尾。維修在底部。


indent = ""

b = [2,3,2,1,4]


def subset_sum(total, idx):

    global indent

    print(indent + "ENTER", total, idx)

    indent += "  "


    if total < 0 or idx < 0:

        result = 0

    elif total == 0:

        result = 1

    else:

        result = subset_sum(total, idx-1) + subset_sum(total-b[idx], idx-1) 


    indent = indent[2:]

    print(indent + "LEAVE", total, idx, result)

    return result


if __name__ == "__main__":

    print(subset_sum(5, 4))

輸出:


ENTER 5 4

  ENTER 5 3

    ENTER 5 2

      ENTER 5 1

        ENTER 5 0

          ENTER 5 -1

          LEAVE 5 -1 0

          ENTER 3 -1

          LEAVE 3 -1 0

        LEAVE 5 0 0

        ENTER 2 0

          ENTER 2 -1

          LEAVE 2 -1 0

          ENTER 0 -1

          LEAVE 0 -1 0

        LEAVE 2 0 0

      LEAVE 5 1 0

      ENTER 3 1

        ENTER 3 0

          ENTER 3 -1

          LEAVE 3 -1 0

          ENTER 1 -1

          LEAVE 1 -1 0

        LEAVE 3 0 0

        ENTER 0 0

        LEAVE 0 0 1

      LEAVE 3 1 1

    LEAVE 5 2 1

    ENTER 4 2

      ENTER 4 1

        ENTER 4 0

          ENTER 4 -1

          LEAVE 4 -1 0

          ENTER 2 -1

          LEAVE 2 -1 0

        LEAVE 4 0 0

        ENTER 1 0

          ENTER 1 -1

          LEAVE 1 -1 0

          ENTER -1 -1

          LEAVE -1 -1 0

        LEAVE 1 0 0

      LEAVE 4 1 0

      ENTER 2 1

        ENTER 2 0

          ENTER 2 -1

          LEAVE 2 -1 0

          ENTER 0 -1

          LEAVE 0 -1 0

        LEAVE 2 0 0

        ENTER -1 0

        LEAVE -1 0 0

      LEAVE 2 1 0

    LEAVE 4 2 0

  LEAVE 5 3 1

  ENTER 1 3

    ENTER 1 2

      ENTER 1 1

        ENTER 1 0

          ENTER 1 -1

          LEAVE 1 -1 0

          ENTER -1 -1

          LEAVE -1 -1 0

        LEAVE 1 0 0

        ENTER -2 0

        LEAVE -2 0 0

      LEAVE 1 1 0

      ENTER -1 1

      LEAVE -1 1 0

    LEAVE 1 2 0

    ENTER 0 2

    LEAVE 0 2 1

  LEAVE 1 3 1

LEAVE 5 4 2

2

修理


在檢查是否超出列表末尾之前,只需檢查是否成功:


if total == 0:

    result = 1

elif total < 0 or idx < 0:

    result = 0


查看完整回答
反對(duì) 回復(fù) 2021-11-16
?
墨色風(fēng)雨

TA貢獻(xiàn)1853條經(jīng)驗(yàn) 獲得超6個(gè)贊

您是否考慮過(guò)迭代方法?itertools.combinations想到


itertools.combinations(iterable, r)

從輸入可迭代返回 r 個(gè)長(zhǎng)度的元素子序列。


組合按字典排序順序發(fā)出。因此,如果輸入可迭代對(duì)象已排序,則組合元組將按排序順序生成。


有了這個(gè),您可以執(zhí)行以下操作:


from itertools import combinations


def count_subsets(main_list, target):

    result = 0

    for i in range(len(main_list)):

        sets = combinations(main_list, i)

        result += sum(sum(subset) == target for subset in sets)

    return result


查看完整回答
反對(duì) 回復(fù) 2021-11-16
?
慕哥6287543

TA貢獻(xiàn)1831條經(jīng)驗(yàn) 獲得超10個(gè)贊

問(wèn)題是你在 idx < 0 時(shí)退出,但沒(méi)有先檢查是否 T == 0(這將是一個(gè)解決方案)。您應(yīng)該首先測(cè)試 T == 0:


if T == 0:

    return 1

elif T < 0 or idx< 0:

    return 0

else:

    return subset_sum(T, idx-1) + subset_sum(T-b[idx], idx-1) 


查看完整回答
反對(duì) 回復(fù) 2021-11-16
  • 3 回答
  • 0 關(guān)注
  • 231 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)