JOYKIT

피보나치 수열은 흔히 재귀적으로 정의하는 또 따른 수학적인 함수이다.

예를 들어 새로 태어난 두 마리 토끼가 우리 안에 있다고 가정해본다. 한마리는 수컷이고 한 마리는 암컷이다. 이 토끼들은 출생한지 한 달이 지나면 가능하며 임신 기간은 한 달이라고 해본다.

만약 이런 특성을 가진 토끼들이 절대로 죽지 않으며 암토끼가 출산할 때마다 수컷과 암컷 토끼를 한마리씩 낳는다고 하면 6개월 후 임신한 토끼는 몇마리나 될까?

6개월 후 임신한 토끼 마리 수

위의 테이블에서 개월 수가 1보다 큰 경우의 식은 다음과 같다.

females(n) = females(n-1) + females(n-2)

각 암토끼는 n-1개월 동안 살아있으며 n개월에도 살아있을 것이다. 거기에다 각 n-2개월에 살아있던 각 암토끼는 n개월에 새로운 암토끼를 출생할 것이다. 그러므로 새로 출생한 암토끼의 수를 n-1개월에 살아있는 암토끼의 수에 더하여 n개월에 살아있는 암토끼의 수를 구하게 된다.

개체수의 증가는 반복을 통해 나타난다.

이것은 피보나치 반복과 그것을 테스트할 수 있는 테스트 함수를 함께 구현한 것이다.

# 피나보치 수열의 재귀적 구현
def fib(n):
    """Assume n an int >= 0
       Returns Fibonacci of n"""
    if n == 0 or n ==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
def testFib(n):
    for i in range(n+1):
        print('fib of', i, '=', fib(i))

print('n개월 후 수량 : ', fib(6))
print('testFib : ', testFib(6))

출력결과 

n개월 후 토끼 마리 수 :  13
fib of 0 = 1
fib of 1 = 1
fib of 2 = 2
fib of 3 = 3
fib of 4 = 5
fib of 5 = 8
fib of 6 = 13
testFib :  None

피보나치 수열은 흔히 재귀적으로 정의하는 또 따른 수학적인 함수이다.

예를 들어 새로 태어난 두 마리 토끼가 우리 안에 있다고 가정해본다. 한마리는 수컷이고 한 마리는 암컷이다. 이 토끼들은 출생한지 한 달이 지나면 가능하며 임신 기간은 한 달이라고 해본다.

만약 이런 특성을 가진 토끼들이 절대로 죽지 않으며 암토끼가 출산할 때마다 수컷과 암컷 토끼를 한마리씩 낳는다고 하면 6개월 후 임신한 토끼는 몇마리나 될까?

6개월 후 임신한 토끼 마리 수

위의 테이블에서 개월 수가 1보다 큰 경우의 식은 다음과 같다.

females(n) = females(n-1) + females(n-2)

각 암토끼는 n-1개월 동안 살아있으며 n개월에도 살아있을 것이다. 거기에다 각 n-2개월에 살아있던 각 암토끼는 n개월에 새로운 암토끼를 출생할 것이다. 그러므로 새로 출생한 암토끼의 수를 n-1개월에 살아있는 암토끼의 수에 더하여 n개월에 살아있는 암토끼의 수를 구하게 된다.

개체수의 증가는 반복을 통해 나타난다.

이것은 피보나치 반복과 그것을 테스트할 수 있는 테스트 함수를 함께 구현한 것이다.

# 피나보치 수열의 재귀적 구현
def fib(n):
    """Assume n an int >= 0
       Returns Fibonacci of n"""
    if n == 0 or n ==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
def testFib(n):
    for i in range(n+1):
        print('fib of', i, '=', fib(i))

print('n개월 후 수량 : ', fib(6))
print('testFib : ', testFib(6))

출력결과 

n개월 후 토끼 마리 수 :  13
fib of 0 = 1
fib of 1 = 1
fib of 2 = 2
fib of 3 = 3
fib of 4 = 5
fib of 5 = 8
fib of 6 = 13
testFib :  None

첫 번째 factI(n)식은 바탕 명제를 정의한것이고, 두 번째 factR식은 이전에 계승된 수에 관해서 바탕 명제를 제외한 모든 자연수의 계승을 정의한것이다.

#계승을 반복함수로 구현한 factI와 재귀함수로 구현한 factR 코드
def factI(n):
    """Assumes that n is an int > 0
       Returns n!"""
    result = 1
    while n > 1:
        result = result*n
        n -= 1
        return result

def factR(n):
    """Assumes that n is an int > 0
       Returns n!"""
    if n == 1:
        return n
    else:
        return n*factR(n-1)  
    
print('factI : ', factI(1))
print('factR : ',factR(1))

출력결과

먼저 factI 함수부터 살펴보면 n=1인 경우 반복문 while n > 1이 리턴하지 않으므로 결과는 None이 된다.

그리고 factR 함수는 n = 1인 경우 결과값 1을 그대로 반환하게 된다.

factI :  None
factR :  1

factI에서 n = 2인 경우 result = result*n  →  result = 1*2가 되어 결과 값은 2가 된다.

factR에서 n = 2인 경우 n*(n-1)! = 2x(2-1)=2가 출력된다.

factI :  2
factR :  2

factI에서 n = 3인 경우 result = result*n  →  result = 1*3가 되어 결과 값은 3가 된다.

factR에서 n = 3인 경우 n*(n-1)! = 3x(3-1)!=3x2!이 되어 6이 출력된다.

factI :  3
factR :  6

findRoot 함수는 제곱근을 찾는데 사용했던 이분 검색을 일반화하는 함수이고, testFindRoot는 findRoot가 제대로 작동하는지 검사할 때 사용하는 함수이다.

프로그램이 제대로 작동하지 않을 때 문제가 어디서 발생하는지 찾고 그것을 고치는 작업을 할 때 만약 미리 테스트 코드를 짜놓는다면 매번 쉘에 시험사례를 입력하여 검사를 하는것 보다 훨씬 수월하게 오류를 찾아낼 수 있다.

#근의 근사값 찾기
def findRoot(x, power, epsilon):
    """Assumes x and epsilon int or float, power an int, 
    epsilon > 0,& power >=1
    Returns float y such that y**power is within epsilon of x.
    If such a float does not exist, it returns None"""
    if x < 0 and power%2 == 0:
        return None
    low = min(-1.0, x)
    high = max(1.0, x)
    ans = (high + low)/2.0
    while abs(ans**power - x) >= epsilon:
        if ans**power < x:
            low = ans
        else:
            high = ans
        ans = (high + low)/2.0
    return ans

def testFindRoot():
    epsilon = 0.0001
    for x in (0.25, -0.25, 2, -2, 8, -8):
        for power in range(1, 4):
            print('Testing x = ' + str(x) + 'and power = ' + str(power))
            result = findRoot(x, power, epsilon)
            if result == None:
                print('No root')
            else:
                print(' ', result**power, '~=', x)

print('testFindRoot :', testFindRoot())
print('findRoot : ', findRoot(4, 2, 0.1))

findRoot의 사양은 그 사양을 만족시키는 모든 구현 가능한 것들을 추상화한 것이다. 

findRoot의 고객은 구현된것이 사양대로 작동한다고 가정할 수 있지만 고객은 그 이상 어떤 것도 추정해서는 안된다.

예를 들어 고객이 findRoot(4.0, 2, 0.1)을 호출하면 제곱으로 3.99에서 4.01 사이의 값을 가진 어떤 값을 변환한다는 것을 추정할 수 있다. 그 값은 양수일 수도 있고 음수일수 있으며 4.0이 완전 제곱이라 할지라고 반환된 완전 제곱 값은 2.0이나 -2.0이 아닐 수도 있다.

출력결과

Testing x = 0.25and power = 1
  0.25 ~= 0.25
Testing x = 0.25and power = 2
  0.25 ~= 0.25
Testing x = 0.25and power = 3
  0.24990749079734087 ~= 0.25
Testing x = -0.25and power = 1
  -0.25 ~= -0.25
Testing x = -0.25and power = 2
No root
Testing x = -0.25and power = 3
  -0.24990749079734087 ~= -0.25
Testing x = 2and power = 1
  1.999908447265625 ~= 2
Testing x = 2and power = 2
  2.0000906325876713 ~= 2
Testing x = 2and power = 3
  2.000059155646067 ~= 2
Testing x = -2and power = 1
  -1.999908447265625 ~= -2
Testing x = -2and power = 2
No root
Testing x = -2and power = 3
  -2.000059155646067 ~= -2
Testing x = 8and power = 1
  7.999931335449219 ~= 8
Testing x = 8and power = 2
  7.99999568007479 ~= 8
Testing x = 8and power = 3
  8.000068664747232 ~= 8
Testing x = -8and power = 1
  -7.999931335449219 ~= -8
Testing x = -8and power = 2
No root
Testing x = -8and power = 3
  -8.000068664747232 ~= -8
testFindRoot : None
findRoot :  2.0078125

함수 : f(x) = x^2 + y, y = 1

x = 3일 경우,  f(3) = 3 ^2 + 1 = 9 + 1 = 10이 된다.

# 2차 방정식 함수
def f(x):
    y = 1
    x = (x**2) + y
    return x

x = 3 
z = f(x)

print('x = 3일 때 f(3) = 3^2 + 1 : ', z)

출력결과 

x = 3일 때 f(3) = 3^2 + 1 :  10

먼저 def로 함수 f(x)를 정의한다.

즉 f(x)는 f(x) = x + y 가 된다.

아래 코드에서처럼 y값은 이미 정해져 있고, x값만 변경하여 주면 z = f(x)의 값이 변형된다. 

x = 5인 경우 f(5) = 5 + 1 = 6이 된다.

# 1차 방정식 함수 정의
def f(x):
    y = 1
    x = x + y
    print('x =', x)
    return x
x = 5
y = 2
z = f(x)
print('z =', z)
print('x =', x)
print('y =', y)

출력결과

x = 6
z = 6
x = 5
y = 2

# 함수 정의
def max(x, y):
    if x > y: 
        return x
    else:
        return y
    
x = 3
y = 5
print('최대 값 : ', max(x,y))

파이썬에서 def는 함수의 시작을 알리는 예약어이다.

위 코드에서 max는 함수를 호출하기 위해 사용된다. 함수 이름 뒤 괄호 안에 변수 이름들을 나열하는데, 이를 함수의 매개변수라고 한다.

함수가 실제 호출될 때, 형식 매개 변수들은 실 매개변수에 바인딩되며, 이러한 실 매개변수를 인수라고 부른다. 

다음과 같이 max(x, y) 함수를 호출하면 형식 매개변수 x는 실 매개변수 3에 바인딩되고, y는 실 매개변수 5에 바인딩된다.

출력결과

최대 값 :  5

실행 지점은 함수가 호출된 지점에서 함수의 본체로 이동하며, 본체에 있는 코드는 반환문을 만날 때까지 실행된다. 이 경우 return 뒤에 쓰여진 수식이 함수 호출 값이 되거나 더 이상 실행할 서술문이 없으면 none을 반환하게 된다. 

# 이분 검색를 사용한 제곱근의 근사치 찾기
x = 25
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0
while abs(ans**2 - x) >= epsilon:
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low)/2.0
print('numGuesses = ', numGuesses)
print(ans, 'is close to square root of', x)

출력결과

numGuesses =  13
5.00030517578125 is close to square root of 25

근사값을 구할 때 가장 보편적으로 사용하는 알고리즘은 아이작  뉴턴이 고안한 것이다.

한 개의 변수를 가진 다항식은 0이거나 0이 아닌 항들의 합이다. 각 항은 상수와 음수가 아닌 값만큼 거듭제곱된 변수의 곱으로 이루어져 있다. 예를 들어 3X^2 + 2X +3이라는 다항식에서 첫 번째 항 3x^2는 상수 3과 제곱된 변수 x의 곱이다.

만약 다항식 p와 실수 r이 있다면 x=r일 때 다항식의 값을 P(r)이라고 할 것이다. 방정식 p=0의 해는 p의 근이다. 즉 P(r)=0이 될 때의 r인 것이다. 그러므로 예를 들어 24의 제곱근의 근사값을 찾는 문제가 주어졌을 때는 x^2 - 24 = 0에서 x의 값을 찾으면 된다.

뉴턴은 어떤 값 guess가 다항식의 근의 근사값일 때 p'가 p의 1차 도함수라고 한다면 guess - P(guess)/P'(guess)가 더 나은 근사값이 된다는 원리를 증명하였다. 어떤 상수 k와 계수 c가 있을 때 cx^2 + k의 1차 도함수는 2cx이다. 또 x^2 - k의 1차 도함수는 2x이다. 그러므로 현재의 추측 값에서 다시한번 y - (y^2 - k)/2y를 구하여 더 나은 근사값을 구할 수 있음을 알 수 있다. 이것을 연속 근사법(successive approximation)이라고 한다.

다음 코드는 이런 방법으로 제곱근의 근사값을 좀 더 빠르게 구하는 것을 구현한 코드이다. 

epsilon = 0.01
k = 24.0
i = 0
guess = k/2.0
while abs(guess*guess - k) >= epsilon:
    i = i + 1
    guess = guess - (((guess**2) - k)/(2*guess))
print('Square root of', k, 'is about', guess)
print('반복회수 : ', str(i))

출력결과

Square root of 24.0 is about 4.8989887432139305
반복회수 :  4

2진수를 10진수로 변환하는 함수는 int()이고,

10진수를 2진수로 변환하는 함수는 bin이다.

# 2진수  1001를 10진수로 바꾸기
# 10진수 9를 2진수로 바꾸기

a = int('1001', 2)
b = bin(9)

print('10진수 : ', a)
print('2진수 : ', b)

출력결과 :

10진수 :  9
2진수 :  0b1001