遞推算法通過(guò)已知的初始條件和遞推關(guān)系，逐步推導(dǎo)出后續(xù)結(jié)果。與遞歸不同，遞推通常使用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)，避免了函數(shù)調(diào)用的開(kāi)銷(xiāo)，效率更高。

本文將用C++語(yǔ)言，通過(guò)幾個(gè)經(jīng)典例題，詳細(xì)講解遞推算法的思想和實(shí)現(xiàn)。

一、遞推算法基本思想

遞推算法的核心是遞推關(guān)系式和初始條件。

遞推關(guān)系式描述了當(dāng)前狀態(tài)如何由前一個(gè)或多個(gè)狀態(tài)推導(dǎo)而來(lái)，而初始條件則是遞推的起點(diǎn)。

在C++中實(shí)現(xiàn)遞推，通常遵循以下步驟：

1. 定義狀態(tài)數(shù)組：使用數(shù)組存儲(chǔ)中間結(jié)果
2. 設(shè)置初始條件：根據(jù)問(wèn)題初始化數(shù)組的前幾項(xiàng)
3. 建立遞推關(guān)系：通過(guò)循環(huán)按照遞推公式計(jì)算后續(xù)項(xiàng)
4. 輸出結(jié)果：返回或輸出目標(biāo)位置的值

遞推與遞歸的主要區(qū)別在于：遞推是自底向上的迭代過(guò)程，而遞歸是自頂向下的函數(shù)調(diào)用過(guò)程。遞推通常更高效，適合處理線性結(jié)構(gòu)問(wèn)題。

二、一維遞推問(wèn)題

1. 斐波那契數(shù)列

問(wèn)題描述：斐波那契數(shù)列的第1項(xiàng)為1，第2項(xiàng)為1，從第3項(xiàng)開(kāi)始，每一項(xiàng)都等于前兩項(xiàng)之和。

遞推關(guān)系：f[i] = f[i-1] + f[i-2] 初始條件：f[1] = 1, f[2] = 1

C++代碼實(shí)現(xiàn)：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 定義數(shù)組存儲(chǔ)斐波那契數(shù)，假設(shè)n不超過(guò)45（保證在int范圍內(nèi)）
    int f[46];  // 第45項(xiàng)約為1.13e9，仍在int范圍內(nèi)
    
    // 初始化初始條件
    f[1] = 1;
    f[2] = 1;
    
    // 遞推計(jì)算
    for (int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    
    cout << f[n] << endl;
    return 0;
}

代碼解析：

• 數(shù)組f存儲(chǔ)已計(jì)算的結(jié)果，避免重復(fù)計(jì)算
• 循環(huán)從3開(kāi)始，依次計(jì)算每一項(xiàng)
• 當(dāng)n≤45時(shí)，結(jié)果在int范圍內(nèi)（約21億內(nèi)）

2. 爬樓梯問(wèn)題

問(wèn)題描述：有n階樓梯，每次可以爬1階或2階，問(wèn)有多少種不同的爬法。

遞推分析：設(shè)a[i]表示爬到第i階樓梯的方法數(shù)。由于每次只能爬1階或2階，所以到達(dá)第i階只能從第i-1階爬1階，或從第i-2階爬2階。

遞推關(guān)系：a[i] = a[i-1] + a[i-2] 初始條件：a[1] = 1（爬1階只有1種方法），a[2] = 2（爬2階有2種方法）

C++代碼實(shí)現(xiàn)：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int a[46];  // 假設(shè)n不超過(guò)45
    a[1] = 1;
    a[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        a[i] = a[i-1] + a[i-2];
    }
    
    cout << a[n] << endl;
    return 0;
}

代碼解析：

• 這個(gè)問(wèn)題實(shí)質(zhì)上是斐波那契數(shù)列的變體，只是初始條件不同

三、二維遞推問(wèn)題

1. 無(wú)障礙網(wǎng)格路徑計(jì)數(shù)

問(wèn)題描述：在一個(gè)m×n的網(wǎng)格中，從左上角(1,1)出發(fā)，每次只能向右或向下移動(dòng)一步，要到達(dá)右下角(m,n)，問(wèn)有多少條不同的路徑。

遞推分析：設(shè)b[i][j]表示從起點(diǎn)到達(dá)坐標(biāo)(i,j)的路徑數(shù)。由于只能向右或向下移動(dòng)，要到達(dá)(i,j)，只能從上方(i-1,j)或左方(i,j-1)過(guò)來(lái)。

遞推關(guān)系：b[i][j] = b[i-1][j] + b[i][j-1] 邊界條件：第一行和第一列的所有位置都只有1條路徑

C++代碼實(shí)現(xiàn)：

#include <iostream>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    
    // 使用二維數(shù)組，假設(shè)m和n不超過(guò)20
    int b[21] = {0};
    
    // 初始化第一行和第一列
    b[1][1] = 1;
    
    // 遞推計(jì)算
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1) continue; // (1,1)點(diǎn)是初始化條件不用遞推
            b[i][j] = b[i-1][j] + b[i][j-1];
        }
    }
    
    cout << b[m][n] << endl;
    return 0;
}

代碼解析：

• 數(shù)組b[i][j]表示到達(dá)(i,j)的路徑數(shù)
• 初始化第一行和第一列為1，因?yàn)檠刂吘€只有一條路徑
• 雙重循環(huán)從(2,2)開(kāi)始遞推計(jì)算

2. 有障礙網(wǎng)格路徑計(jì)數(shù)

路徑計(jì)數(shù)2（洛谷P1176）

問(wèn)題描述：一個(gè) N×N 的網(wǎng)格，你一開(kāi)始在 (1,1)，即左上角。每次只能移動(dòng)到下方相鄰的格子或者右方相鄰的格子，問(wèn)到達(dá) (N,N)，即右下角有多少種方法。

但是這個(gè)問(wèn)題太簡(jiǎn)單了，所以現(xiàn)在有 M 個(gè)格子上有障礙，即不能走到這 M 個(gè)格子上。

遞推分析：遞推關(guān)系與無(wú)障礙情況類(lèi)似，但需要額外考慮障礙物：

1. 如果(i,j)是障礙物，則b[i][j] = true
2. 否則，a[i][j] =a[i-1][j] + a[i][j-1]

C++代碼實(shí)現(xiàn)：

#include <iostream>
using namespace std;

const int MOD = 100003; // 定義模數(shù)常量，避免魔法數(shù)字
int a[1001][1001] = {0}; // 顯式初始化為0
bool b[1001][1001] = {false}; // 顯式初始化為false

int main() {
    int n, m;
    cin >> n >> m;

    // 讀入障礙物
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        b[x][y] = true;
    }

    // 初始化起點(diǎn)
    a[1][1] = 1;

    // 遞推
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 跳過(guò)起點(diǎn)和障礙物
            if (i == 1 && j == 1) continue;
            if (b[i][j]) continue;
            a[i][j] = (a[i-1][j] + a[i][j-1]) % MOD;
        }
    }

    cout << a[n][n] << endl;
    return 0;
}

四、馬走日（過(guò)河卒）問(wèn)題

問(wèn)題描述：棋盤(pán)上有一個(gè)卒需要從A點(diǎn)(1,1)走到B點(diǎn)(n,m)，卒只能向右或向下移動(dòng)。棋盤(pán)上有一個(gè)馬，馬走"日"字，馬所在位置及其控制點(diǎn)（馬能走到的8個(gè)位置）卒不能通過(guò)。

遞推分析：這是網(wǎng)格路徑計(jì)數(shù)問(wèn)題的變體，增加了障礙點(diǎn)（馬的控制點(diǎn)）。設(shè)b[i][j]表示卒從起點(diǎn)到達(dá)(i,j)的路徑數(shù)，stop[i][j]表示(i,j)是否為障礙點(diǎn)。

遞推關(guān)系與有障礙網(wǎng)格類(lèi)似：

1. 如果(i,j)是障礙點(diǎn)，則b[i][j] = 0
2. 否則，b[i][j] = b[i-1][j] + b[i][j-1]

C++代碼實(shí)現(xiàn)：

#include<bits/stdc++.h>
using namespace std;
// 定義 long long 類(lèi)型別名，用于存儲(chǔ)可能的大數(shù)結(jié)果
#define ll long long

// 馬的控制點(diǎn)方向數(shù)組：包括馬本身及其8個(gè)走日位置，共9個(gè)方向
// dx和dy分別對(duì)應(yīng)行和列的變化量，其中(0,0)表示馬自身位置
int dx[] = {-2, -2, -1, -1, 0,  1,  1,  2, 2};
int dy[] = {-1,  1, -2,  2, 0, -2,  2, -1, 1};

// 標(biāo)記數(shù)組：s[i][j]=true表示(i,j)是障礙點(diǎn)（馬的控制點(diǎn)）
bool s[40];
// 動(dòng)態(tài)規(guī)劃數(shù)組：ans[i][j]表示從起點(diǎn)到達(dá)(i,j)的路徑數(shù)
ll ans[40];

// 變量定義：bx,by為目標(biāo)點(diǎn)坐標(biāo)，mx,my為馬的位置坐標(biāo)
int bx, by, mx, my;

int main() {
	// 讀入目標(biāo)點(diǎn)坐標(biāo)和馬的位置坐標(biāo)（原始坐標(biāo)從(0,0)開(kāi)始）
	cin >> bx >> by >> mx >> my;
	
	// 所有坐標(biāo)加2：偏移操作，防止后續(xù)計(jì)算馬的控制點(diǎn)時(shí)數(shù)組越界
	// 這樣棋盤(pán)有效坐標(biāo)從(2,2)開(kāi)始，對(duì)應(yīng)原坐標(biāo)(0,0)
	bx+=2, by+=2, mx+=2, my+=2;
	
	// 標(biāo)記馬的控制點(diǎn)為障礙（包括馬自身）
	// dx和dy數(shù)組長(zhǎng)度為9，索引0~8
	for (int i = 0; i < 9; i++) {
		s[mx+dx[i]][my+dy[i]] = true;
	}
	
	// 遞推初始化：起點(diǎn)(2,2)的路徑數(shù)為1
	ans[2][2] = 1;
	
	// 遞推：遍歷從起點(diǎn)到目標(biāo)點(diǎn)的所有位置
	for (int i = 2; i <= bx; i++) {
		for (int j = 2; j <= by; j++) {
			// 如果當(dāng)前位置是障礙點(diǎn)或是起點(diǎn)，則跳過(guò)（起點(diǎn)已初始化）
			if (s[i][j] || i==2&&j==2) continue;
			
			// 狀態(tài)轉(zhuǎn)移方程：到達(dá)(i,j)的路徑數(shù)等于從左邊(i,j-1)和從上方(i-1,j)的路徑數(shù)之和
			// 由于卒只能向右或向下移動(dòng)，因此只需考慮這兩個(gè)方向
			ans[i][j] = ans[i][j-1] + ans[i-1][j];
		}
	}
	
	// 輸出結(jié)果：到達(dá)目標(biāo)點(diǎn)(bx,by)的路徑數(shù)
	cout << ans[bx][by];
	return 0;
}

五、遞推算法的核心要點(diǎn)

1. 確定遞推狀態(tài)

遞推狀態(tài)是問(wèn)題的關(guān)鍵，通常用一個(gè)或多個(gè)變量表示問(wèn)題的某個(gè)狀態(tài)。例如：

• 爬樓梯問(wèn)題：a[i]表示到達(dá)第i階的方法數(shù)
• 網(wǎng)格路徑問(wèn)題：b[i][j]表示到達(dá)(i,j)的路徑數(shù)

狀態(tài)的定義需要能夠完整描述問(wèn)題的當(dāng)前情況，并且能夠通過(guò)遞推關(guān)系轉(zhuǎn)移到其他狀態(tài)。

2. 建立遞推關(guān)系

遞推關(guān)系描述了狀態(tài)之間的轉(zhuǎn)移方式，通常基于問(wèn)題的限制條件。

例如：

• 爬樓梯：一次只能爬1或2階 → a[i] = a[i-1] + a[i-2]
• 網(wǎng)格路徑：只能向右或向下 → b[i][j] = b[i-1][j] + b[i][j-1]

3. 設(shè)置初始條件

初始條件是遞推的起點(diǎn)，必須明確給出。例如：

• 爬樓梯：a[1] = 1, a[2] = 2
• 網(wǎng)格路徑：第一行和第一列都為1（無(wú)障礙時(shí)）

4. 處理邊界情況

邊界情況需要特別小心，例如數(shù)組越界、障礙物檢查等。在編寫(xiě)代碼時(shí)，要確保所有邊界情況都被正確處理。

六、常見(jiàn)錯(cuò)誤與調(diào)試技巧

1. 數(shù)組越界

這是遞推算法中最常見(jiàn)的錯(cuò)誤。要確保數(shù)組下標(biāo)在有效范圍內(nèi)，特別是當(dāng)訪問(wèn)a[i-1]、b[i-1][j]等時(shí)，要檢查i>1的條件。

2. 初始條件錯(cuò)誤

遞推的初始條件必須正確設(shè)置，否則整個(gè)遞推過(guò)程都會(huì)出錯(cuò)。要仔細(xì)分析問(wèn)題的起點(diǎn)狀態(tài)。

3. 遞推關(guān)系錯(cuò)誤

遞推關(guān)系必須正確反映狀態(tài)之間的轉(zhuǎn)移規(guī)律?？梢酝ㄟ^(guò)手工計(jì)算小規(guī)模樣例來(lái)驗(yàn)證遞推關(guān)系的正確性。

4. 數(shù)據(jù)類(lèi)型選擇

雖然用戶要求使用int類(lèi)型，但要確保計(jì)算結(jié)果不會(huì)溢出。對(duì)于可能的大數(shù)據(jù)，需要考慮使用更大的數(shù)據(jù)類(lèi)型。

總結(jié)

遞推算法通過(guò)已知條件和遞推關(guān)系，逐步推導(dǎo)出問(wèn)題的解。在C++中實(shí)現(xiàn)遞推算法，關(guān)鍵是正確定義狀態(tài)、建立遞推關(guān)系、設(shè)置初始條件。通過(guò)本文的四個(gè)例題，我們可以看到遞推算法在解決序列問(wèn)題和網(wǎng)格路徑問(wèn)題中的應(yīng)用。

對(duì)于初學(xué)者來(lái)說(shuō)，理解遞推思想比掌握高級(jí)數(shù)據(jù)結(jié)構(gòu)更重要。通過(guò)大量練習(xí)，可以培養(yǎng)將實(shí)際問(wèn)題轉(zhuǎn)化為遞推模型的能力，這是算法學(xué)習(xí)的重要基礎(chǔ)。遞推算法不僅是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，也是許多復(fù)雜算法的核心思想。

在實(shí)際編程中，要注意邊界條件的處理、數(shù)組下標(biāo)的范圍檢查，以及遞推關(guān)系的正確性驗(yàn)證。通過(guò)不斷練習(xí)和調(diào)試，可以逐漸掌握遞推算法的精髓，為解決更復(fù)雜的算法問(wèn)題打下堅(jiān)實(shí)基礎(chǔ)。

到此這篇關(guān)于C++遞推算法的具體使用的文章就介紹到這了,更多相關(guān)C++遞推算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論