【基本算法—递推递归】几种走法
- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？
- 输入
- 一个数N。1<=N<=1000。
- 输出
- 一个整数，表示共有多少种走法。由于结果可能很大，你只需要输出这个答案mod 12345的值。
- 样例输入
-
2 - 样例输出
-
7 - 来源
- 网络
- 源程序：#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
int pu(int s){
int a[1010];
a[1]=3;
a[2]=7;
for(int i=3;i<=s;i++){
a[i]=(2*a[i-1]+a[i-2])%12345;
}
return a[s];
}
int n;
int main(){
cin>>n;
cout<<pu(n);
return 0;
} - 分析：
有三种走法，所以f(n)=f(n)shang+f(n)zuo+f(n)you
向上走，即f(n)shang=f(n-1)
向左走，即f(n)zuo=f(n-1)zuo+f(n-1)shang
向右走，即f(n)you=f(n-1)you+f(n-1)shang
f(n)=2f(n-1)+f(n-2)