楼梯有n阶台阶,上楼可以一步上1阶,2阶,3阶,编程序计算共有多少种不同的走法? |
您所在的位置:网站首页 › 一步一步走出来 › 楼梯有n阶台阶,上楼可以一步上1阶,2阶,3阶,编程序计算共有多少种不同的走法? |
题目:楼梯有n阶台阶,上楼可以一步上1阶,2阶,3阶,编程序计算共有多少种不同的走法?
对于这样一个问题, 思路:设n阶台阶的走法数为f(n)。如果只有1个台阶,走法有1种(一步上1个台阶),即f(1)=1;如果有2个台阶,走法有2种(一种是上1阶,再上1阶,另一种是一步上2阶),即f(2)=2;如果有3个台阶,走法有4种(一种每次1阶,共一种;另一种是2+1,共两种;第三种是3,共1种),即f(3)=4; 当有n个台阶(n>3)时,我们缩小问题规模,可以这样想:最后是一步上1个台阶的话,之前上了n-1个台阶,走法为f(n-1)种,而最后是一步上2个台阶的话,之前上了n-2个台阶,走法为f(n-2)种,故而f(n)=f(n-1)+f(n-2)。列出的递归方程为:f(1)=1;f(2)=2; f(3)=4; if(n==1) return 1; else if(n==2) return 2; else if(n==3) return 4; else return f(n-1)+f(n-2)+f(n-3),n>3 最后一步可能是从第n-1阶往上走1阶、从n-2阶往上走2阶,或从第n-3阶往上走3阶。因此,抵达最后一阶的走法,其实就是抵达这最后三阶的方式的总和。 解决方法1:按照递归的思想;但运算时间很长 int countWays (int n) {if (n |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |