재귀(C 언어)_developdoc

재귀(C 언어)

2024-07-12

기사 디렉토리

1. 피보나치 수열
2. 타보나치 시퀀스
3. 2차원 재발 문제
4. 실제 전투

재귀에 대한 가장 대중적인 이해는 시퀀스입니다. 재귀와 시퀀스 사이의 관계는 알고리즘과 데이터 구조 사이의 관계와 같습니다.
데이터 구조의 선형 목록(순차 목록 또는 연결 목록, 일반적으로 순차 목록)과 마찬가지로 재귀는 다음과 같습니다.
루프 또는 반복적인 열거 프로세스입니다.
재귀는 본질적으로 수학적 문제이기 때문에 일부 학생들은 알고리즘에 좋은 수학이 필요한지 물었습니다. 이는 사실이 아닙니다.
이런 수학은 우리가 중학교, 고등학교 때 잘 못 배운 것들일 뿐입니다. 우리는 이미 대학 입시를 치렀는데 왜 이런 것들을 두려워해야 합니까!?

1. 피보나치 수열

피보나치 수열(보통 F(n)으로 표시)을 피보나치 수열이라고 합니다.시퀀스는 0과 1로 시작하여 다음으로 이어집니다.
의 각 숫자는 이전 두 숫자의 합입니다. 그건:

F(0)=0，F(1)=1
F(n)=F(n -1)+ F(n- 2), 여기서 n>1이고 n(0 ≤n≤ 30)이 주어지면 F(n)을 계산하십시오.

이 질문을 받은 후 먼저 질문의 범위를 살펴보겠습니다. 최대 30을 넘지 않아야 합니다. 왜냐하면 피보나치 수의 증가 속도가 매우 빠르기 때문입니다.
기하급수적으로 빠릅니다. 따라서 n이 크면 C 언어의 32비트 정수 범위를 초과하게 됩니다.가장 기본적인 배송입니다
우리는 이미 추론 질문과 재귀 공식에 대해 설명했습니다. 우리가 해야 할 일은 루프를 사용하여 이 재귀를 구현하는 것뿐입니다.
F[31] 배열을 사용하고 F[0]과 F[1]을 초기화한 다음 주어진 공식에 따라 루프에서 계산하면 됩니다.

int febonacci(int n) {  
    int F[30] = {0,1};  
    for (int i = 2; i < 30; i++) {  
        F[i] = F[i - 1] + F[i - 2];  
    }  
    return F[29]  
}
1
2
3
4
5
6
7

2. 타보나치 시퀀스

타보나치 수열 Tn은 다음과 같이 정의됩니다.
T(0) = 0, T(1) = 1,T(2)=1
그리고 n>2의 조건에서 T(n)=T(n-1)+T(n-2)+T(n-3), 정수 n을 제공하면 n번째 Tabonacci를 반환하십시오.
숫자 T(n)의 값입니다.
이미 피보나치 수열을 이해했다면 이 문제는 어렵지 않으나 초기화할 때 처음 세 숫자를 초기화해야 합니다.
그리고 루프 반복 계산 중에 현재 숫자의 값은 이전 세 숫자 값의 누적 합계가 필요합니다. 이와 같이:

int tribonacci(int n) {  
    int F[30] = {0,1,1};  
    for (int i = 3; i < 30; i++) {  
        F[i] = F[i - 1] = F[i - 2] + F[i - 3];  
    }  
    return F[29];  
}
1
2
3
4
5
6
7

3. 2차원 재발 문제

피보나치 수열과 같은 문제는 1차원 배열로 풀 수 있는 경우가 있는데, 때로는 한 차원이 풀리지 않을 때도 있습니다.
우리는 더 높은 차원에서 문제를 바라볼 필요가 있습니다.

길이는 n(1
단, 다른 문자는 없어야 하며, M이 서로 인접하는 것은 금지되어 있습니다. 이러한 문자열은 몇 가지입니까?

길이가 n이고, 'A'로 끝나는 f[n][0] 종류의 문자열, 'C'로 끝나는 f[n][1] 종류의 문자열, 그리고 f[n][가 있다고 생각해보세요. 1] ''로 끝나는 문자열 종류
f[n][2] 종

4. 실제 전투

4.1 509개의 피보나치 수열에 가깝습니다.

피보나치 수열(보통 사용되는F(n)나타냄) 형성된 시퀀스를피보나치 수열 .이 시퀀스는 다음과 같이 구성됩니다.0그리고1처음에 각 후속 숫자는 이전 두 숫자의 합입니다.

int fib(int n){
    if(n == 0){
       return 0;

    }
    else if (n == 1){
        return 1;

    }
    return fib(n - 1) + fib(n - 2);
}
1
2
3
4
5
6
7
8
9
10
11

4.2 Likou 70 계단 오르기

당신이 계단을 오르고 있다고 가정해보자.필요n계단을 이용하면 건물 꼭대기까지 올라갈 수 있습니다.
올라갈 수 있을 때마다1또는2 걸음. 건물 꼭대기까지 올라갈 수 있는 다양한 방법이 있나요?

int climbStairs(int n) {  
    int f[46];  
    f[0] = 1;  
    f[1] = 1;  
    for(int i = 2; i <= n; i++){  
        f[i] = f[i - 1] + f[i - 2];  
    }  
    return f[n];  
}
1
2
3
4
5
6
7
8
9

4.3 리커우 119 양휘 트라이앵글||

음수가 아닌 인덱스가 주어지면rowIndex, "양희삼각형"의 세 번째 지점으로 복귀rowIndex좋아요.

int* getRow(int rowIndex, int* returnSize) {  
    int f[34][34];  
    for(int i = 0; i <= rowIndex; i++){  
        for(int j = 0; j <= i; j++){  
            if(j ==0 || j == i){  
                f[i][j] = 1;  
            }  
            else {  
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1];   
            }  
        }  
    }  
    int* ret = (int *)malloc (sizeof(int) * (rowIndex + 1));  
    for(int j = 0; j <= rowIndex; j++){  
        ret[j] = f[rowIndex][j];  
    }  
    *returnSize = rowIndex + 1;  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

기술나눔