[이산수학] Mathematical Thinking in computer Science 3주차

Recursion 재귀

팩토리얼 함수는 양의 정수 n에 대해 1~n까지의 합이다. (n!)

팩토리얼 함수의 재귀는 n! 를 if n=1일 때 1 (base case) , if n>1일 때 nX(n-1)!

 

재귀함수에는 base case가 있어야 하고 parameter(매개변수)가 존재해야 한다.

 

문제) Coin problem 8 이상의 모든 돈이 3과 5로만 이루어질 수 있다

→ 8, 9, 10의 경우만 확인하면 그 뒤로는 3을 더하면 된다.

def change(amount):
  if amount == 24:
    return [5, 5, 7, 7]
  if amount == 25:
    return [5, 5, 5, 5, 5]
  if amount == 26:
    return [5, 7, 7, 7]  
  if amount == 27:
    return [5, 5, 5, 5, 7]
  if amount == 28:
    return [7, 7, 7, 7]      

  coins=change(amount-5)
  coins.append(5)
  return coins
    
  # complete this method

문제) 하노이의 탑

해설) 가장 밑의 원판을 옮기려면 n-1개의 원판을 옮기고나서 가능하다 → 재귀

base case인 n=1이 가능하다면 모두 가능 → 수학적 귀납법(induction) 개념과 관련되어 있음.

수학적 귀납법 Induction

1부터 n까지 더하는 공식을 수학적 귀납법을 통해 증명할 수 있다.

base case인 1이 성립함을 보이고 그 뒤에 n이 성립할 때 n+1이 성립함을 보이면 된다.

 

문제) 비행기 색칠

4color theorem 원 안의 어떤 모양이든 인접하지 않게 서로 다른 4개의 색으로 칠할 수 있다.

 

문제) 복리 계산

베르누이 방정식 x가 -1보다 크거나 같은 모든 0보다 크거나 같은 n에 대하여,

(1+x)의 n제곱은 1+xn보다 크거나 같다.

 

문제) 산술평균(arithmetic mean) 과 기하평균(geometric mean)

산술평균이 기하평균보다 크거나 같다

 

 

coursera Introduction to Discrete Mathematics for Computer Science 과정 중

Mathematical Thinking in coumputer Science 3주차 내용 정리