프로그래머의 수학 - 귀납과 귀속

《프로그래머의 수학》 독서 노트 목록

0의 역할

로마 계수법

여수의 운용

논리 연산

정렬 조합

귀납과 귀속

귀납

induction:귀납

단계

기저(base)-증명P(0)성립

귀납(induction)-가설P(k)성립은 P(k+1)성립을 증명하고 그 중에서 k는 0보다 적지 않은 정수

순환 불변식

귀속

GNU is short for "GNU is Not UNIX"

귀착되는 사고방식을 발견하다.

n층의 전체 문제에서 일부 문제를 은폐하여 나머지 부분이 n-1층의 문제인지 아닌지를 판단하다

추이 공식과 해석식

추이 공식: 자신을 이용하여 자신을 추론하는 등식 해석식: 변수 n만 사용하여 자신의 등식을 프로그래밍할 수 있고 해석식을 사용할 수 있으며 가능한 해석식을 사용할 수 있다. 프로그램의 귀속 함수는 창고 공간을 많이 소모하고 호출 횟수가 방대하며 CPU를 소모한다. 피보나치 수열의 예를 보십시오.

한노타

점진식

$$ H(n)=\left{\begin{aligned} & 0 & n = 0\& H(n-1) + 1 + H(n-1) & n > 0\end{aligned}\right. $$

해석식

$$ H(n) = 2^n - 1 $$

데모 코드

#include 
#include 

void hanoi(int n, char x, char y, char z);

void hanoi(int n, char x, char y, char z) {
    if (0 == n) {
        // do nothing
    } else {
        hanoi(n - 1, x, z, y);
        printf("%c --> %c, ", x, y);
        hanoi(n - 1, z, y, x);
    }
}

int main(void) {
    hanoi(6, 'A', 'B', 'C');
}

단계 곱하기

점차적 공식

$$ n!=\left{\begin{aligned} & 1 & n = 0\& n × (n-1)! & n > 0\end{aligned}\right. $$

구화 공식

점차적 공식

$$ SUM(n)=\left{\begin{aligned} & 0 & n = 0\& n + SUM(n - 1) & n > 0\end{aligned}\right. $$

해석식

$$ SUM(n) =\dfrac{n × (n + 1)}{2} $$

피보나 절수열

$$ F(n)=\left{\begin{aligned} & 0 & n = 0\& 1 & n = 1\& F(n - 1) + F(n - 2) & n > 1\end{aligned}\right. $$

피보나치 수열의 코드 구현

차례로 실현되다
추이 공식에 따르다

/**
 *     
 *
 * @param n  n Fibonacci ， 0  
 */
public static long fibonacciRecursively(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacciRecursively(n - 1) + fibonacciRecursively(n - 2);
    }
}

최적화 1

/**
 *    ：        
 *
 * @param n  n Fibonacci ， 0  
 */
public static long fibonacciRecursivelyWithLoop(int n) {
    if (n <= 1) {
        return n;
    } else {
        long result = 1;
        do {
            result += fibonacciRecursivelyWithLoop(n - 2);
            n--;
        } while(n > 1);
        return result;
    }
}

최적화 2

/**
 *    ：    
 *
 * @param n  n Fibonacci ， 0  
 */
public static long fibonacciIteratively(int n) {
    if (n <= 1) {
        return n;
    } else {
        long a = 0, b = 1;
        do {
            long tmp = b;
            b += a;
            a = tmp;
        } while(--n > 1);
        return b;
    }
}

최적화

/**
 *    ：    ，        ，        
 *
 * @param n  n Fibonacci ， 0  
 */
public static long fibonacciIterativelyFaster(int n) {
    if (n <= 1) {
        return n;
    } else {
        long a, b = 1;
        n--;
        a = n & 1;
        n /= 2;
        while(n-- > 0) {
            a += b;
            b += a;
        }
        return b;
    }
}

파스칼 삼각형(Pascal's Triangle)

조합수의 귀속 정의

$$ C^K_N=\left {\begin {aligned} & 1 & N = 0 또는 N = K\& C^ {K - 1} {N - 1} + C^K {N - 1} & K > 0 및 K < N\end {aligned}\right. $$

조합수의 수리적 의미

N개의 다른 원소, 그 중 하나의 원소 a. N에서 K개의 원소를 선택한 조합수는 a를 포함하는 조합수와 a를 포함하지 않는 조합수의 합과 같다.

반복 그래프 - 분형(fractale)

두 갈래 나무

바다거북이가 그림을 그리다.

forward(n)//앞으로 n보 병선

backward(n)//뒷다리 n보에 선을 긋지 않음

left()//시계 반대 방향으로 일정 각도 회전

right()//시계 방향으로 일정 각도 회전

셀핀스키 삼각형(sierpinski triangle)

파스카 삼각형의 짝수를 색깔로 구분하여 셀핀스키 삼각형을 얻다

귀속과 귀납의 대비 (recursion and induction)

귀납과 귀납은 방향이 다르기 때문에 일반적인 전제에서 개별적인 결론을 내놓는 것은 귀납 사상이고 개별적인 전제에서 일반적인 결론을 내놓는 것은 귀납 사상이다.

데모 코드

//   
void prove(int n) {
    int k;
    // step 1 start
    k = 0;
    printf("P(%d)  
", k);
    // step 1 end
    while (k < n) {
        // step 2 start
        printf("P(%d)  ， P(%d)   
", k, k + 1);
        // step 2 end
        k++;
    }
    printf("    ");
}

//   
void prove(int n) {
    if (0 == n) {
        printf("  1 --> P(%d)  。
", n);
    } else {
        prove(n - 1);
        printf("  2 -->  P(%d)  ， P(%d)   。
", n - 1, n);
        printf("  ，P(%d)  。
", n);
    }
}