アルゴリズム:再帰知識とテーマ整理-python
45347 ワード
再帰
再帰は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部例題
フィボナッチ数列
最も基本的な再帰
数式
23=((5*2+1)*2+1)113=(((11+1)+1)*2*2*2+1)学習:baseとreturn
このポイントは、baseが何なのか、b>=aなので、baseはb=aで、次に何を返すのか、印刷式なので、baseの場合は文字列で、実際には毎回1つの式を返すので、欠けている部分は括弧で、+1と*2があります.状況に応じて、対応する式を出力します.これがネストされたプロセスです.
印刷物差し
学習:ほんの少しの工事の感じ印刷尺度:目盛りを描く必要があり、目盛りを描くには線を描く必要があります.したがって、異なる関数が必要です.
再帰的な運用は目盛りに
ハノータ
数学の帰納法の感覚.n=1、startからendに移動する限り.n=kと仮定すると、私はやり方を知っています.n=k+1の場合,k部分をbyに移動し,残りの1をendに移動し,最後にkをbyからendに移動する.
対応:baseがn=1の場合、他は私が再帰する部分です.
万門課程第二部分例題
1.集合のサブセット
遍歴的なやり方
ここでちょっと注意したいことがありますが、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点:どのようなアクセスがありますか? はどのような状態を維持しますか?
砕砕念:逐次解析し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のサブセット全配列 遡及法によるすべての解決:(サブセットを模倣する方法)
サブセットとの差はどこですか?違いは、メンテナンスの結果配列(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】を行うことができる..このようにすれば,全配列を実現できる.
コードは次のとおりです.
swap関数は、k位置の要素を後の要素と交換するために使用されます.次に配列はkを0からn−1まで遍歴し,全配列を得る.枝を切るのは前後の2つの同じ要素に対して、kと交換する必要はありません.そうしないと、繰り返しになります.
参考解法:万門の授業で与えられた解法を見てみましょう
こちらでは、なぜlen(nums)=0になったのかを考えてみましょう.ループはまだできます.再帰中のnumsはnums[0:i]+nums[i+1:]であり,このスライスは実際には複製(浅いコピー)であり,実際の最初のnums長は変わらないことに気づいた.
3.およびKのすべてのサブセット
それともサブセットのテンプレートを使って、いつappendしますか?目標とappendを達成します.
2つの要件があります. a.同じ要素が複数回現れることを許可する . b.同一の要素は一度に しか使用できない.
まずbを見ましょう
ステータスを1つ多く維持しました、remain.remainが0の場合、resultに追加します.remain<0直接returnは、繰り返し要素の剪断にも注意して遡及を開始します.
もう一度aを見てみましょう:どのようにして同じ要素を何度も使うことができて、また繰り返しをもたらしません.まずソートし、次に使用したものが使用されないことを確認します.カリキュラムの解答は2つ目の点でもう1つのstartで保証されていますが、実際には少し変更すればいいです.
ループ中のnums[i+1:]をnums[i:]に変更するだけで、remain<=0までループを毎回自分から開始します.
4.かっこの正しい組み合わせ
正しい組み合わせというのは)です(これでは無理です.
サブセットテンプレートの方法
考え方は簡単で、括弧は0と1にほかならない.すなわち、n個の0とn個の1がある.私がしなければならないのは0と1の配列を見つけることにほかならない.2つのコンストレイントがあります.重複した配列はありません.各配列について、左から右に0の数が1以上の数になります.方法:符号化->正常な全配列の書き方->枝切り->復号.
カリキュラムの方法:
再帰は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.配列
配列にはいくつかのサブ問題があります.
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つの要件があります.
まず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)