[Python]アルゴリズム2.再帰呼び出し

1.実際の

1~n連続整数の積
n : 1 x 2 x ... x n-1 x n

1)繰り返し文の使用

def fact1(n):
	f = 1
    for i in range(1, n+1):
    	f = f * i
    return f

2)再帰呼び出し

終了条件が必要

1! = 1
2! = 1 x 2 = 2 x 1!
3! = 1 x 2 x 3 = 3 x 2!
n! = 1 x 2 x ... x (n-1) x n = n x (n-1)!

def fact2(n):
	if n<=1: # 종료 조건
    	return 1
    return n * fact(n-1)

ex) fact2(4)
-> 4! = 4 x 3! = 4 x 3 x 2! = 4 x 3 x 2 x 1! = 4 x 3 x 2 = 4 x 6 = 24
3)性能

for文:乗算n

再帰呼び出し:乗算n-1
全てO(n)

4)応用
4-1)1~nの和:再帰呼び出し

def sum_n(n):
    if n == 1:
        return 1
    return n + sum_n(n-1)

print(sum_n(3))

4-2)n個の数値の中で最も高い値を探す:再帰呼び出し

def find_max(a, n):
    if n == 1:
        return a[0]
    max_n = find_max(a, n-1)

    if max_n > a[n-1]:
        return max_n
    else:
        return a[n-1]
    
    
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max(v, len(v)))

2.最大公約数を求める

2つ以上の整数のうち最大の整数

1)繰り返し文

def gcd(a, b):
	i = min(a,b)
    while True:
    	if a % i == 0 and b % i == 0:
        	return i
        i = i - 1

2)ユークリッドアルゴリズム

aおよびbの最大承諾数は、bおよびa%bの残りの最大承諾数

に等しい

gcd(a,b) = gcd(b, a%b)

0の最大承諾数は自己->終了条件

gcd(n, 0) = n

ex) gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12

def gcd(a,b):
	if b == 0:
    	return a
    return gcd(b, a%b)

3)フィボナッチ数列

0, 1, 1, 2, 3, 5, 8, 13 ...

def pibo(n):
	if n <= 1:
    	return n

    return pibo(n-1) + pibo(n-2)

3.ハノイの塔

ウエハ出力n個のハノイタワーのウエハ移動順序のアルゴリズム

n個の大きさの異なる円盤を始点柱から到達柱に移動

円盤は一度に1つしか移動できません

ディスクを移動する場合は、ディスク上部の

のみ移動できます.

大きなディスクは小さなディスクに移動できません.

1)回答
1-1)ディスクが1個の場合

円盤を柱1から柱3

へ一度に移動可能
1-2)ディスクが2つある場合

1号柱の頂部円盤を柱2

に移動

1号柱の底部円盤を柱3

に移動

2号柱の円盤を柱3

に移動

3次移動ディスク

1～3)3つのディスク

2個の円盤が柱2に移動(原理は1-2と同じ):1->3、2->2、1->2

1号柱の最後の円盤が柱3

に移動

柱2の上部円盤を柱1

に移動

柱2の円盤を柱3

に移動

柱1の円盤を柱3

に移動

7次移動ディスク

1-4)円板はn個

1番柱のn-1個の円盤を2番柱

に移動

1番柱の最後の円盤が3番柱

に移動

2番柱のn-1個の円盤を2番柱に移動

2)実施

def hanoi (n, from_pos, to_pos, aux_pos):
    if n ==1:
        print("출발:", from_pos)
        print("->")
        print("도착:", to_pos)
        return
    
    hanoi(n-1, from_pos, aux_pos, to_pos)
    print("출발:", from_pos)
    print("->")
    print("도착:", to_pos)
    hanoi(n-1, aux_pos, to_pos, from_pos)


hanoi(3, 1, 3, 2) 

hanoi(n-1, from_pos, aux_pos, to_pos):n-1個の円盤が補助柱

に移動

hanoi(n-1, aux_pos, to_pos, from_pos):補助柱のn-1個の円盤を目標柱に移動します.

3)分析

演算回数:2^n-1

性能:O(2^n)
4.再帰呼び出しによる描画画像の使用

Python「亀の図形」を使う

カメ画像:ブラシを画面に作用させたカメを画面にアップロードし、カメを移動させて絵を描き始めるように命令する

1)長方形のらせんを描く

import turtle as t

def spiral(sp_len):
    if sp_len <= 5:
        return
    t.forward(sp_len)
    t.right(90)
    spiral(sp_len - 5)

t.speed(0)
spiral(200)
t.hideturtle()
t.done()

2)シルフォンスキーの三角形を描く

import turtle as t

def tri(tri_len):
    if tri_len <= 10:
        for i in range(0, 3):
            t.forward(tri_len)
            t.left(120)
        return
    new_len = tri_len / 2
    tri(new_len)
    t.forward(new_len)
    tri(new_len)
    t.backward(new_len)
    t.left(60)
    t.forward(new_len)
    t.right(60)
    tri(new_len)
    t.left(60)
    t.backward(new_len)
    t.right(60)

t.speed(0)
tri(160)
t.hideturtle()
t.done()

3)木を描く

import turtle as t

def tree(br_len):
    if br_len <= 5:
        return
    new_len = br_len * 0.7
    t.forward(br_len)
    t.right(20)
    tree(new_len)
    t.left(40)
    tree(new_len)
    t.right(20)
    t.backward(br_len)

t.speed(0)
t.left(90)
tree(70)
t.hideturtle()
t.done()

4)雪を描く

import turtle as t

def snow(snow_len):
    if snow_len <= 10:
        t.forward(snow_len)
        return
    new_len = snow_len / 3
    snow(new_len)
    t.left(60)
    snow(new_len)
    t.right(120)
    snow(new_len)
    t.left(60)
    snow(new_len)

t.speed(0)
snow(150)
t.right(120)
snow(150)
t.right(120)
snow(150)
t.hideturtle()
t.done()