企业网站建站费用,常设中国建设工程法律论坛网站,wordpress前端投稿,山东省工程建设信息官方网站上台阶 题目描述 有一楼梯共m级#xff0c;刚开始时你在第一级#xff0c;若每次只能跨上一级或二级#xff0c;要走上第m级#xff0c;共有多少走法#xff1f;注#xff1a;规定从一级到一级有0种走法。 输入…上台阶 题目描述 有一楼梯共m级刚开始时你在第一级若每次只能跨上一级或二级要走上第m级共有多少走法注规定从一级到一级有0种走法。 输入输入数据首先包含一个整数n(1n100)表示测试实例的个数然后是n行数据每行包含一个整数m1m40), 表示楼梯的级数。样例输入223输出对于每个测试实例请输出不同走法的数量。样例输出12时间限制C/C语言2000MS其它语言4000MS 内存限制C/C语言65537KB其它语言589825KB在赛码网做算法题遇到这样一个问题。虽然我还很一般还需要继续进步但是希望能够记录下学习的新知识。把握自己的思想写下来提供给没有想法的伙伴们一个参考~代码捉襟见肘还请见谅~这是一个动态规划问题。动态规划的特点是一个庞大的问题我们可以把它分成多个阶段每个阶段得到一个结果作为下一个阶段的开始。 但是每个阶段都有多种可能性每一种决策会影响当前的结果但是对下一阶段是没有影响的阶段之间相互独立只选择决策自己。下面说一下我的思路当前我们站在1台阶 输入一个m 代表目标台阶1 如果m是1 则 答案是0种2 如果m是2 只有一种可能:1步上去 则答案是1种3 如果m是3 两种可能两次1步一次2步 则答案是2种4 如果m是4 有两种情况到达4 从2迈2台阶到4 从3迈1台阶到4 从1到2有1种、1到3有2种所以 我们把这两种情况加在一起 12 答案是3种5 如果m是5 有两种情况到达4 从3迈2台阶到5 从4迈1台阶到5 从1到4有3种、1到3有2种 所以 我们把这两种情况加在一起 32 答案是5种......之后都是一样的我们从一开始往后推算任何一个台阶都可以从上一个台阶迈1台阶 或者 上两个台阶 迈两个台阶过来从1台阶到 前一台阶或者前两台阶都计算过。我们把两种情况相加就是这个目标的答案。这就是很典型的动态规划算法的思想了请看代码python3版本 1 #coding:utf82 def count(steps):3 if steps 1:4 return 05 if steps 2:6 return 17 if steps 3:8 return 29 return count(steps -1) count(steps -2)
10 if __name__ __main__:
11 m int(input())
12 for i in range(m):
13 n int( input() )
14 print( count(n) ) 鉴于python的使用量还不够庞大我又用c写了一遍相同的实现。 C语言版本 1 int count( steps ){2 if( steps 1 ) return 0;3 if( steps 2 ) return 1;4 if( steps 3 ) return 2;5 return count(steps -1 ) count(steps -2);6 }7 int main(){8 int n,m;9 scanf(%d,n);
10 while( n-- ){
11 scanf(%d,m);
12 printf(%d\n,count(m));
13 }
14 return 0;
15 } 这两种语言实现相同的思想。不用纠结哪种语言。 不过经历了上面的分析我们发现每次台阶的结果都是前两个台阶结果的加和 这不禁让我们联想到斐波那契数斐波那契数就是 前两项都是1从第三项开始每一项都是前两项加和。 所以用生成斐波那契数的方法来实现 python版本 1 #斐波那契数列实现2 def getResult(n):3 i 24 num1 15 num2 16 while i n:7 num1, num2 num2, num1 num28 i 19 print(num1)
10 if __name__ __main__:
11 m int(input())
12 for i in range(m):
13 n int(input())
14 getResult(n) 能力一般~~请多包涵~ 希望对大家有帮助 转载于:https://www.cnblogs.com/Lin-Yi/p/7338937.html
