최대공약수
최대공약수
Greatest Common Disiver, GCD
두 개 이상의 정수의 공통 약수 중 가장 큰 값
방법
1. 정수 중 작은 값부터 1씩 감소시키면서 약수인 값을 찾는다.
2. 유클리드 알고리즘
- a와 b의 최대공약수는 b를 a로 나눈 나머지의 최대공약수와 같다.
gcd(a, b) = gcd(b, a%b) - 어떤 수와 0의 최대공약수는 자기 자신이다.
gcd(n, 0) = n
두 번째 성질이 재귀 호출의 종료조건이 된다.
유클리드 알고리즘 코드
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
피보나치 수열
Fibonacci numbers
제 1항을 0, 제 2항을 1로 두고, 그 이후의 항부터는 바로 앞의 두 수를 더한 수로 정의한다.
$$ F_n=\begin{cases}0, & n = 1\\ 1, & n = 2 \\ F_{n-2} + F_{n-1}, & n>2 \end{cases} $$
정의에 따라 1항을 1로, 2항을 1로 두기도 한다.
재귀호출을 이용해 피보나치 수를 구하는 경우, 1항과 2항의 경우가 종료조건이 될 것이다.
피보나치 수 코드
def fibonacci(n):
if n == 1:
return 0
if n == 2:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)