算法与数据结构---7.4、变态跳台阶
一、总结
一句话总结:
1、变态跳台阶的问题有了之前跳台阶和进阶跳台阶的问题做铺垫,递推表达式非常好想:f(n)=f(n-1)+f(n-2)+...+f(n-k),
2、根据f(n)=f(n-1)+f(n-2)+...+f(n-k),所以我们需要知道前k项,从而确定1-k项为初始状态,从而求解
#include <iostream> using namespace std; const int mod=100003; int f[100005]={0}; int main(){ int n,k; cin>>n;cin>>k; //1、确定初始值(前k项) f[1]=1; for(int i=2;i<=k;i++){ f[i]=1; for(int j=1;j<=i-1;j++){ f[i]=(f[i]+f[j])%mod; } } //2、根据递推表达式来做递推 //f(n)=f(n-1)+f(n-2)+...+f(n-k) for(int i=k+1;i<=n;i++){ for(int j=1;j<=k;j++){ f[i]=(f[i]+f[i-j])%mod; } } cout<<f[n]<<endl; return 0; }
二、变态跳台阶
博客对应课程的视频位置:7.4、变态跳台阶
https://www.fanrenyi.com/video/27/287
1、题目描述
题目描述
有N级的台阶,你一开始在底部,
每次可以向上迈最多K级台阶(最少1级),
问到达第N级台阶有多少种不同方式。
输入格式
两个正整数N,K。
输出格式
一个正整数,为不同方式数,由于答案可能很大,
你需要输出ans mod 100003后的结果。
输入输出样例
输入
5 2
输出
8
数据范围:
对于20%的数据,有N<=10, K<=3;
对于40%的数据,有N<=1000;
对于100%的数据,有N<=100000,K<=100。
题目位置:
P1192 台阶问题 - 洛谷
https://www.luogu.com.cn/problem/P1192
2、分析及解答
分析:
f(n)=f(n-1)+f(n-2)+...+f(n-k)
n=5,k=2
f(5)=f(4)+f(3)
初始状态:
f(1)=1
前k项的值怎么确定
这个时候,问题就变成有k级台阶,
每次可以跳k步,问达到k级台阶有多少种跳法
f(1)=1
f(2)=2
f(3)=f(2)+f(1)+1=4
f(4)=f(3)+f(2)+f(1)+1=8
f(5)=f(4)+f(3)+f(2)+f(1)+1=16
算法思路:
1、确定初始值(前k项)
2、根据递推表达式来做递推
1 #include <iostream> 2 using namespace std; 3 const int mod=100003; 4 int f[100005]={0}; 5 int main(){ 6 int n,k; 7 cin>>n;cin>>k; 8 //1、确定初始值(前k项) 9 f[1]=1; 10 for(int i=2;i<=k;i++){ 11 f[i]=1; 12 for(int j=1;j<=i-1;j++){ 13 f[i]=(f[i]+f[j])%mod; 14 } 15 } 16 //2、根据递推表达式来做递推 17 //f(n)=f(n-1)+f(n-2)+...+f(n-k) 18 for(int i=k+1;i<=n;i++){ 19 for(int j=1;j<=k;j++){ 20 f[i]=(f[i]+f[i-j])%mod; 21 } 22 } 23 cout<<f[n]<<endl; 24 return 0; 25 }
三、跳台阶
博客对应课程的视频位置:7.2、跳台阶-高精度加法
https://www.fanrenyi.com/video/27/285
1、题目描述
题目描述
有N级的台阶,你一开始在底部,
每次可以向上跳一步或者跳两步,
问到达第N级台阶总共有多少种不同方式。
输入格式
一个数字,楼梯数。
输出格式
走的方式几种。
输入输出样例
输入
4
输出
5
数据范围
60%,N<=50
100%,N<=5000
题目位置:
P1255 数楼梯 - 洛谷 | 计算机科学教育新生态
https://www.luogu.com.cn/problem/P1255
2、分析
分析:
第1级台阶有一种方式
第2级台阶有两种方式
第3级台阶可以由第1阶走两步或第2阶走一步得出。1+2=3
第4级台阶由第2阶走两步或第3阶走一步得出。2+3=5
第5级台阶由第3阶走两步或第4阶走一步得出。3+5=8
...
所以
第n级台阶由第n-2阶走两步或第n-1阶走一步得出。
所以如果用 f(n)表示跳到第n级台阶的总方式数
所以 f(n)=f(n-1)+f(n-2)
3、没高精度只能过5个点
本题的考点除了斐波那契数列,还考高精度,没写高精度只能过5个点
1 #include <iostream>
2 using namespace std;
3
4 int main(){
5 int n;
6 int a,b,c;
7 cin>>n;
8 //1、确定初始值
9 a=1;
10 b=2;
11 //2、循环做递推,3-n
12 for(int i=3;i<=n;i++){
13 //F(n)=F(n-1)+F(n-2)
14 c=b+a;
15 //保留f(n)和f(n-1)做下一轮的f(n-1)和f(n-2)
16 a=b;
17 b=c;
18 }
19 if(n==0) cout<<0<<endl;
20 else if(n==1) cout<<1<<endl;
21 else if(n==2) cout<<2<<endl;
22 else cout<<c<<endl;
23 return 0;
24 }
4、加上高精度过所有点
高精度加法,因为递推关系式里面就是加法:
https://www.cnblogs.com/Renyi-Fan/p/13066540.html
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 //高精度数对应的结构体
7 struct BigNum{
8 int length=0;
9 int v[5000];
10 BigNum(){
11 memset(v,0,sizeof(v));
12 }
13 };
14
15 //高精度加法
16 BigNum add(BigNum a,BigNum b){
17 BigNum ans;
18 ans.length=max(a.length,b.length);
19 //逐位相加
20 for(int i=0;i<=ans.length-1;i++){
21 ans.v[i]=a.v[i]+b.v[i];
22 }
23 //处理进位
24 for(int i=0;i<=ans.length-1;i++){
25 if(ans.v[i]/10){
26 ans.v[i+1]+=ans.v[i]/10;
27 ans.v[i]%=10;
28 }
29 }
30 //判断最高位的数
31 if(ans.v[ans.length]) ans.length++;
32 return ans;
33 }
34
35
36 int main(){
37 int n;
38 BigNum a,b,c;
39 cin>>n;
40 //1、确定初始值
41 a.length=1;b.length=1;
42 a.v[0]=1;
43 b.v[0]=2;
44 //2、循环做递推,3-n
45 for(int i=3;i<=n;i++){
46 //F(n)=F(n-1)+F(n-2)
47 c=add(b,a);
48 //保留f(n)和f(n-1)做下一轮的f(n-1)和f(n-2)
49 a=b;
50 b=c;
51 }
52 if(n==0) cout<<0<<endl;
53 else if(n==1) cout<<1<<endl;
54 else if(n==2) cout<<2<<endl;
55 else{
56 for(int i=c.length-1;i>=0;i--){
57 cout<<c.v[i];
58 }
59 cout<<endl;
60 }
61 return 0;
62 }
四、进阶跳台阶
博客对应课程的视频位置:7.3、进阶跳台阶
https://www.fanrenyi.com/video/27/286
1、问题描述
有n级的台阶,你一开始在底部,
每次可以向上迈最多n级台阶,
问到达第n级台阶有多少种不同方式。
题目位置:
变态跳台阶_牛客网
https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&&tqId=11162&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
2、分析及解答
1 /*
2 分析:
3
4 f(1)=1
5 f(2)=2
6 f(3)=f(2)+f(1)+1=4
7 f(4)=f(3)+f(2)+f(1)+1=8
8 f(5)=f(4)+f(3)+f(2)+f(1)+1=16
9
10 如果发现数字规律,可以直接
11 f(n)=2^(n-1)
12
13 如果没发现数字规律,可以用递推公式
14 f(n)=f(n-1)+f(n-2)+...+f(1)+1
15
16 */
17 #include <iostream>
18 using namespace std;
19 int f[10000]={0};
20 int main(){
21 int n;
22 cin>>n;
23 f[1]=1;
24 f[2]=2;
25 //这层循环用来求f[i]
26 for(int i=3;i<=n;i++){
27 f[i]=1;
28 for(int j=1;j<=i-1;j++){
29 f[i]+=f[j];
30 }
31 }
32 cout<<f[n]<<endl;
33 return 0;
34 }