[アルゴリズム]再帰関数with pyhon

さいきかんすう

定義フェーズで自身の関数を再参照する

コール独自のモードを終了するには、ベース条件(Base condition)と呼ばれる脱出条件を作成する必要がある.

再構築可能な関数を設計する3つのステップ!!きっと！！

1)関数の役割を言語で正確に定義する.
2)基本条件では,関数は正常な動作を示す.
3)関数(小さな入力に対して)が正常に動作していると仮定し,関数を完了する.

再帰関数nのドア回転(Advanced Brute-Force)を使用する

完全検索(brute-force)はfor文であり、入力したn値nのfor文に従う必要がある場合は、再帰関数を使用して完全検索を行います.

質問する

任意の自然数はそれより小さい自然数の和で表すことができる.たとえば、4の場合、
4
= 3+1
= 2+2
= 2+1+1
= 1+1+1+1
上記の方法で表現できます.この場合、数字の構成が同一であるが順序のみが異なる場合は同一であると考えられ、例えば以下の3つの場合はいずれも同一である.
2 + 1 + 1, 1 + 2 + 1 , 1 + 1 + 2
再帰呼び出しを使用して、自然数nを入力し、n未満の自然数の和を表すすべての方法を出力するプログラムを作成してください.
入力
1行目は2以上20以下の自然数nを与える.
しゅつりょく
最初のローから、ローごとにメソッドが出力されます.1つの式には大きな数字が前に進み、全体的に大きな数字を先に出力します.数字とプラス記号の間にスペースはありません.そして、分割された自然数の個数を最後の行に出力する.

に答える

再帰関数を迂回して完全検索を行い、結果を結果配列に格納します.
これまで求めた値の和がnに等しいと脱出する.
反復検査:例えば、nが4の場合、1+3などの組合せは3+1の組合せと反復する.この場合、3+1の組合せは先に格納されるため(問題では大きい順から小さい順にリストすることが推奨される)、resultのインデックス値が前のインデックス値より大きい場合は、繰り返し処理することができる.

result=[0]*30 #result에다가 재귀함수 돌린 값들을 저장할것임. 일단 0 30개짜리 빈 배열 만들어놓음. 
n=int(input())
count=0

def getResult(mySum,index): #현재까지 구한 합이 mySum, index번째 숫자를 결정할 차례
  if (mySum==n): #탈출조건 : 현재까지 구한 합이 주어진 n과 같아지면 result와 count를 출력하고 탈출한다.
    print(result[0],end='')
    for i in range(1,index):
      print("+",end='')
      print(result[i],end='')
    print()
    global count
    count+=1
  else: 
    myNumber=0
    if(index==0):
      myNumber=n-1
    else: myNumber = n-mySum
    for i in range(myNumber,0,-1):
      result[index]=i
      if(index>0 and result[index-1]<result[index]): #중복확인
        continue;
      getResult(mySum+i, index+1)  
      
getResult(0,0)      
print(count)