😀前言
遞推算法在計算機(jī)科學(xué)中扮演著重要的角色。通過遞推，我們可以根據(jù)已知的初始條件，通過一定的規(guī)則推導(dǎo)出后續(xù)的結(jié)果，從而解決各種實際問題。本文將介紹遞推算法的基礎(chǔ)知識，并通過一些入門例題來幫助讀者更好地理解和掌握遞推算法的應(yīng)用。

🏠個人主頁：塵覺主頁

算法基礎(chǔ)

遞推

入門例題

斐波那契數(shù)列

輸入一個整數(shù) n ，求斐波那契數(shù)列的第 n 項。

假定從 0 開始，第 0 項為 0。

數(shù)據(jù)范圍
0≤n≤39
樣例
輸入整數(shù) n=5

返回 5

題解

該題十分基礎(chǔ)，我們要理解斐波那契數(shù)列的組成，數(shù)列中從每一項都是前兩項的和，所以如果不要求存下一些數(shù)的數(shù)值，我們就可以直接使用，幾個變量操作不用進(jìn)行數(shù)組創(chuàng)建。

class Solution {
public:int Fibonacci(int n) {if(n<=1)return n;if(n==2) return 1;int a=1,b=1;int t;for(int i=3;i<=n;i++){t=a+b;a=b;b=t;}return t;}
};

費解的開關(guān)

你玩過“拉燈”游戲嗎？

25 盞燈排成一個 5×5 的方形。

每一個燈都有一個開關(guān)，游戲者可以改變它的狀態(tài)。

每一步，游戲者可以改變某一個燈的狀態(tài)。

游戲者改變一個燈的狀態(tài)會產(chǎn)生連鎖反應(yīng)：和這個燈上下左右相鄰的燈也要相應(yīng)地改變其狀態(tài)。

我們用數(shù)字 1 表示一盞開著的燈，用數(shù)字 0 表示關(guān)著的燈。

下面這種狀態(tài)

10111
01101
10111
10000
11011
在改變了最左上角的燈的狀態(tài)后將變成：

01111
11101
10111
10000
11011
再改變它正中間的燈后狀態(tài)將變成：

01111
11001
11001
10100
11011
給定一些游戲的初始狀態(tài)，編寫程序判斷游戲者是否可能在 6 步以內(nèi)使所有的燈都變亮。

輸入格式
第一行輸入正整數(shù) n，代表數(shù)據(jù)中共有 n 個待解決的游戲初始狀態(tài)。

以下若干行數(shù)據(jù)分為 n 組，每組數(shù)據(jù)有 5 行，每行 5 個字符。

每組數(shù)據(jù)描述了一個游戲的初始狀態(tài)。

各組數(shù)據(jù)間用一個空行分隔。

輸出格式
一共輸出 n 行數(shù)據(jù)，每行有一個小于等于 6 的整數(shù)，它表示對于輸入數(shù)據(jù)中對應(yīng)的游戲狀態(tài)最少需要幾步才能使所有燈變亮。

對于某一個游戲初始狀態(tài)，若 6 步以內(nèi)無法使所有燈變亮，則輸出 ?1。

數(shù)據(jù)范圍
0<n≤500
輸入樣例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
輸出樣例：

3
2
-1

題解

該題我們分析可以發(fā)現(xiàn)，我們可以通過枚舉第一行的5個燈的32中開與不開的狀態(tài)來實現(xiàn)，因為第一行開關(guān)確定以后，第一行的開關(guān)亮與不亮只與下一層開關(guān)有關(guān)，如果i-1行j列是關(guān)的，我們就開一下i行j列的燈就可以使上一個燈泡開，一次遞推我們就可以實現(xiàn)是否所有燈都能開，要注意的是我們要保存一下開始的燈泡狀態(tài)，因為要枚舉32次，積累一下位運算>>

我們可以通過op>>i&1表示第一行的燈是否開，這是通過二進(jìn)制存儲實現(xiàn)的，我們用0表示不開，用1表示開。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;
const int N=510;
char g[6][6],backup[6][6];
int dx[6]={-1,0,1,0,0},dy[6]={0,1,0,-1,0};
int n;
void turn(int x,int y){for(int i=0;i<5;i++){int a=x+dx[i],b=y+dy[i];if(a<0||a>=5||b<0||b>=5)continue;g[a][b]^=1;}
}
int main(){cin>>n;while(n--){for(int i=0;i<5;i++)cin>>g[i];int ans=10;for(int op=0;op<32;op++){memcpy(backup,g,sizeof g);int stmp=0;for(int i=0;i<5;i++){if(op>>i&1){turn(0,i);stmp++;}}for(int i=1;i<5;i++){for(int j=0;j<5;j++){if(g[i-1][j]=='0'){turn(i,j);stmp++;}}}bool suf=true;for(int j=0;j<5;j++){if(g[4][j]=='0'){suf=false;break;}}if(suf){ans=min(ans,stmp);}memcpy(g,backup,sizeof backup);}if(ans>6){cout<<-1<<endl;}else{cout<<ans<<endl;}}return 0;
}

😄總結(jié)

本文介紹了遞推算法的基礎(chǔ)知識，并通過斐波那契數(shù)列和一個實際問題的例題進(jìn)行了講解和分析。通過學(xué)習(xí)這些例題，讀者可以更深入地理解遞推算法的原理和應(yīng)用場景，為進(jìn)一步探索算法和解決實際問題打下堅實的基礎(chǔ)。

😁熱門專欄推薦
想學(xué)習(xí)vue的可以看看這個

java基礎(chǔ)合集

數(shù)據(jù)庫合集

redis合集

nginx合集

linux合集

手寫機(jī)制

微服務(wù)組件

spring_塵覺

springMVC

mybits

等等等還有許多優(yōu)秀的合集在主頁等著大家的光顧感謝大家的支持

🤔歡迎大家加入我的社區(qū) 塵覺社區(qū)

文章到這里就結(jié)束了，如果有什么疑問的地方請指出，諸佬們一起來評論區(qū)一起討論😁
希望能和諸佬們一起努力，今后我們一起觀看感謝您的閱讀🍻
如果幫助到您不妨3連支持一下，創(chuàng)造不易您們的支持是我的動力🤞