每日编程-20170326

it2022-05-06  1

题目:有一楼梯共m级,刚开始时你在第一级,若每次只能跨上一级或者二级,要走上m级,共有多少走法?注:规定从一级到一级有0种走法。给定一个正整数int n,请返回一个数,代表上楼的方式数。保证n小于等于100。为了防止溢出,请返回结果Mod 1000000007的值。测试样例:3返回:2

解答:

今天开始多训练一些递归的编程题,感觉自己这方面差不少。

先从比较简单的开始。

main函数只完成简单的调用任务。

upStairs函数逻辑如下:

先判断递归是不是结束,如果n减到了1,或者2,递归结束。

0的情况下,不剩任何走法,直接返回答案。

1的情况下,只有走1步这个走法,所以答案+1.

2的情况下,有1+1,2两种走法,所以答案+2.

接下来是递归调用,将n每次减1或者2,然后调用本身。

最后是返回,如果每次减1或者2都操作完,不进行减3操作(因为没有这个走法),直接返回当前得到的答案。

1 #include <iostream> 2 3 using namespace std; 4 5 int upStairs(int n, int ans) { 6 if (n == 0) return ans; 7 if (n == 1) return ans + 1; 8 if (n == 2) return ans + 2; 9 for (size_t i = 1; i < 3; i++) 10 { 11 ans = upStairs(n - i, ans); 12 } 13 return ans; 14 } 15 int main() { 16 int n; 17 while (cin >> n) 18 { 19 int answer = 0; 20 cout << ((n - 1) == 0 ? 0 : (upStairs(n - 1, answer)))% 1000000007 << endl; 21 } 22 }

 

转载于:https://www.cnblogs.com/linhaowei0389/p/6622792.html


最新回复(0)