Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Das beliebteste Verständnis von Rekursion ist eine Sequenz. Die Beziehung zwischen einer Rekursion und einer Sequenz ähnelt der Beziehung zwischen einem Algorithmus und einer Datenstruktur
Rekursion ist wie eine lineare Liste in einer Datenstruktur (die eine sequentielle Liste oder eine verknüpfte Liste sein kann, normalerweise eine sequentielle Liste).
Eine Schleife oder ein iterativer Aufzählungsprozess.
Rekursion ist im Wesentlichen ein mathematisches Problem, daher fragten einige Schüler, ob der Algorithmus gute Mathematik erfordert. Das stimmt nicht
Diese Mathematik sind nur Dinge, die wir in der Mittel- und Oberschule schlecht gelernt haben. Wir haben die Aufnahmeprüfung für das College bereits bestanden, warum sollten wir uns also vor diesen Dingen fürchten?

1. Fibonacci-Folge

Die aus Fibonacci-Zahlen (normalerweise dargestellt durch F(n)) gebildete Folge wird Fibonacci-Folge genannt.Die Sequenz beginnt mit 0 und 1, gefolgt von
Jede Zahl in ist die Summe der beiden vorherigen Zahlen. Das ist:

F(0)=0，F(1)=1
F(n)=F(n -1)+ F(n- 2), wobei n>1, gegeben n(0 ≤n≤ 30), bitte berechnen Sie F(n)

Nachdem wir diese Frage beantwortet haben, schauen wir uns zunächst den Bereich der Frage an, der 30 nicht überschreiten sollte. Das liegt daran, dass die Wachstumsrate der Fibonacci-Zahlen sehr schnell ist.
Schnell, exponentiell. Wenn n also groß ist, überschreitet es den Bereich der 32-Bit-Ganzzahlen in der C-Sprache.Dies ist die einfachste Lieferung
Die Deduktionsfrage und die Rekursionsformel haben wir Ihnen bereits erklärt. Wir müssen lediglich eine Schleife verwenden, um diese Rekursion zu implementieren.
Wir müssen nur ein F[31]-Array verwenden, F[0] und F[1] initialisieren und es dann in einer Schleife gemäß der angegebenen Formel berechnen.

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. Tabonacci-Folge

Die Tabonacci-Folge Tn ist wie folgt definiert:
T(0) = 0, T(1) = 1,T(2)=1
Und unter der Bedingung n>2, T(n)=T(n-1)+T(n-2)+T(n-3), was Ihnen die ganze Zahl n ergibt, geben Sie bitte den n-ten Tabonacci zurück
Der Wert der Zahl T(n).
Wenn Sie die Fibonacci-Folge bereits verstehen, ist dieses Problem nicht schwierig, aber beim Initialisieren müssen Sie die ersten drei Zahlen initialisieren.
Und während der Schleifeniterationsberechnung erfordert der Wert der aktuellen Zahl die kumulative Summe der Werte der vorherigen drei Zahlen. so was:

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. Zweidimensionales Wiederholungsproblem

Probleme wie die Fibonacci-Folge können mit einem eindimensionalen Array gelöst werden. Manchmal, wenn eine Dimension es nicht lösen kann, I
Wir müssen das Problem aus einer höheren Dimension betrachten.

Die Länge beträgt n(1
Es dürfen jedoch keine anderen Zeichen vorhanden sein und es ist verboten, M nebeneinander zu haben. Wie viele Arten solcher Zeichenfolgen gibt es?

Bedenken Sie, dass die Länge n ist und es f[n][0] Arten von Zeichenfolgen gibt, die mit „A“ enden, f[n][1] Arten von Zeichenfolgen, die mit „C“ enden, und es gibt f[n][ 1] Arten von Zeichenfolgen, die mit '' enden
f[n][2] Arten

4. Tatsächlicher Kampf

4.1 Nahezu 509 Fibonacci-Zahlen

Fibonacci-Zahlen(normalerweise verwendetF(n)darstellt) wird die gebildete Folge aufgerufenFibonacci-Folge .Diese Sequenz besteht aus0Und1Zunächst ist jede weitere Zahl die Summe der beiden vorherigen Zahlen.

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 Treppensteigen

Angenommen, Sie steigen Treppen.brauchennSie können die Spitze des Gebäudes über Treppen erreichen.
Jedes Mal, wenn du klettern kannst1oder2 ein Schritt. Auf wie viele verschiedene Arten kann man auf die Spitze eines Gebäudes klettern?

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 Likou 119 Yang Hui Dreieck||

Gegeben sei ein nicht negativer IndexrowIndex, kehren Sie zum dritten Punkt des „Yang-Hui-Dreiecks“ zurückrowIndexOK.

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