Code Eatアルゴリズムのクラシックコースのコースまとめ.
不正確な内容や漏れがある場合がありますので、講義をお勧めします.
次の文章で再帰関数を練習します.同様に、次の2つの要素をエクスポートして問題を解決します.
再帰関数の2つの要素

Recursive case:現在の問題が大きすぎる場合、同じ形式の小さな部分の問題を再帰的に解決

Basecase:問題が十分小さい場合は、より小さな部分に分ける必要はありません

リストを反転

質問する

パラメータを使用してlistmore listを取得し、反転したlistを返す再帰関数flipを作成します.
複文を使用してはいけません.

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    d = len(some_list)
    if d <= 1:
        return some_list
    return some_list[-1:] + flip(some_list[:-1])

# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)

# 콘솔 출력
[9, 8, 7, 6, 5, 4, 3, 2, 1]

に答える

リストの長さをdと呼ぶ.
まずbasecaseを考えてみましょう.
d=1の場合、反転しても同じ値が返されるので、常にflip(some_list)=some_listである.
再帰caseを考えてみましょう.
d=5人リスト[1, 2, 3, 4, 5]の場合.この場合、リストを[1, 2, 3, 4]と[5]に分割し、[5]と[1, 2, 3, 4]のリストをマージして返すことができます.このとき[1, 2, 3, 4]を覆す一部の問題が発生し,再帰的に解決できる.

コード#コード#

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    d = len(some_list)
    if d <= 1: # base case
        return some_list
    # recursive case
    return some_list[-1:] + flip(some_list[:-1])

# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)

# 콘솔 출력
[9, 8, 7, 6, 5, 4, 3, 2, 1]

バイナリ・ナビゲーションを使用して再帰的に実装

質問する

再帰関数を用いてバイナリ探索アルゴリズムを実現する.

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # 코드를 작성하세요.

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

# 콘솔 출력
0
None
2
1
4

に答える

まずbasecaseを考えてみましょう.
basecaseは2つを考慮することができる.
1.探したい要素がない場合は、Noneを返します.
2.エンティティが見つかった場合、インデックスが返されます.
1つ目が存在しない場合は複数回バイナリ検索を行い,start_index<end_indexの場合,値は存在しないと考えられる.
2回目にエリオットを見つけたら、インデックスを返します.start indexとend indexを基準とすると、中間値はセグメントに等しい.

コード#コード#

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1
    mid = (start_index + end_index + 1) // 2
    if start_index > end_index:
        return None
    if some_list[mid] == element:
        return mid
    if some_list[mid] > element:
        end_index = mid - 1
    elif some_list[mid] < element:
        start_index = mid + 1
    return binary_search(element, some_list, start_index, end_index)

    # 코드를 작성하세요.

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

# 콘솔 출력
0
None
2
1
4

ハノイの塔

質問する

ハノイタワーの解答を出力する関数hanoiを書き出します.hanoiはパラメータとして原版数(num disks)、ゲーム開始柱番号(start peg)、ターゲット柱番号(end peg)を入力する.すべての転送元の順序を再帰的に解く.

ハノイのタワールール

一度に1枚のバックグラウンドしか移動できません.
2.大きな円板は小さな円板にはできません.
このゲームの目標は左柱の円板を右柱に移すことです.

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))

def hanoi(num_disks, start_peg, end_peg):
    # 코드를 입력하세요.

# 테스트 코드 (포함하여 제출해주세요)
hanoi(3, 1, 3)

# 콘솔 출력
1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동

に答える

basecaseが見つかりました。

原版個数がゼロの場合.何もしなくてもいいです.

if num_disks == 0:
    return

再帰caseを探します。

バックシートが1枚しかない場合-一部の問題1

1番柱は3番柱に移動します.
(ディスクをstart pegからend pegに移動します.)

if num_disks == 1:
    move_disk(num_disks, start_peg, end_peg)

2つのディスクの場合-部分的な問題2

1番円盤は1番柱から2番柱に移動します.
(ディスクをstart pegからother pegに移動します)

2番円盤は1番柱から3番柱に移動します.
(ディスクをstart pegからend pegに移動します.)

1番円盤は2番柱から3番柱に移動します.
(ディスクをother pegからend pegに移動します.)
1、2、3がいずれも円板である場合、一部の問題1に等しい.

if num_disks == 2:
    other_peg = 6 - start_peg - end_peg
    # 원반1를 기둥1에서 기둥2로 옮긴다.
    hanoi(num_disks-1, start_peg, other_peg)  # num_disks-1=1이므로 부분문제1을 푸는걸로 볼 수 있다.
    # 원반2를 기둥1에서 기둥3으로 옮긴다.
    move_disk(num_disks, start_peg, end_peg)
    # 원판1을 기둥2에서 기둥3으로 옮긴다.
    hanoi(num_disks-1, start_peg, other_peg)  # num_disks-1=1이므로 부분문제1을 푸는걸로 볼 수 있다.

3つのディスクの場合

最大円盤(3番円盤)を除く他の円盤(1,2番円盤)を1番柱から2番柱に移す.
(ディスクをstart pegからother pegに移動します)

最大の円盤(3番円盤)を1番柱から3番柱に移動します.
(ディスクをstart pegからend pegに移動します.)

最大円盤以外の円盤(1,2番円盤)を2番柱から3番柱に移動します.
(ディスクをother pegからend pegに移動します.)
1、3番は全部で2つの円盤を移動しました.ディスクが2つの場合、部分的な問題2と見なすことができる.

if num_disks == 3:
    other_peg = 6 - start_peg - end_peg
    # 가장 큰 원반을 제외한 나머지 원반을 기둥1에서 기둥2로 옮긴다.
    hanoi(num_disks-1, start_peg, other_peg)  # num_disks-1=2이므로 부분문제2를 푸는걸로 볼 수 있다.
    # 가장 큰 원반인 원반3을 기둥1에서 기둥3으로 옮긴다.
    move_disk(num_disks, start_peg, end_peg)
    # 가장 큰 원반을 제외한 나머지 원반을 기둥2에서 기둥3으로 옮긴다.
    hanoi(num_disks-1, start_peg, other_peg)  # num_disks-1=2이므로 부분문제2를 푸는걸로 볼 수 있다.

その後計算を繰り返し,解法は3つの円盤の場合と同じである.
作成したコードを調べると,2つのディスクの場合のコードは3つのディスクの場合のコードと同じであることがわかる.また、説明のために、1つの円盤しかない場合には、単独で書くことも可能であるが、実際には、円盤がもっと多い場合と同じバージョンを書くことができる.(基本的なケースを作成する必要があります.)したがって、再帰コードを記述することができる.コード全体をチェックしてみましょう.

コード#コード#

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))
    

def hanoi(num_disks, start_peg, end_peg):
    # base case
    if num_disks == 0:
        return
    # recursive case
    other_peg = 6 - start_peg - end_peg
    hanoi(num_disks-1, start_peg, other_peg)
    move_disk(num_disks, start_peg, end_peg)
    hanoi(num_disks-1, other_peg, end_peg)
    

# 테스트 코드 (포함하여 제출해주세요)
hanoi(3, 1, 3)

# 콘솔 출력
1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동