Berbagi teknologi

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

Pemahaman yang paling populer tentang rekursi adalah suatu urutan. Hubungan antara rekursi dan suatu urutan seperti hubungan antara algoritma dan struktur data
Seperti daftar linier dalam struktur data (yang dapat berupa daftar berurutan atau daftar tertaut, biasanya daftar berurutan), rekursi adalah
Proses enumerasi yang berulang atau berulang.
Rekursi pada dasarnya adalah masalah matematika, jadi beberapa siswa bertanya apakah algoritma tersebut memerlukan matematika yang baik
Matematika ini hanyalah hal-hal yang kita pelajari dengan buruk di SMP dan SMA. Kita sudah melalui ujian masuk perguruan tinggi, jadi kenapa kita harus takut dengan hal-hal ini!?

1. Deret Fibonacci

Deret yang dibentuk oleh bilangan Fibonacci (biasanya diwakili oleh F(n)) disebut deret Fibonacci.Urutannya dimulai dengan 0 dan 1, diikuti oleh
Tiap angka yang masuk merupakan penjumlahan dari dua angka sebelumnya. Itu adalah:

F(0)=0,F(1)=1
F(n)=F(n -1)+ F(n- 2), dimana n>1, diketahui n(0 ≤n≤ 30), hitunglah F(n)

Setelah mendapatkan pertanyaan ini, mari kita lihat dulu rentang pertanyaannya yang tidak boleh melebihi 30. Itu karena tingkat pertumbuhan angka Fibonacci sangat cepat.
Cepat, secara eksponensial. Jadi jika n besar maka akan melebihi kisaran bilangan bulat 32-bit dalam bahasa C.Ini adalah penyampaian paling dasar
Kami telah memberi tahu Anda pertanyaan deduksi dan rumus rekursi. Yang harus kami lakukan hanyalah menggunakan loop untuk mengimplementasikan rekursi ini.
Kita hanya perlu menggunakan array F[31], menginisialisasi F[0] dan F[1], lalu menghitungnya dalam satu lingkaran sesuai dengan rumus yang diberikan.

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

Deret Tabonacci Tn didefinisikan sebagai berikut:
T(0) = 0, T(1) = 1, T(2) = 1
Dan dengan kondisi n>2, T(n)=T(n-1)+T(n-2)+T(n-3), memberi Anda bilangan bulat n, harap kembalikan Tabonacci ke-n
Nilai bilangan T(n).
Jika anda sudah memahami deret Fibonacci, maka soal ini tidaklah sulit, namun pada saat menginisialisasi, anda perlu menginisialisasi tiga angka pertama.
Dan selama perhitungan iterasi loop, nilai angka saat ini memerlukan jumlah kumulatif dari nilai tiga angka sebelumnya. seperti ini:

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. Masalah perulangan dua dimensi

Permasalahan seperti deret Fibonacci dapat diselesaikan dengan array satu dimensi. Terkadang, ketika satu dimensi tidak dapat menyelesaikannya, I
Kita perlu melihat permasalahan ini dari dimensi yang lebih tinggi.

Panjangnya adalah n(1
Tapi tidak boleh ada karakter lain) dan dilarang ada M yang berdekatan satu sama lain.

Misalkan panjangnya n, dan ada f[n][0] jenis string yang diakhiri dengan 'A', f[n][1] jenis string yang diakhiri dengan 'C', dan ada f[n][ 1] jenis string yang diakhiri dengan ''
f[n][2] spesies

4. Pertarungan sebenarnya

4.1 Mendekati angka Fibonacci 509

Angka Fibonacci(biasanya digunakanF(n)mewakili) barisan yang terbentuk disebutBarisan Fibonacci .Urutan ini terdiri dari0Dan1Awalnya, setiap angka berikutnya merupakan jumlah dari dua angka sebelumnya.

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 Menaiki tangga

Misalkan Anda sedang menaiki tangga.membutuhkannAnda dapat mencapai puncak gedung dengan mengambil langkah.
setiap kali Anda bisa mendaki1atau2 sebuah langkah. Berapa banyak cara berbeda yang dapat Anda lakukan untuk mencapai puncak sebuah gedung?

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

Diberikan indeks non-negatifrowIndex, kembali ke poin ketiga "Segitiga Yang Hui"rowIndexOKE.

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