Data structures 02.2:mathematical induction 동의대학교 멀티미디어공학과 이광의 교수.

Data structures 02.2:mathematical induction 동의대학교 멀티미디어공학과 이광의 교수

Today’s topic 재귀함수의 예와 동작방법 mathematical induction수학적 귀납법 재귀함수의 활용
계승 함수와 그 동작방법 피보나치 함수와 그 동작방법 최소공배수 함수 mathematical induction수학적 귀납법 계승 함수의 증명 피보나치 함수의 증명 최소공배수 함수의 증명 재귀함수의 활용 징검다리 건너기 당근 캐기 거북이 옮기기 Dept. of Multimedia Engineering, DongEui Univ.

Correctness of Recursive Functions
계승함수의 증명 int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } void main ( ) { cout << rFac(3); // 6을 출력 Dept. of Multimedia Engineering, DongEui Univ.

계승함수의 증명 int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } void main ( ) { cout << rFac(3); // 6을 출력 rFac () 1 N=1 rFac () 2 N=2 rFac() 6 N=3 main () Dept. of Multimedia Engineering, DongEui Univ.

계승함수의 증명 int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } void main ( ) { cout << rFac(3); // 6을 출력 무엇을 증명하여야 하는가? rFac () 1 N=1 rFac () 2 N=2 rFac() 6 N=3 main () 설명이 아니라 증명이 필요하다. 함수가 제대로 동작하는가? 모든 자연수에 n대하여 n!값을 돌려주는가? Dept. of Multimedia Engineering, DongEui Univ.

계승함수의 증명 int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } void main ( ) { cout << rFac(3); // 6을 출력 무엇을 증명하여야 하는가? rFac(1) == 1! rFac(2) == 2! … rFac(n) == n! ... rFac () 1 N=1 rFac () 2 N=2 rFac() 6 N=3 main () Dept. of Multimedia Engineering, DongEui Univ.

계승함수의 증명 int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } void main ( ) { cout << rFac(3); // 6을 출력 무엇을 증명하여야 하는가? rFac(1) == 1! rFac(2) == 2! … rFac(n) == n! ... 모든 자연수 n에 대하여 rFac(n) == n! rFac () 1 N=1 rFac () 2 N=2 rFac() 6 N=3 main () Dept. of Multimedia Engineering, DongEui Univ.

계승함수의 증명 int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } void main ( ) { cout << rFac(3); // 6을 출력 무엇을 증명하여야 하는가? rFac(1) == 1! P(1)을 rFac(1) == 1! rFac(2) == 2! P(2)를 rFac(2) == 2! … rFac(n) == n! P(n)을 rFac(n) == n! ... 모든 자연수 n에 대하여 rFac(n) == n! 모든 자연수 n에 대하여 P(n)이 성립! rFac () 1 N=1 rFac () 2 N=2 rFac() 6 N=3 main () Dept. of Multimedia Engineering, DongEui Univ.

Mathematical induction
모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) Dept. of Multimedia Engineering, DongEui Univ.

모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) 증명 P(1) P(2) P(3) P(4) … P(n-1) P(n) ... Dept. of Multimedia Engineering, DongEui Univ.

모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) 증명 P(1): 단계 1에 의하여 P(2) P(3) P(4) … P(n-1) P(n) ... P(1) Dept. of Multimedia Engineering, DongEui Univ.

모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) 증명 P(1): 단계 1에 의하여 P(2): 단계 2에서 k에 1을 대입 P(1)->P(2) P(3) P(4) … P(n-1) P(n) ... P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) 증명 P(1): 단계 1에 의하여 P(2): 단계 2에서 k에 1을 대입 P(1)->P(2) P(3): 단계 2에서 k에 2를 대입 P(2)->P(3) P(4) … P(n-1) P(n) ... P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) 증명 P(1): 단계 1에 의하여 P(2): 단계 2에서 k에 1을 대입 P(1)->P(2) P(3): 단계 2에서 k에 2를 대입 P(2)->P(3) P(4): 단계 2에서 k에 3을 대입 P(3)->P(4) … P(n-1) P(n) ... P(4) P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) 증명 P(1): 단계 1에 의하여 P(2): 단계 2에서 k에 1을 대입 P(1)->P(2) P(3): 단계 2에서 k에 2를 대입 P(2)->P(3) P(4): 단계 2에서 k에 3을 대입 P(3)->P(4) … P(n-1) P(n) ... … P(4) P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) 증명 P(1): 단계 1에 의하여 P(2): 단계 2에서 k에 1을 대입 P(1)->P(2) P(3): 단계 2에서 k에 2를 대입 P(2)->P(3) P(4): 단계 2에서 k에 3을 대입 P(3)->P(4) … P(n-1): 앞 단계에 의하여 성립함이 증명되었을 것임. P(n) ... P(n-1) … P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

P(n) 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(k) -> P(k+1) 증명 P(1): 단계 1에 의하여 P(2): 단계 2에서 k에 1을 대입 P(1)->P(2) P(3): 단계 2에서 k에 2를 대입 P(2)->P(3) P(4): 단계 2에서 k에 3을 대입 P(3)->P(4) … P(n-1): 앞 단계에 의하여 성립함이 증명되었을 것임. P(n): 단계 2에서 k에 n-1을 대입 P(n-1)->P(n) ... P(n-1) … P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

… 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. P(n) … P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

… 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 특히 P(k-1)을 “귀납법 가정”이라 한다. 이를 수학적 귀납법이라 한다. P(n) … P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

… 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 단계 1: P(1)이 성립함을 보인다. 단계 2: 임의의 자연수 k에 대하여 P(k)이 성립할 때 P(k+1)이 성립함을 보인다. 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 특히 P(k-1)을 “귀납법 가정”이라 한다. 이를 수학적 귀납법이라 한다. A이상의 모든 정수 n에 대하여 P(n)이 성립함을 보이는 2단계 귀납법 기초: P(a) 귀납법 단계: 임의의 자연수 k>a에 대하여 P(k-1)->P(k) P(n) … P(a+2) P(a+1) 실제로 프로그램에서는 대부분의 경우 a=1이다. P(a) Dept. of Multimedia Engineering, DongEui Univ.

… 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } 증명과정: 귀납법 기초 P(1) 귀납법 단계 P(n-1)->P(n) P(n) … P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

… 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } 증명과정: 귀납법 기초 P(1): rFac(1)은 1!을 계산한다. 귀납법 단계 P(n-1)->P(n) P(n) … P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

… 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } 증명과정: 귀납법 기초 P(1): rFac(1)은 1!을 계산한다. O.K. 귀납법 단계 P(n-1)->P(n) P(n) … P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

… 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } 증명과정: 귀납법 기초 P(1): rFac(1)은 1!을 계산한다. O.K. 귀납법 단계 P(n-1)->P(n): rFac(n-1)이 (n-1)!을 계산한다면, rFac(n)은 n!을 계산한다. P(n) … P(3) P(2) 재귀함수는 수학적 귀납법을 그대로 구현한다. 증명과정과 호출과정을 서로 반대다. 귀납법 기초는 호출을 마무리한다. (매우 중요) P(1) Dept. of Multimedia Engineering, DongEui Univ.

… 모든 자연수 n에 대하여 P(n)이 성립함을 보이는 2단계 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } 증명과정: 귀납법 기초 P(1): rFac(1)은 1!을 계산한다. O.K. 귀납법 단계 P(n-1)->P(n): rFac(n-1)이 (n-1)!을 계산한다면, rFac(n)은 n!을 계산한다. O.K. P(n) … P(3) P(2) 재귀함수는 수학적 귀납법을 그대로 구현한다. 증명과정과 호출과정을 서로 반대다. 귀납법 기초는 호출을 마무리한다. (매우 중요) P(1) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? P(0): rF(0) == 0 일단 생략 P(1): rF(1) == 1 P(2): rF(2) == 1 P(3): rF(3) == 2 … P(n): rF(n) == n번째 피보나치 수 ... 모든 자연수 n에 대하여 P(n)이 성립! >> 수학적 귀납법 오른쪽이 오리지날 버전이지만, 왼쪽으로 대체 >> 이후 원래 버전으로 설명 Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 증명과정: 귀납법 기초 P(1): 귀납법 단계 P(n-1)->P(n): Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 증명과정: 귀납법 기초 P(1): rF(1)은 첫번째 피보나치 수를 계산한다. 귀납법 단계 P(n-1)->P(n): Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 증명과정: 귀납법 기초 P(1): rF(1)은 첫번째 피보나치 수를 계산한다. O.K. 귀납법 단계 P(n-1)->P(n): Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 증명과정: 귀납법 기초 P(1): rF(1)은 첫번째 피보나치 수를 계산한다. O.K. 귀납법 단계 P(n-1)->P(n): rF(n-1)은 (n-1)번째 피보나치 수를 계산한다면, rF(n)은 n번째 피보나치 수를 계산한다. Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 증명과정: 귀납법 기초 P(1): rF(1)은 첫번째 피보나치 수를 계산한다. O.K. 귀납법 단계 P(n-1)->P(n): rF(n-1)은 (n-1)번째 피보나치 수를 계산한다면, rF(n)은 n번째 피보나치 수를 계산한다. Nope! Absolutely Not!! Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 증명과정: 귀납법 기초 P(1): rF(1)은 첫번째 피보나치 수를 계산한다. O.K. 귀납법 단계 P(n-1)->P(n): rF(n-1)은 (n-1)번째 피보나치 수를 계산한다면, rF(n)은 n번째 피보나치 수를 계산한다. Nope! Absolutely Not!! {P(n-1) AND P(n-2)} –> P(n) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) O.K. 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) O.K. 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) O.K. Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 검증해 봅시다! ??? P(1) P(2) P(3) … Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 검증해 봅시다! ??? P(1): 귀납법 기초에서 P(1)이 성립함을 증명. O.K. P(2) P(3) … P(1) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 검증해 봅시다! ??? P(1): 귀납법 기초에서 P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2) P(3) … P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 검증해 봅시다! ??? P(1): 귀납법 기초에서 P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2) Oops!! P(3) … P(2) P(0) P(1) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 검증해 봅시다! ??? P(1): 귀납법 기초에서 P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2) Oops!! P(3) … P(2) P(0) P(1) 도대체 무엇이 문제인가? Dept. of Multimedia Engineering, DongEui Univ.

귀납법 기초는 귀납법 단계의 모든 경우에 결국 종료될 수 있도록 모든 경우를 고려하여 작성되어야 한다. 피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 검증해 봅시다! ??? P(1): 귀납법 기초에서 P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2) Oops!! P(3) … P(2) P(0) P(1) 도대체 무엇이 문제인가? Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초의 점검 P(1): 귀납법 기초에서 P(0), P(1)이 성립함을 증명. O.K. P(2) P(3) … P(1) P(0) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초의 점검 P(1): 귀납법 기초에서 P(0), P(1)이 성립함을 증명. O.K. P(2) P(3) … P(2) P(1) P(0) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초의 점검 P(1): 귀납법 기초에서 P(0), P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2) P(3) … P(2) P(1) P(0) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초의 점검 P(1): 귀납법 기초에서 P(0), P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2). O.K. P(3) … P(2) P(1) P(0) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초의 점검 P(1): 귀납법 기초에서 P(0), P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2). O.K. P(3) … P(3) P(2) P(1) P(0) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초의 점검 P(1): 귀납법 기초에서 P(0), P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2). O.K. P(3): 귀납법 단계에서 k에 3를 대입 {P(2) AND P(1)} -> P(3). … P(3) P(2) P(1) P(0) Dept. of Multimedia Engineering, DongEui Univ.

P(n) 피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초의 점검 P(1): 귀납법 기초에서 P(0), P(1)이 성립함을 증명. O.K. P(2): 귀납법 단계에서 k에 2를 대입 {P(1) AND P(0)} -> P(2). O.K. P(3): 귀납법 단계에서 k에 3를 대입 {P(2) AND P(1)} -> P(3). … … P(3) P(2) P(1) 호출과정은 지난 시간의 내용을 다시 참조 반드시 확인할 것. P(0) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 증명과정: 귀납법 기초 P(1), P(0): rF(1)은 1번째, rF(0)은 0번째 피보나치 수를 계산한다. 귀납법 단계 {P(k-1) AND P(k-2)} -> P(k) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 증명과정: 귀납법 기초 P(1), P(0): rF(1)은 1번째, rF(0)은 0번째 피보나치 수를 계산한다. O.K. 귀납법 단계 {P(k-1) AND P(k-2)} -> P(k) Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 증명과정: 귀납법 기초 P(1), P(0): rF(1)은 1번째, rF(0)은 0번째 피보나치 수를 계산한다. O.K. 귀납법 단계 {P(k-1) AND P(k-2)} -> P(k): rF(k-1)가 (k-1)번째 피보나치 수를 계산하고 rF(k-2)가 (k-2)번째 피보나치 수를 계산한다면, rF(k)은 k번째 피보나치 수를 계산한다. Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 증명과정: 귀납법 기초 P(1), P(0): rF(1)은 1번째, rF(0)은 0번째 피보나치 수를 계산한다. O.K. 귀납법 단계 {P(k-1) AND P(k-2)} -> P(k): rF(k-1)가 (k-1)번째 피보나치 수를 계산하고 rF(k-2)가 (k-2)번째 피보나치 수를 계산한다면, rF(k)은 k번째 피보나치 수를 계산한다. O.K. Dept. of Multimedia Engineering, DongEui Univ.

피보나치 함수의 증명 int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } // 0, 1, 1, 2, 3, 5, 8, 13, 21… 무엇을 증명해야 하는가? 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. 증명과정: 귀납법 기초 P(1), P(0): rF(1)은 1번째, rF(0)은 0번째 피보나치 수를 계산한다. O.K. 귀납법 단계 {P(k-1) AND P(k-2)} -> P(k): rF(k-1)가 (k-1)번째 피보나치 수를 계산하고 rF(k-2)가 (k-2)번째 피보나치 수를 계산한다면, rF(k)은 k번째 피보나치 수를 계산한다. O.K. Dept. of Multimedia Engineering, DongEui Univ.

수학적 귀납법 무엇을 증명해야 하는가? int rFac (int n) { // n>0; int rF(int n) { // n>=0 if (n==1) return 1; if (n<2) return n; // if (n==0||n==1) return n else return n*rFac (n-1); else return rF(n-1)+rF(n-2); } } 계승함수 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 피보나치 함수 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) Dept. of Multimedia Engineering, DongEui Univ.

수학적 귀납법 무엇을 증명해야 하는가? int rFac (int n) { // n>0; int rF(int n) { // n>=0 if (n==1) return 1; if (n<2) return n; // if (n==0||n==1) return n else return n*rFac (n-1); else return rF(n-1)+rF(n-2); } } 계승함수 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. (위의 구조에 대하여 증명되어 있음) 피보나치 함수 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. 재귀식에 따른 귀납법 기초의 설정에 익숙해질 수 있어야 한다. Dept. of Multimedia Engineering, DongEui Univ.

수학적 귀납법 무엇을 증명해야 하는가? int rFac (int n) { // n>0; if (n==1) return 1; else return n*rFac (n-1); } 계승함수 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. 피보나치 함수 귀납법 기초: 귀납법 단계: 재귀식에 따른 귀납법 기초의 설정에 익숙해질 수 있어야 한다. main () rFac() rFac () N=3 N=2 N=1 1 Dept. of Multimedia Engineering, DongEui Univ.

main () rF(3) rF(2) rF(1) rF(0) 2 1 3 수학적 귀납법 무엇을 증명해야 하는가? int rF(int n) { // n>=0 if (n<2) return n; // if (n==0||n==1) return n else return rF(n-1)+rF(n-2); } 계승함수 귀납법 기초: 귀납법 단계: 피보나치 함수 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. 재귀식에 따른 귀납법 기초의 설정에 익숙해질 수 있어야 한다. Dept. of Multimedia Engineering, DongEui Univ.

Strong Mathematical induction
수학적 귀납법 계승함수 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 피보나치 함수 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 확장된 수학적 귀납법 귀납법 단계: 임의의 자연수 k에 대하여 {P(1), P(2), …, P(k-1)} -> P(k) P(1) Dept. of Multimedia Engineering, DongEui Univ.

수학적 귀납법 계승함수 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 피보나치 함수 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 확장된 수학적 귀납법 귀납법 단계: 임의의 자연수 k에 대하여 {P(1), P(2), …, P(k-1)} -> P(k) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

수학적 귀납법 계승함수 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 피보나치 함수 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 확장된 수학적 귀납법 귀납법 단계: 임의의 자연수 k에 대하여 {P(1), P(2), …, P(k-1)} -> P(k) P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

수학적 귀납법 계승함수 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 피보나치 함수 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 확장된 수학적 귀납법 귀납법 단계: 임의의 자연수 k에 대하여 {P(1), P(2), …, P(k-1)} -> P(k) P(4) P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

P(k) 수학적 귀납법 계승함수 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 P(k-1)->P(k) 피보나치 함수 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 확장된 수학적 귀납법 귀납법 단계: 임의의 자연수 k에 대하여 {P(1), P(2), …, P(k-1)} -> P(k) … P(4) P(3) P(2) P(1) Dept. of Multimedia Engineering, DongEui Univ.

최소공배수 함수의 증명 int gcd (int a, int b) { if (b==0) return a; return gcd(b, a%b); } void main ( ) { cout << gcd(3,9); Dept. of Multimedia Engineering, DongEui Univ.

최소공배수 함수의 증명 int gcd (int a, int b) { if (b==0) return a; return gcd(b, a%b); } void main ( ) { cout << gcd(3,9); 무엇을 증명하여야 하는가? 확장된 수학적 귀납법 귀납법 기초: P(1) 귀납법 단계: 임의의 자연수 k에 대하여 {P(1), P(2), …, P(k-1)} -> P(k) Dept. of Multimedia Engineering, DongEui Univ.

최소공배수 함수의 증명 int gcd (int a, int b) { if (b==0) return a; return gcd(b, a%b); } void main ( ) { cout << gcd(3,9); 무엇을 증명하여야 하는가? 확장된 수학적 귀납법 귀납법 기초: P(1) => 임의의 자연수 a에 대하여 P(a,0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(1), P(2), …, P(k-1)} -> P(k) => 임의의 자연수 n과 m에 대하여 {P(a, b): 0<a<=n, 0<=b<=m, 단, 동시에 a=n 이고 b=m은 아니다} -> P(n, m) Dept. of Multimedia Engineering, DongEui Univ.

최소공배수 함수의 증명 int gcd (int a, int b) { if (b==0) return a; return gcd(b, a%b); } void main ( ) { cout << gcd(3,9); 무엇을 증명하여야 하는가? 확장된 수학적 귀납법 귀납법 기초: P(1) => 임의의 자연수 a에 대하여 P(a,0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(1), P(2), …, P(k-1)} -> P(k) => 임의의 자연수 n과 m에 대하여 {P(a, b): 0<a<=n, 0<=b<=m, 단, 동시에 a=n 이고 b=m은 아니다} -> P(n, m) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. Dept. of Multimedia Engineering, DongEui Univ.

You are the one Who makes that happen!!! summaries 수학적 귀납법 계승 함수의 증명
피보나치 함수의 증명 최소공배수 함수의 증명 You are the one Who makes that happen!!! Dept. of Multimedia Engineering, DongEui Univ.

Data structures 02.2:mathematical induction 동의대학교 멀티미디어공학과 이광의 교수.

Similar presentations

Presentation on theme: "Data structures 02.2:mathematical induction 동의대학교 멀티미디어공학과 이광의 교수."— Presentation transcript:

Similar presentations

About project

지원

로그인

Auth with social network:

Data structures 02.2:mathematical induction 동의대학교 멀티미디어공학과 이광의 교수.

Similar presentations

Presentation on theme: "Data structures 02.2:mathematical induction 동의대학교 멀티미디어공학과 이광의 교수."— Presentation transcript:

Similar presentations

About project

지원