Teknologian jakaminen

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

Suosituin käsitys rekursiosta on sekvenssi. Rekursion ja sekvenssin välinen suhde on kuin algoritmin ja tietorakenteen välinen suhde
Kuten lineaarinen lista tietorakenteessa (joka voi olla peräkkäinen luettelo tai linkitetty luettelo, yleensä peräkkäinen luettelo), rekursio on
Silmukka tai iteratiivinen luettelointiprosessi.
Rekursio on pohjimmiltaan matemaattinen ongelma, joten jotkut opiskelijat kysyivät, vaatiiko algoritmi hyvää matematiikkaa. Se ei ole totta
Nämä matematiikka ovat vain asioita, joita opimme huonosti yläasteella ja lukiossa. Olemme jo käyneet läpi korkeakoulun pääsykokeet, joten miksi meidän pitäisi pelätä näitä asioita!?

1. Fibonacci-sekvenssi

Fibonacci-lukujonoa (jota yleensä edustaa F(n)) kutsutaan Fibonacci-sekvenssiksi.Sarja alkaa 0:lla ja 1:llä, jota seuraa
Jokainen luku on kahden edellisen luvun summa. Tuo on:

F(0)=0，F(1)=1
F(n)=F(n-1)+ F(n-2), missä n>1, kun n(0 ≤n≤ 30), laske F(n)

Kun olet saanut tämän kysymyksen, katsotaan ensin kysymyksen aluetta, joka ei saa ylittää 30:tä Tämä johtuu siitä, että Fibonacci-lukujen kasvunopeus on erittäin nopea.
Nopeasti, eksponentiaalisesti. Joten jos n on suuri, se ylittää C-kielen 32-bittisten kokonaislukujen alueen.Tämä on yksinkertaisin toimitus
Olemme jo kertoneet sinulle päättelykysymyksen ja rekursiokaavan. Meidän tarvitsee vain käyttää silmukkaa toteuttamaan tämä rekursio.
Meidän tarvitsee vain käyttää F[31]-taulukkoa, alustaa F[0] ja F[1] ja sitten laskea se silmukassa annetun kaavan mukaan.

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. Tibernacci-sekvenssi

Tabonaccin sekvenssi Tn määritellään seuraavasti:
T(0) = 0, T(1) = 1, T(2) = 1
Ja ehdolla n>2, T(n)=T(n-1)+T(n-2)+T(n-3), jolloin saat kokonaisluvun n, palauta n:s Tabonacci
Numeron T(n) arvo.
Jos ymmärrät jo Fibonacci-sekvenssin, tämä ongelma ei ole vaikea, mutta alustuksen aikana sinun on alustettava kolme ensimmäistä numeroa.
Ja silmukan iteroinnin aikana nykyisen luvun arvo vaatii kolmen edellisen luvun arvojen kumulatiivisen summan. kuten tämä:

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. Kaksiulotteinen rekursiotehtävä

Fibonacci-sekvenssin kaltaiset ongelmat voidaan ratkaista yksiulotteisella taulukolla. Joskus, kun yksi ulottuvuus ei pysty ratkaisemaan sitä, I
Meidän on tarkasteltava ongelmaa korkeammasta ulottuvuudesta.

Pituus on n(1
Mutta muita merkkejä ei saa olla) ja on kiellettyä olla M vierekkäin Kuinka monta tyyppiä tällaisia ​​merkkijonoja on?

Oletetaan, että pituus on n, ja on f[n][0] tyyppistä merkkijonoa, joka päättyy 'A', f[n][1] tyyppistä merkkijonoa, joka päättyy 'C', ja on f[n][ 1] merkkijonoja, jotka päättyvät ''
f[n][2] lajia

4. Todellinen taistelu

4.1 Lähes 509 Fibonacci-numeroa

Fibonaccin numerot(yleensä käytettyF(n)edustaa) muodostettua sekvenssiä kutsutaanFibonaccin sekvenssi .Tämä sekvenssi koostuu0ja1Aluksi jokainen seuraava luku on kahden edellisen luvun summa.

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 Kiipeilyportaat

Oletetaan, että kiipeät portaita.tarvenPääset rakennuksen huipulle portaita ottamalla.
aina kun voit kiivetä1tai2 askel. Kuinka monella eri tavalla voit kiivetä rakennuksen huipulle?

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 -kolmio||

Annettu ei-negatiivinen indeksirowIndex, palaa "Yang Huin kolmion" kolmanteen pisteeseenrowIndexOK.

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