Κοινή χρήση τεχνολογίας

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

Η πιο δημοφιλής κατανόηση της αναδρομής είναι μια ακολουθία
Όπως μια γραμμική λίστα σε μια δομή δεδομένων (η οποία μπορεί να είναι μια διαδοχική λίστα ή μια συνδεδεμένη λίστα, συνήθως μια διαδοχική λίστα), η αναδρομή είναι
Μια διαδικασία βρόχου ή επαναληπτικής απαρίθμησης.
Η αναδρομή είναι ουσιαστικά ένα μαθηματικό πρόβλημα, οπότε ορισμένοι μαθητές ρώτησαν αν ο αλγόριθμος απαιτεί καλά μαθηματικά
Αυτά τα μαθηματικά είναι απλά πράγματα που μάθαμε κακώς στο γυμνάσιο και στο γυμνάσιο Έχουμε ήδη περάσει από τις εισαγωγικές εξετάσεις στο κολέγιο, οπότε γιατί να φοβόμαστε αυτά τα πράγματα!

1. Ακολουθία Fibonacci

Η ακολουθία που σχηματίζεται από αριθμούς Fibonacci (συνήθως αντιπροσωπεύεται από F(n)) ονομάζεται ακολουθία Fibonacci.Η ακολουθία ξεκινά με 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. Αυτό συμβαίνει επειδή ο ρυθμός αύξησης των αριθμών Fibonacci είναι πολύ γρήγορος.
Γρήγορα, εκθετικά. Έτσι, εάν το n είναι μεγάλο, θα υπερβεί το εύρος των ακεραίων 32-bit στη γλώσσα C.Αυτή είναι η πιο βασική παράδοση
Σας έχουμε ήδη πει την ερώτηση έκπτωσης και τον τύπο αναδρομής Το μόνο που έχουμε να κάνουμε είναι να χρησιμοποιήσουμε έναν βρόχο για να εφαρμόσουμε αυτήν την αναδρομή.
Χρειάζεται μόνο να χρησιμοποιήσουμε έναν πίνακα 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. Ακολουθία Tabonacci

Η ακολουθία Tabonacci Tn ορίζεται ως εξής:
Τ(0) = 0, Τ(1) = 1, Τ(2)=1
Και υπό την προϋπόθεση n>2, T(n)=T(n-1)+T(n-2)+T(n-3), δίνοντάς σας τον ακέραιο n, παρακαλούμε επιστρέψτε το nο Tabonacci
Η τιμή του αριθμού T(n).
Εάν καταλαβαίνετε ήδη την ακολουθία Fibonacci, τότε αυτό το πρόβλημα δεν είναι δύσκολο, αλλά κατά την προετοιμασία, πρέπει να αρχικοποιήσετε τους τρεις πρώτους αριθμούς.
Και κατά τον υπολογισμό της επανάληψης βρόχου, η τιμή του τρέχοντος αριθμού απαιτεί το σωρευτικό άθροισμα των τιμών των τριών προηγούμενων αριθμών. σαν αυτό:

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. Δισδιάστατο πρόβλημα υποτροπής

Προβλήματα όπως η ακολουθία Fibonacci μπορούν να λυθούν με έναν μονοδιάστατο πίνακα Μερικές φορές, όταν μια διάσταση δεν μπορεί να το λύσει, I
Πρέπει να δούμε το πρόβλημα από μια υψηλότερη διάσταση.

Το μήκος είναι n(1
Αλλά δεν πρέπει να υπάρχουν άλλοι χαρακτήρες) και απαγορεύεται να υπάρχει το Μ δίπλα στο άλλο Πόσα είδη τέτοιων χορδών υπάρχουν;

Σκεφτείτε ότι το μήκος είναι n, και υπάρχουν f[n][0] είδη συμβολοσειρών που τελειώνουν με 'A', f[n][1] είδη συμβολοσειρών που τελειώνουν με 'C' και υπάρχουν f[n][ 1] είδη χορδών που τελειώνουν με ''
f[n][2] είδη

4. Πραγματική μάχη

4.1 Κοντά στους 509 αριθμούς Fibonacci

Αριθμοί Fibonacci(συνήθως χρησιμοποιείταιF(n)αντιπροσωπεύει) καλείται η ακολουθία που σχηματίζεταιΑκολουθία Fibonacci .Αυτή η ακολουθία αποτελείται από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 Λήκου 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 Likou 119 Yang Hui Triangle||

Δεδομένου ενός μη αρνητικού δείκτηrowIndex, επιστροφή στο τρίτο σημείο του "Τρίγωνο Yang Hui"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