復帰(Recursion)

さいきかんすう

:ある関数から自分自身を呼び出して操作を実行する関数

再帰的な例示的なファクトリ問題の使用

工場の二つの条件

0! = 1

n>0はnを表します!=n * (n-1)

def factorial(n: int) -> int:
    """양의 정수 n의 팩토리얼을 구하는 과정"""
    if n > 0:
        return n * factorial(n - 1)
    else:
        return 1

if __name__ == '__main__':
    n = int(input('출력할 팩토리얼 값을 입력하세요.: '))
    print(f'{n}의 팩토리얼은 {factorial(n)}입니다.')

ユークリッドアーク除算(GCD,最大公約数を求める)問題

2つの整数値の最大公倍数を求める問題->2つの整数値がそれぞれ辺長の矩形がある場合、この矩形内に複数の正方形を埋め込むと、作成可能な矩形の中で最小の矩形辺長を探す意味と同じです

def gcd(x: int, y: int) -> int:
    """정숫값 x와 y의 최대 공약수를 반환"""
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

if __name__ == '__main__':
    print('두 정숫값의 최대 공약수를 구합니다.')
    x = int(input('첫 번째 정숫값을 입력하세요.: '))
    y = int(input('두 번째 정숫값을 입력하세요.: '))

    print(f'두 정숫값의 최대 공약수는 {gcd(x, y)}입니다.')

->2つの整数値を指定した場合、大きい値を小さい値で割った場合、小さい値は最大公約数になります.

再帰アルゴリズム解析

上から下への分析

一番上のボックスの中の関数呼び出しから始めて,次第に深く研究する分析方法

def recur(n: int) -> int:
    """순수한 재귀 함수 recur의 구현"""
    if n > 0:
        recur(n - 1)
        print(n)
        recur(n - 2)

x = int(input('정숫값을 입력하세요.: '))

recur(x)

n=3の場合

関数で再帰呼び出しを複数回実行する関数
n=4の場合
4->recur(3)、print(4)#5番目の出力、////////////////////////recur(2)
->recur(2)、print(3)#3番目の出力、recur(1)#4番目の出力//////////////////recur(1)print(2)recur(0)
->recur(1)print(2)#2番目の出力recur(0)
->recur(0)print(1)#最初の出力recur(-1)
Output : 1 2 3 1 4 1 2

じょうほうこうぶんせき

上から下への分析とは逆に、下から上へ積み重ねて分析します.
recur()関数はnが正の値の場合にのみ実行されるため,まずrecur(1)がどのように処理されるかを考える.
recur(1)実行プロセス
運転

recur(0)

1出力

実行

recur(-1)
最終出力1万

recur(2)実行プロセス
再帰

(1)実行

2出力

実行

recur(0)
recur(1)および2出力

このようにrecur(4)導出に蓄積する

再帰関数を非再帰的に実装する(末尾再帰を削除する)

末尾再帰(n-2)は「パラメータn-2として」の値を意味し、recur()関数を呼び出す
->すなわち、nの値をn-2に更新し、関数の開始点を返します.

def recur(n: int) -> int:
    """꼬리 재귀를 제거한 함수 recur"""
    while n > 0:
        recur(n - 1)
        print(n)
        n = n - 2
x = int(input('정수값을 입력하세요.: '))

recur(x)

再帰の削除

n値を出力する前にrecur(n-1)を実行する必要があるため、n=4の場合、recur(3)の処理が完了するまで4をある位置に保存し、スタックを使用する必要があります!

from stack import Stack  # stack.py의 Stack 클래스를 임포트

def recur(n: int) -> int:
    """재귀를 제거한 함수 recur"""
    s = Stack(n)

    while True:
        if n > 0:
            s.push(n)         # n 값을 푸시
            n = n - 1
            continue
        if not s.is_empty():  # 스택이 비어 있지 않으면
            n = s.pop()       # 저장하고 있는 값을 n에 팝
            print(n)
            n = n - 2
            continue
        break

x = int(input('정수값을 입력하세요.: '))

recur(x)

分割とマージ

1つのアルゴリズムで、問題をいくつかの部分に分けて解き、それから合併して問題の答えを得る.
問題設計要領
1)Divide:問題が分割可能であれば2つ以上の問題に分けられる.
2)Conquer:分割の問題がまだ分割可能であれば再分割
3)Combine:Conquerは問題を統合して元の問題の答えを得る

ハノイの塔問題

ハノイの塔は小円盤上、大円盤下のルールを守り、3本の柱を利用して円盤を移動する問題がある.
3つのディスクの移動プロセス全体

3つのディスクの場合

組(ディスク1,2)が始点柱->中間柱

円板3を先頭柱->ターゲット柱

組(円柱1,2)が中間柱->ターゲット柱

2つのディスクの場合

組(円盤1)が始点柱->中間柱

円板2を先頭柱->ターゲット柱

組(円盤1)は中間柱->目標柱

4つのディスクの場合

組(ディスク1,2,3)が始点柱->中間柱

円板4を先頭柱->ターゲット柱

組(円盤1,2,3)は中間柱->ターゲット柱

def move(no: int, x: int, y: int) -> None:
    """원반을 no개를 x 기둥에서 y 기둥으로 옮김"""
    if no > 1:
        move(no - 1, x, 6 - x - y)

    print(f'원반 [{no}]을(를) {x}기둥에서 {y}기둥으로 옮깁니다.')

    if no > 1:
        move(no - 1, 6 - x - y, y)

print('하노이의 탑을 구현하는 프로그램입니다.')
n = int(input('원반의 개수를 입력하세요.: '))

move(n, 1, 3)

8皇后問題

8皇后問題は8×8サイズのチェス盤に8皇后を配置する問題です.1848年にマックス・ベッチェルが初めて提出した.この問題を一般化すると,NxNサイズのチェス盤にN個のクイーンを置くNクイーン問題である.

pos = [0] * 8          # 각 열에 배치한 퀸의 위치
flag_a = [False] * 8   # 각 행에 퀸을 배치했는지 체크
flag_b = [False] * 15  # 대각선 방향(↙↗)으로 퀸을 배치했는지 체크
flag_c = [False] * 15  # 대각선 방향( ↘↖)으로 퀸을 배치했는지 체크

def put() -> None:
    """각 열에 배치한 퀸의 위치를 출력"""
    for i in range(8):
        print(f'{pos[i]:2}', end='')
    print()

def set(i: int) -> None:
    """i 열의 알맞은 위치에 퀸을 배치"""
    for j in range(8):
        if(     not flag_a[j]            # j행에 퀸이 배치 되지 않았다면
            and not flag_b[i + j]        # 대각선 방향(↙↗)으로 퀸이 배치 되지 않았다면
            and not flag_c[i - j + 7]):  # 대각선 방향( ↘↖)으로 퀸이 배치 되지 않았다면
            pos[i] = j  # 퀸을 j행에 배치
            if i == 7:  # 모든 열에 퀸을 배치하는 것을 완료
                put()
            else:
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
                set(i + 1)  # 다음 열에 퀸을 배치
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False

set(0)  # 0열에 퀸을 배치