题目：

链接：https://ac.nowcoder.com/acm/contest/90/A 来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld

题目描述

小明在坐景驰科技研发的无人车到达了目的地。

景驰科技（JingChi.ai）是一家由人工智能技术驱动、以无人驾驶技术为核心的智能出行公司。它将打造面向中国市场的全无人驾驶。

从无人车下来以后，小明看到了一个长长的楼梯。

有一个n级台阶的楼梯，小明一次可以向上跳1步，两步，甚至是n步，请问小明跳到n级台阶有多少种跳法？

输入描述:

第一行输入一个整数t，代表有t组样例:（ T<=30） 接下来的t行，都用一个整数n，表示楼梯有n级台阶（ 1<=n<=30）

输出描述:

输出跳到第n级台阶有多少种跳法

示例1

输入

1 1

输出

1

---

问题描述：

记得高中在讲排列时老师讲过这道题的算法，但一下子又忘记了，只是模模糊糊地记得与斐波那契数列有关，在简单地列出前12345阶的跳法后就总结出下面的代码：

#include <stdio.h> int num( int n ) { int total = 0; int i; if ( n==1 ) return n; else { for ( i=2; i<=n; i++ ) { total += num(i-1); } total++; return total; } } int main() { int t; scanf ( "%d", &t ); while ( t-- ) { int n; scanf ( "%d", &n ); printf ( "%d\n",num(n) ); } return 0; }

经过几轮自测检验无误后，在平台提交了，结果是：

看来是测试点中有较大的数据导致递归超时了，一开始我想的补救方法是先列出前几项，但仔细想想后觉得并没有什么用处，再列出来的这几项相对于测试点的超时数据并不能加快多少毫秒。

然后就开始思考其他算法了，其实是对数字再次找规律（对，就是那么弱智的小学做法，因为我想不出什么方法了hhh）其实一开始的递归方法其实我也没有太弄清楚原理，也是找规律得出来的。

详细且规范的证明过程可以参考下这篇技术博客

然后我就找到了这样的规律，写出了下面的代码，因为只是一个指数运算，所以没有超时，平台也AC了。

---

代码分析：

#include <stdio.h> #include <math.h> int main() { int t; scanf ( "%d", &t ); while ( t-- ) { int n; scanf ( "%d", &n ); int k = pow(2,n-1); printf ( "%d\n", k ); } return 0; }

其中有个很有趣的小问题，为什么要单独设k变量呢？

int k = pow(2,n-1); printf ( "%d\n", k );

可不可以换成

printf ( "%d\n", pow(2,n-1) );

可以自己先试一试

详情可以看这篇博客