「
「
「基礎演算法
」
」
」第1章 遞推演算法
目錄：
A.錯排問題
B.奇怪漢諾塔
C.數的劃分
D.傳球游戲
E.平鋪方案
A . A. A. 例題 1 1 1 錯排問題
分析：
考慮第
n
n
n個元素 放在
k
k
k位上 那么有
(
n
?
1
)
(n-1)
(n?1)種方案
(
k
≠
n
)
(k≠n)
(k?=n)
再考慮這個
k
k
k 當它在
n
n
n位時 就有由于
n
,
k
n,k
n,k兩元素位置相同 其他
n
?
2
n-2
n?2個元素錯排即可
當
k
k
k不在
n
n
n位時 直接
n
?
1
n-1
n?1個元素錯排
遞推式：
f
n
=
(
n
?
1
)
?
(
f
n
?
1
+
f
n
?
2
)
f_n=(n-1)*(f_{n-1}+f_{n-2})
fn?=(n?1)?(fn?1?+fn?2?)
CODE：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
long long f[25];
int main(){
scanf("%d",&n);
f[1]=0;f[2]=1;
for(int i=3;i<=n;i++)
f[i]=(i-1)*(f[i-1]+f[i-2]); //遞推
printf("%lld",f[n]);
return 0;
}
B . B. B. 例題 2 2 2 奇怪漢諾塔
分析：
看到這個
n
n
n這么小 直接打表
考慮只有
3
3
3座塔的漢諾塔問題 設
f
n
f_n
fn?為
n
n
n盤子
3
3
3塔的最優步數
先把
n
?
1
n-1
n?1個盤子移到
B
B
B塔 則步數為
f
n
?
1
f_{n-1}
fn?1? 再把
A
A
A塔上
1
1
1個盤子移到
C
C
C塔 步數為
1
1
1
最后把
B
B
B塔上
n
?
1
n-1
n?1盤子移到
C
C
C塔 步數為
f
n
?
1
f_{n-1}
fn?1?
最終遞推式：
2
?
f
n
?
1
+
1
2*f_{n-1}+1
2?fn?1?+1 那么這道題就可以轉化過來
f
n
f_n
fn?表示
n
n
n盤子
4
4
4塔的最優步數 先將
j
j
j個盤子從
A
A
A移到
B
B
B 步數為
f
j
f_j
fj? 將剩下
n
?
j
n-j
n?j個盤子移到
D
D
D
剩余三塔 就可以用上面的遞推式預處理出這個
f
n
?
j
f_{n-j}
fn?j?
最后將
B
B
B的
j
j
j個盤子移到
D
D
D 步數為
f
j
f_j
fj?
再把它們加起來取
m
i
n
min
min即可.
CODE：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int d[13],f[13];
int main(){
d[1]=1;
for(int i=2;i<=12;i++)
d[i]=2*d[i-1]+1; //預處理三塔步數
f[1]=1;
for(int i=2;i<=12;i++)
{
f[i]=0x3f3f3f3f;
for(int j=1;j<=i;j++)
f[i]=min(f[i],2*f[j]+d[i-j]); //最終遞推式
}
for(int i=1;i<=12;i++) printf("%d\n",f[i]);
return 0;
}
C . C. C. 例題 3 3 3 數的劃分
分析：
可以
d
f
s
dfs
dfs 但時效不夠有
200
200
200~
300
m
s
300ms
300ms
設
f
i
,
j
f_{i,j}
fi,j?表示整數
i
i
i分為
j
j
j份的方案數
那么顯然
i
<
j
i<j
i<j時
f
i
,
j
=
0
f_{i,j}=0
fi,j?=0 ;
i
=
j
i=j
i=j時
f
i
,
j
=
1
f_{i,j}=1
fi,j?=1
其他狀態：
有
1
1
1就拆
1
1
1 那么
f
i
,
j
=
f
i
?
1
,
j
?
1
f_{i,j}=f_{i-1,j-1}
fi,j?=fi?1,j?1? 沒有
1
1
1就在
f
i
?
j
,
j
f_{i-j,j}
fi?j,j?的基礎上加
1
1
1
遞推式：
f
i
,
j
=
f
i
?
1
,
j
?
1
+
f
i
?
j
,
j
f_{i,j}=f_{i-1,j-1}+f_{i-j,j}
fi,j?=fi?1,j?1?+fi?j,j?
CODE：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define reg register
using namespace std;
int n,k,f[205][12];
int main()
{
scanf("%d%d",&n,&k);
for(reg int i=1;i<=n;i++)
for(reg int j=1;j<=k;j++)
{
if(i==j) f[i][j]=1;
else if(i<j) f[i][j]=0;
else f[i][j]=f[i-1][j-1]+f[i-j][j];
}
printf("%d",f[n][k]);
return 0;
}
D . D. D. 例題 4 4 4 傳球游戲
分析：
我們設
f
i
,
j
f_{i,j}
fi,j?表示經過
i
i
i輪傳遞到第
j
j
j個同學的方案數
由于球可以從第
j
?
1
j-1
j?1和
j
+
1
j+1
j+1個同學傳過來
故有遞推式：
f
i
,
j
=
f
i
?
1
,
j
?
1
+
f
i
?
1
,
j
+
1
f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1}
fi,j?=fi?1,j?1?+fi?1,j+1?
但由于這些人坐成了一個環 我們需特別處理一下第
n
n
n位和第
1
1
1位即可.
CODE：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int n,m,f[50][50];
int main(){
scanf("%d%d",&n,&m);
f[0][1]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(j==1) f[i][j]=f[i-1][n]+f[i-1][j+1];
else if(j==n) f[i][j]=f[i-1][n-1]+f[i-1][1]; //特別處理
else f[i][j]=f[i-1][j-1]+f[i-1][j+1];
}
printf("%d",f[m][1]);
return 0;
}
E . E. E. 例題 5 5 5 平鋪方案
分析：
設
f
i
f_i
fi?表示平鋪
2
?
i
2*i
2?i矩形的方案數 分類：
在
f
i
f_i
fi?放置一個豎的
2
?
1
2*1
2?1矩形 方案數為
f
i
?
1
f_{i-1}
fi?1?
在
f
i
f_i
fi?與
f
i
?
1
f_{i-1}
fi?1?放置一個
2
?
2
2*2
2?2的矩形 方案數為
f
i
?
2
f_{i-2}
fi?2?
在
f
i
f_i
fi?與
f
i
?
1
f_{i-1}
fi?1?放置兩個橫的
2
?
1
2*1
2?1矩形 方案數為
f
i
?
2
f_{i-2}
fi?2?
遞推式：
f
i
=
2
?
f
i
?
2
+
f
i
?
1
f_i=2*f_{i-2}+f_{i-1}
fi?=2?fi?2?+fi?1?
注意
n
<
=
250
n<=250
n<=250 做高精
CODE：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int n;
struct node{
int val[103];
}a[255];
void add(int x)
{
for(int i=1;i<=100;i++) //100位數字 隨便開
{
a[x].val[i]+=a[x-2].val[i]*2+a[x-1].val[i]; //遞推式
a[x].val[i+1]=a[x].val[i]/10; //高精
a[x].val[i]%=10;
}
}
void print(int x){
int p=100;
while(a[x].val[p]==0) p--;
while(p)
{printf("%d",a[x].val[p]);p--;} //輸出
printf("\n");
}
int main(){
a[0].val[1]=a[1].val[1]=1;
a[2].val[1]=3;
for(int i=3;i<=250;i++) add(i);
while(scanf("%d",&n)!=EOF)
print(n);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240470.html
標籤：其他