跳台阶算法
计科小马在地面,面前有一楼梯共M级。若每次只能向上跳1级,4级或7级,那么要走上第M级,共有多少种走法?
输入数据每行包含一个整数M(1
对于每个测试实例,请输出不同走法的数量。由于数值比较大输出对20170920的余数。
//计科小马在地面,面前有一楼梯共M级。若每次只能向上跳1级,4级或7级,那么服务器托管网要走上第M级,共有多少种走法?
//输入数据每行包含一个整数M(1
#include
//计科小马在地面,面前有一楼梯共M级。若每次只能向上跳1级,4级或7级,那么要走上第M级,共有多少种走法?
//输入数据每行包含一个整数M(1=1) sum += f(n-1);
if (n>=3) sum += f(n-4);
if (n>=7) sum += f(n-7);
return sum%20170920;
}
int main(int argc, char** argv) {
printf("%d",f(20)); //715
return 0;
}
有个问题:为什么要输出对20170920的余数
查看f(3)被调用了多少次,下面的f函数代码中写的是if(n==3)所以是判断f(3)
可以在运行结果看到输入20后(20个级台阶)输出了有715种方法,
然后输入0结束,之后再输出了f(3)被调用的次数,当我们输入的次数开始超过50次之后就会发现程序响应的时间越来越久了。
备忘录方法记录值
使用备忘录方法来记录这个数有没有被计算过(数组)
然后再f函数里面先判断数组里面的元素是否大于0,大于0直接返回元素,否则就计算,然后将结果赋值给数组元素并返回
int Memo[20000];
int f(int n) {
if (Memo[n]>0) return Memo[n];
if (n==0)return 1;
int sum = 0 ;
if (n>=1) sum += f(n-1);
if (n>=3) sum += f(n-4);
if (n>=7) sum += f(n-7);
Memo[n] = sum%20170920;
return Memo[n];
}
int main(int argc, char** argv) {
int i ;
while (1){
scanf("%d",&i);
for(int a=1;a
报错显示:
21 3 C:UsersuserDesktopmain.c [Error] 'for' loop initial declarations are only allowed in C99 or C11 mode
为什么错了?
因为C语言在devc++中好像是不能直接在for循环中定义的,要先在for循环前面定义,也就是:
int a ;
for (a=0;a
#include
int Memo[20000];
int main(void ) {
int i ;
while(1){
scanf("%d",&i);
if (i==0) break;
Memo[0]=1;
int a;
for (a=1;a=1) sum+=Memo[a-1];
if(a>=4) sum+=Memo[a-4];
if(a>=7) sum+=Memo[a-7];
Memo[a] = sum%20170920;
}
printf("%dn",Memo[i]);
}
return 0;
}
前后最大差值
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
shell命令概述 Shell作用:命令解释器 介于操作系统内核与用户之间,负责解释命令行 获得命令帮助 内部命令help 命令的“–help” 选项 使用man命令阅读手册页 命令行编辑的几个辅助操作 Tab键:自动补齐 反斜杠“”:强制换行 快捷键 Ct…