啊那什么是遞推呢？
即：從已知到未知，
利用觀察發現前面已知資料從而得出遞推公式，再利用遞推公式求解，
啊那它和遞回有腎么區別？
即：從未知到已知，再從已知到未知，
舉個例子的話：（源自洛谷題單：遞推與遞回）
那么下面開始總結近日的練習
題單鏈接
T 1 3 1 2 昆 蟲 繁 殖
題目原鏈接
這是一道一本通上的例題，但是我并沒有看課本的解法
思 路
這個題上來就當頭一棒
過x月產y對卵
可能這一下就蒙了，這玩意怎么找遞推公式？
但是還是要把題看完的嘛，
后面就有稍微熟悉點的東西了，
每對卵要過兩個月長成成蟲，且卵長成成蟲后的第一個月不產卵(過x個月產卵)
但是好像還不是很明顯，再看樣例，可以看出實際上是有一定的關系可尋的，
對于樣例，每過1個月每對成蟲生2對幼蟲，每對幼蟲兩個月長成成蟲，
那么：
當月的成蟲=上上個月（兩個月前）的幼蟲+上個月的成蟲
當月的幼蟲=上個月（一個月前）的成蟲*2
再由這個特殊推向一般，
即得：
當月的成蟲=一個月前成蟲+兩個月前的幼蟲
當月的幼蟲=x月前的成蟲*y
設c[i]是當月的成蟲數量，u[i]是當月的幼蟲數量，表示上式可得：
c[i]=c[i-1]+u[i-2]
u[i]=c[i-x]*y
搞完這些，就可以代碼實作了，
剩下的都在代碼注釋里面了（
上 代 碼
#include <iostream>
using namespace std;
int long long c[60],u[60];//c是成蟲的數量，u是幼蟲的數量
int main()
{
int x,y,z;
cin>>x>>y>>z;
for(int i=1;i<=x;i++)
{
c[i]=1;u[i]=0;//因為過x月才產一次，所以在1~x月都只有1對成蟲
}
for(int i=x+1;i<=z+1;i++)
{
u[i]=y*c[i-x];//本月幼蟲是x月之前的成蟲生的，所以幼蟲數量就是i-x月的成蟲*y
c[i]=c[i-1]+u[i-2];//因為兩個月幼蟲長成成蟲，所以本月成蟲就是上月的成蟲數量+上上月的幼蟲數量
}
cout<<c[z+1];//過了z月，即輸出第z+1月的成蟲數量
return 0;
}
本題總結
對于我來說最一開始想那些用的時間很長，但是一點一點分析還是可以出來的
蒟蒻嘆氣
T 1 3 1 3 位 數 問 題
題目原鏈接
又是一道例題
思路
在第一遍做的時候，看完題目毫無思路......
因為出現了因為語文差而產生的死亡性閱讀偏差：
題目第一句話
在所有的N位數中，有多少個數中有偶數個數字3?
正常的斷句
在所有的N位數中，有多少個/數中/有偶數個/數字3?
但是我的斷句：
在所有的N位數中，有多少/個數中有/偶數/個數/字3?
導致我光看題看了三分鐘......
看完題了還是沒思路，看決議也不會，于是去問學長，問明白了，
果然還是我太菜，人家三分鐘連代碼都敲完了
st（Q A Q） 學長 （Q A Q）rz
經過我理解之后，思路是這樣的：
分析每一位奇數個三和偶數個三的個數然后推導這一位的這兩個數值和上一位的這連個數值有腎么關系
設f[i]為到當前位，3的個數為偶數的情況總數，g[i]則是3的個數為奇數的情況總數
這里的位數是從小到大，即由個位到百位，千位......
遞推公式要先有個已知，也就是要有個頭，于是分析個位的情況
| 0個3 | 0,1,2,4,5,6,7,8,9 | 9個 |
|---|---|---|
| 1個3 | 3 | 1個 |
也就是f[i]=9，g[i]=1
有了這個再去推普遍的情況
假設之前的位都已經推好了，如果要有偶數個3的話
- 當前位的0,1,2,4,5,6,7,8,9都可以和上一位的每一種有偶數個3的情況結合，產生新的有偶數個3的數，
（因為前者都有0個3，后者必有偶數個3，加在一起還是必有偶數個3） - 當前位的3可以和上一位的每一種有奇數個3的情況結合，產生新的有偶數個3的數
（因為前者有奇數個3，后者必有奇數個3，加在一起必有偶數個3）
所以可以推得f[i]=f[i-1]*9+g[i-1]
同樣的道理，如果要有奇數個3的話
- 當前位的0,1,2,4,5,6,7,8,9都可以和上一位的每一種有奇數個3的情況結合，產生新的有奇數個3的數，
（因為前者都有0個3，后者必有奇數個3，加在一起必有奇數個3） - 當前位的3可以和上一位的每一種有偶數個3的情況結合，產生新的有奇數個3的數
（因為前者有奇數個3，后者必有偶數個3，加在一起必有奇數個3）
所以可以推得g[i]=g[i-1]*9+f[i-1]
（小學奇偶性的連續運用）
這樣就完了......
嗎？
起初我和學長都是這樣認為的，于是提交.......
10*WA......
于是好像還差了點什么，于是再分析......
原來最后一位（最高位）不能是0，淦......
那么就需要在剛才的分析的基礎上，添加一個特判
即當到最后一位的時候，上式（們）變為：
f[i]=f[i-1]* 8 +g[i-1]
f[i]=f[i-1]* 8 +g[i-1]
那么接下來就可以實作10*AC了
上 代 碼
#include <iostream>
#include <cstdio>
using namespace std;
int n,f[1001],g[1001];//f是有偶數個3的數的個數，g是有奇數個3的個數
int main()
{
cin>>n;
f[1]=9;//第一位（個位）有9個數中是0個數字3
g[1]=1;//第一位中只有3有奇數（1個）數字3
int x=9;//每位考慮0-9（除3）的情況
for(int i=2;i<=n;i++)
{
if(i==n)
x--;//當i到最后一位（最高位）的時候，因為最高位不能是0，所以這里的x變為8，即考慮1~9（除3）的情況
f[i]=f[i-1]*x+g[i-1];
g[i]=g[i-1]*x+f[i-1];
f[i]%=12345;//按照題目要求模12345
g[i]%=12345;
}
cout<<f[n];
}
下面這個是從網上找到的，大體意思一樣，也放出來吧
#include<iostream>
#include<cstdio>
using namespace std;
const int mod = 12345;
int num[1010][2];
int main()
{
int n;
num[1][0] = 9; num[1][1] = 1;
scanf("%d", &n);
int x = 9;
for (int i = 2; i <= n; ++i)
{
if (i == n)
--x;
num[i][0] = (num[i - 1][0] * x + num[i - 1][1]) % mod;
num[i][1] = (num[i - 1][1] * x + num[i - 1][0]) % mod;
}
printf("%d\n", num[n][0]);
}
本題總結
要分類討論，假設遞推
T 1 3 1 4 過河卒 + T 1 1 9 1 流 感 傳 染 + T 1 1 9 4 移 動 路 線
T1314+T1191+T1194+過河卒洛谷
為什么把這幾道題放一塊呢？
很簡單，解法類似（或者說我的解法類似），都是圖形中的遞推
過河卒 思路
既然這個題給了圖，那我就往圖的方向去想
我們看它的問題：
從A點能夠到達B點的路徑的條數
于是我想到到達每個點的方案數，因為是有到達不了的點的，而最后要到達的點也是可以以此分析的，
假設A點的到達路徑數為1，由題中說只能向下或向右，我們可以得出這樣一個表
1 1 1 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0
1 3 3 3 0 0 0 0 0
1 4 0 3 3 3 0 0 0
1 5 5 0 3 0 0 0 0
（可能比較難看懂，把馬能到的點標為C,再把A和B加粗）
A 1 1 C 0 C 0 0 0
1 2 C 0 0 0 C 0 0
1 3 3 3 C 0 0 0 0
1 4 C 3 3 3 C 0 0
1 5 5 C 3 C 0 0 0
可以看出每個點都是它的上和左的和（因為只能向下、向右走卒）
那怎么解決最邊上的呢？
這里的話我把A平移到的(1,1)其他的，也相應平移 [比如B變成（n+1，m+1）]
然后把最邊上的一排和一列都初始化為0，這樣的話對加法運算不會產生影響，也不會超越陣列限制
還有一點就是如A，C這樣的點，每次操作它們的時候得保證值不變（A始終為1，C始終為0）
主要就是用二維陣列模擬坐標系來計算
過河卒 代碼
#include <iostream>
using namespace std;
int long long sq[22][22],c1,c2,n,m;
void seth()//將A點，C點以及馬能到的點初始化，加if以防出陣列
{
sq[1][1]=1;
sq[c1+1][c2+1]=0;
if(c1>=0&&c1<=n+1&&c2+3>=0&&c2+3<=m+1)
sq[c1][c2+3]=0;
if(c1>=0&&c1<=n+1&&c2-1>=0&&c2-1<=m+1)
sq[c1][c2-1]=0;
if(c1+2>=0&&c1+2<=n+1&&c2+3>=0&&c2+3<=m+1)
sq[c1+2][c2+3]=0;
if(c1+2>=0&&c1+2<=n+1&&c2-1>=0&&c2-1<=m+1)
sq[c1+2][c2-1]=0;
if(c1+3>=0&&c1+3<=n+1&&c2+2>=0&&c2+2<=m+1)
sq[c1+3][c2+2]=0;
if(c1+3>=0&&c1+3<=n+1&&c2>=0&&c2<=m+1)
sq[c1+3][c2]=0;
if(c1-1>=0&&c1-1<=n+1&&c2+2>=0&&c2+2<=m+1)
sq[c1-1][c2+2]=0;
if(c1-1>=0&&c1-1<=n+1&&c2>=0&&c2<=m+1)
sq[c1-1][c2]=0;
}
int main()
{
cin>>n>>m>>c1>>c2;
seth();
for(int i=1;i<=n+1;i++)
{
for(int u=1;u<=m+1;u++)
{
sq[i][u]=sq[i-1][u]+sq[i][u-1];
seth();
}
}
cout<<sq[n+1][m+1];
return 0;
}
因為這個題昨天一次過了
所以這個代碼沒有怎么改，顯得比較臃腫，
流感傳染 思路
和上個題相似，但這次不同的是這次要判斷上下左右四個方向的房間，還要判斷是否為空
但是多加幾個判斷誰不會啊
為了防止超出陣列范圍，我還是做了判斷
這個題我估計解法不少
這里隨便放一種解法
流感傳染 代碼
#include<iostream>
#include<cstring>
using namespace std;
char s[110];
int a[110][110];
struct nxx
{
int r;
int c;
int d;
}q[10100];
int nexe[][2]={{-1,0},{1,0},{0,-1},{0,1}};
int main()
{
int n,m;
int h=1,t=1;
int r,c,d;
int nr,nc,gt=0;
int i,j;
cin>>n;
for(i=0;i<n;i++)
{
cin>>s;
for(j=0;j<n;j++)
if(s[j]=='.')
a[i][j]=0;
else if(s[j]=='@')
{
a[i][j]=1;
q[t].r=i;
q[t].c=j;
q[t].d=1;
t++;
}
else if(s[j]=='#')
a[i][j]=2;
}
cin>>m;
while(h<t)
{
r=q[h].r;
c=q[h].c;
d=q[h].d;
if(d==m)
break;
for(i=0;i<4;i++)
{
nr=r+nexe[i][0];
nc=c+nexe[i][1];
if(a[nr][nc]==0&&0<=nr&&nr<n&&0<=nc&&nc<n)
{
q[t].r=nr;
q[t].c=nc;
q[t].d=d+1;
a[nr][nc]=1;
t++;
}
}
h++;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]==1)
gt++;
cout<<gt<<endl;
return 0;
}
這個解法是用了陣列來判斷周圍四個房子是否為空/已經被感染
（由此可見病毒的傳播很快，所以過年要注意個人防護）
移動路線 思路
啊這題一看就非常的眼熟，這不就是過河卒的簡化+反向版嗎
過河卒是只能向下和向右，這個題螞蟻只能向上和向右
我的主題思路還是用二維陣列來推導每個方格的可能路徑總數
實際上就是把過河卒的每個格由上+左改為下+左
（甚至如果想偷懶的話就改一下陣列下標，刪掉關于馬的定點就行）
就不多說了
移動路線 代碼
#include <iostream>
using namespace std;
int sq[21][21],m,n;
int main()
{
cin>>m>>n;
sq[1][1]=1;
for(int i=1;i<=m;i++)
{
for(int u=1;u<=n;u++)
{
sq[i][u]=sq[i-1][u]+sq[i][u-1];sq[1][1]=1;
}
}
cout<<sq[m][n]<<endl;
return 0;
}
本組題總結
要會數形結合，注意不變點
T 1 1 8 8 斐 波 那 契 數 列 （2） + T 1 1 8 9 P e l l 數 列 + T 1 1 9 6 踩 方 格
T1188+T1189+T1196
啊那為什么把這三道題放在一起呢？
因為他們都是找規律數列遞推題
斐波那契數列（2） 思路
啊那這為什么是（2）呢？
因為它多加了個取模1000......
思路就很簡單了，畢竟斐波那契數列在這里只用到遞推公式了
即對于i>=3
j[i]=j[i-1]+j[i-2]
再加上模1000
j[i]=j[i-1]+j[i-2]%1000
當然在這里一個一個模也是可以的
斐波那契數列（2） 代碼
#include <iostream>
using namespace std;
int long long f[10000001],num[10000001],a;
int main()
{
int n;
cin>>n;
for(int u=0;u<n;u++)
{
cin>>a;
f[1]=f[2]=1;
for(int i=3;i<=a;i++)
{
f[i]=(f[i-1]+f[i-2])%1000;
}
num[u]=f[a];
}
for(int i=0;i<n;i++)
cout<<num[i]<<endl;
return 0;
}
極 其 簡 單
Pell數列 思路
看題之前:看起來好高級的樣子
看題之后：真高級，這不就斐波那契數列第一項x2嗎
Pell數列 代碼
#include <iostream>
using namespace std;
int long long f[10000001],num[10000001],a;
int main()
{
int n;
cin>>n;
for(int u=0;u<n;u++)
{
cin>>a;
f[1]=1;
f[2]=2;
for(int i=3;i<=a;i++)
{
f[i]=(2*f[i-1]+f[i-2])%32767;
}
num[u]=f[a];
}
for(int i=0;i<n;i++)
cout<<num[i]<<endl;
return 0;
}
踩方格 思路
說實話我最一開始以為這也是個圖形問題
后來發現這個好像沒有界限就不是很好推，于是就一點一點的寫，然后發現：
這不也是Pell數列嗎......
（真就套娃）
踩方格 代碼
#include <iostream>
using namespace std;
int main()
{
int x[21]={0},n;
x[0]=1;
x[1]=3;
cin>>n;
for(int i=2;i<=n;i++)
{
x[i]=2*x[i-1]+x[i-2];
}
cout<<x[n];
return 0;
}
本組題總結
耐心找規律，鬼都能做對
總結
可以發現，到了遞推，這些題都有或許難度了，也不再是只是狹窄的考法，演算法的思路也逐漸拓寬，那這更需要我去耐心思考，看到題就用筆和紙分析一下，不要純靠想
也可以去Dfkuaid的回顧那看看
鏈接在這
End
2020.2.2
共3232字
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/255815.html
標籤：C++
上一篇：程式編譯