アルゴリズム:再帰知識とテーマ整理-python


再帰
再帰はbaseに達するまで繰り返し呼び出します.考え方は数学の帰納法に似ている.書き方によって異なる時間で複雑に読むことに注意してください.たとえば,フィボナッチ数列を計算すると,式f(n)=f(n−1)+f(n−2)f(n)=f(n−1)+f(n−2)f(n)=f(n−1)+f(n−2)のように直接書くと,時間的代価が大きい.
万科目第1部例題
フィボナッチ数列
最も基本的な再帰
def f(n):
    assert(n>=0)
    result = [0, 1]
    for i in range(2, n+1):
        result.append(result[-2] + result[-1])
    return result

数式
23=((5*2+1)*2+1)113=(((11+1)+1)*2*2*2+1)学習:baseとreturn
def draweq(a,b):
    if a == b:
        return str(a)
    if b % 2 == 1:
        return '(' + draweq(a,b-1) + ' + 1' +')'
    if b < 2*a:
        return  '(' + draweq(a,b-1) + ' + 1' + ')'
    return   draweq(a,b/2) + ' * 2' 

このポイントは、baseが何なのか、b>=aなので、baseはb=aで、次に何を返すのか、印刷式なので、baseの場合は文字列で、実際には毎回1つの式を返すので、欠けている部分は括弧で、+1と*2があります.状況に応じて、対応する式を出力します.これがネストされたプロセスです.
印刷物差し
学習:ほんの少しの工事の感じ印刷尺度:目盛りを描く必要があり、目盛りを描くには線を描く必要があります.したがって、異なる関数が必要です.
def draw_line(length,label =''):
    line = '-'*length
    if label:
        line += ' '+ label
    print(line)
def draw_intervals(length):
    if length > 0:
        draw_intervals(length-1)
        draw_line(length)
        draw_intervals(length-1)
def draw_ruler(inches,length):
    draw_line(length,'0')
    for i in range(1,inches+1):
        draw_intervals(length-1)
        draw_line(length,str(i))

再帰的な運用は目盛りに
ハノータ
数学の帰納法の感覚.n=1、startからendに移動する限り.n=kと仮定すると、私はやり方を知っています.n=k+1の場合,k部分をbyに移動し,残りの1をendに移動し,最後にkをbyからendに移動する.
対応:baseがn=1の場合、他は私が再帰する部分です.
def hano(n,start,by,end):
    if n == 1:
        print('move from',start,'to',end)
    else:
        hano(n-1,start,end,by)
        hano(1,start,by,end)
        hano(n-1,by,start,end)

万門課程第二部分例題
1.集合のサブセット
遍歴的なやり方
def subsets(nums):
    result = [[]]
    for num in nums:
        for element in list(result):
            x = list(element)
            x.append(num)
            result.append(x)
            print(result)
        
    return result
def subsets_2(nums):
    res = [[]]
    for num in nums: 
        res += [ i + [num] for i in res]
        print(res)
    return res

ここでちょっと注意したいことがありますが、forループは直接resultでいいですか?印刷結果を確認
---- i = 1 result = [[]] ---- i = 2 result = [[], [1]] ---- i = 3 result = [[], [1], [2], [1, 2]]
final :[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
直接resultではだめです.こちらlist(result)or result[:]はリストコピーです.
最初のforループは、resultをコピーするたびに、各要素に新しい要素を追加します.ここでelementもコピーします(直接x=elementであれば、実はxelementが同じ配列を指していると、元の決まった集合が変わります.
再帰的な書き方
こちらは遡及の思想を用いた.遡及で重要な2点:
  • どのようなアクセスがありますか?
  • はどのような状態を維持しますか?
  • def subsets_recursive(nums):
        lst = []
        result = []
        subsets_recursive_helper(result, lst, nums, 0);
        return result;
    
    def subsets_recursive_helper(result, lst, nums, pos):
        result.append(lst[:])
        for i in range(pos, len(nums)):
            lst.append(nums[i]) #
            subsets_recursive_helper(result, lst, nums, i+1) #
            lst.pop()
    

    砕砕念:逐次解析しnums=[a,b,c]1.result=[[]]で、コピーであることに注意してください.2.ループ開始0_0、i=0 3.lst->[a]->最初の再帰4に入る.result = [ [] , [a] ] 5.ループ1_へ0,start 1=1,lst->[a,b]->は2回目の再帰6に入る.result = [ [] , [a] , [a,b] ] 7. ループ2_へ0,start 2=2,lst->[a,b,c]->3回目の再帰8に入る.result = [ [] , [a] , [a,b] , [a,b,c] ] 9. 【遡及】循環するものはなく、3回目の再帰に対してlst.pop()はc,->lst=[a,b]をポップアップし,3回目の再帰を終了する.[a,b,c]から元の状態に戻る[a,b]10.10.「遡及」.2回目の再帰に戻りlst.pop()ポップアップb,サイクル2終了,2回目の再帰終了,lst=[a]である.このとき、[a,b]は元の状態に戻る[a]11.ループ1_へ1,start 1+1=2,lst->[a,c]->は4回目の再帰12に入る.result = [ [] , [a] , [a,b] , [a,b,c] ,[a,c]] 13. 【遡及】何も循環していないlst.pop()はcをポップアップし,4回目の再帰終了,lst=[a]であった.このとき[a,c]から元の状態に戻る[a]14.【遡及】対ループ1_1,lst.pop()はa,lst=[],ループ1が終了し,最初の再帰が終了する.このとき[a]から元の状態[]15に戻る.締め切り、サイクル0の最初のサイクルを完了し、合計4回の再帰を行った.16.ループ0_に入る1,i=1,lst->[b]について5回目の再帰を開始する...に続く
    2.配列
    配列にはいくつかのサブ問題があります.
  • 重複しない要素の全配列
  • 繰り返し要素全配列
  • 要素kのサブセット全配列
  • 遡及法によるすべての解決:(サブセットを模倣する方法)
    def perm(nums,k):
        result = []
        lst = []
        n = len(nums)
        nums.sort()
        perm_helper(result,nums,lst,k)
        return result
    def perm_helper(result,nums,lst,k):
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            lst.append(nums[i])
            print(lst)
            perm_helper(result,nums[0:i]+nums[i+1:],lst,k)
            lst.pop()
        if len(lst) == k:
            result.append(lst[:])
        print('res =', result)
    

    サブセットとの差はどこですか?違いは、メンテナンスの結果配列(result)をいつ更新するかです.サブセットは、毎回新しいものを加えて短縮します.配列ではlstが指定された長さに達する限り、追加します.そして,元の配列をどのように減らすか.サブセット:Posを利用して、絶えず前に移動して、元の配列を縮小します;配列では、追加した要素を除去します.
    枝切りの書き方は、並べ替えて枝を切ることが意味があることに注意しましょう.[1,2,3]を例にlstをプリントアウト[1,2],[1,2],[1,2],[3,3],[1,3,2][2,1],[2,1,3][2,3],[2,3,1][3,1],[3,1],[3,1][3,2],[3,2],[3,2,2,1]すると,遡及がどこで起こったのかがはっきり見える
    交換の考え方(個人的なやり方)に基づいて(枝を切って重複を解決することができて、Kサブセットの配列はまだよく考えていません)
    思想:配列とは何か、配列は絶えず位置を交換することである.例えば、【1,2,3,4】は、【1,2,3,4】、【2,1,3,4】、【3,2,1,4】、【4,2,3,1】と理解され、これは第1の位置が他の3つの位置と交換される.そして、【2,3,4】を見ても、同様に【3,2,4】、【4,3,2】を行うことができる..このようにすれば,全配列を実現できる.
    コードは次のとおりです.
    def perm1(nums):
        nums.sort()
        num = [nums]
        for i in range(len(nums)):
            num = swap(num,i)
        return num
    def swap(num,k):
        for lis in num[:]:
            n = len(lis)
            for i in range(k+1,n):
                x = lis[:]
                if x[i-1]==x[i] :
                    continue
                x[k],x[i] = x[i],x[k]
                num.append(x)
        return num
    

    swap関数は、k位置の要素を後の要素と交換するために使用されます.次に配列はkを0からn−1まで遍歴し,全配列を得る.枝を切るのは前後の2つの同じ要素に対して、kと交換する必要はありません.そうしないと、繰り返しになります.
    参考解法:万門の授業で与えられた解法を見てみましょう
    def permUnique(result, nums):
        nums.sort()
        if (len(nums)==0):
            print(result)
        for i in range(len(nums)):
            if (i != 0 and nums[i] == nums[i-1]):
                continue;
            permUnique(result+str(nums[i]), nums[0:i]+nums[i+1:])
    

    こちらでは、なぜlen(nums)=0になったのかを考えてみましょう.ループはまだできます.再帰中のnumsはnums[0:i]+nums[i+1:]であり,このスライスは実際には複製(浅いコピー)であり,実際の最初のnums長は変わらないことに気づいた.
    3.およびKのすべてのサブセット
    それともサブセットのテンプレートを使って、いつappendしますか?目標とappendを達成します.
    2つの要件があります.
  • a.同じ要素が複数回現れることを許可する
  • .
  • b.同一の要素は一度に
  • しか使用できない.
    まずbを見ましょう
    def comb(nums,target):
        result = []
        lst = []
        nums.sort()
        helper(result,lst,nums,target)
        return result
    def helper(result,lst,nums,remain):
    	if remains < 0: return
        if remain == 0 :
            result.append(lst[:])
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            lst.append(nums[i])
            helper(result,lst,nums[i+1:],remain-nums[i])
            lst.pop()
    

    ステータスを1つ多く維持しました、remain.remainが0の場合、resultに追加します.remain<0直接returnは、繰り返し要素の剪断にも注意して遡及を開始します.
    もう一度aを見てみましょう:どのようにして同じ要素を何度も使うことができて、また繰り返しをもたらしません.まずソートし、次に使用したものが使用されないことを確認します.カリキュラムの解答は2つ目の点でもう1つのstartで保証されていますが、実際には少し変更すればいいです.
    def comb1(nums,target):
        result = []
        lst = []
        nums.sort()
        helper(result,lst,nums,target)
        return result
    def helper(result,lst,nums,remain):
    	if remains < 0: return
        if remain == 0 :
            result.append(lst[:])
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue       
            lst.append(nums[i])
            helper(result,lst,nums[i:],remain-nums[i])
            lst.pop()
    

    ループ中のnums[i+1:]をnums[i:]に変更するだけで、remain<=0までループを毎回自分から開始します.
    4.かっこの正しい組み合わせ
    正しい組み合わせというのは)です(これでは無理です.
    サブセットテンプレートの方法
    def kuohao(n):
        result = []
        lst = []
        nums = [0 if i<=n else 1 for i in range(1,2*n+1) ] #  
        helper_k(result,lst,nums,n)
        return result
    def helper_k(result,lst,nums,n):
        if len(lst) ==  2*n:
            result.append(trans(lst[:],n)) #  
        for i in range(len(nums)):
            if count(nums,n) or( i>0 and nums[i-1]==nums[i]):  #  
                continue
            lst.append(nums[i])
            helper_k(result,lst,nums[:i]+nums[i+1:],n)
            lst.pop()
    def count(nums,n): #      
        l = len([i for i in nums if i == 0])
        r = len([i for i in nums if i == 1])
        return True if l > r else False
    def trans(lst,n): #    
        for i,num in enumerate(lst[:]):
            lst[i] = '(' if num == 0 else ')'
        return ''.join(lst)
    

    考え方は簡単で、括弧は0と1にほかならない.すなわち、n個の0とn個の1がある.私がしなければならないのは0と1の配列を見つけることにほかならない.2つのコンストレイントがあります.重複した配列はありません.各配列について、左から右に0の数が1以上の数になります.方法:符号化->正常な全配列の書き方->枝切り->復号.
    カリキュラムの方法:
    def generateParenthesis(n):
        def generate(prefix, left, right, parens=[]):
            if right == 0:   parens.append(prefix)
            if left > 0:     generate(prefix + '(', left-1, right)
            if right > left: generate(prefix + ')', left, right-1)
            return parens
        return generate('', n, n)