一个有意思的算法面试题

这不年后了么，尝试着换一个工作环境，去一家IT公司继续面试原来的工作岗位，软件测试

面试到第三轮，技术总监。

尴尬的是，总监今天不在公司，第二天进行了电话简单的面试。

给我出了一个简单的算法题目。

“从楼上走到楼下有N个台阶。每一步有三种走法：走一个台阶，走两个台阶，走三个台阶。

当有1个台阶的时候，有1种走法；

当有2个台阶的时候，有2种走法；

当有3个台阶的时候，有4种走法。

请问，当有123个台阶的时候有多少种走法。”

可以用Excel，也可以用会的编程语言算出来。

分析过程：

先把有4个台阶，5个台阶的走法都罗列出来了，然后找到了公式（我认为是正确的）。

f(n)=f(n-1)+f(n-2)+f(n-3)

至于为什么，这里就不详细说明，如果有兴趣可以私聊我进行讨论。

用Excel算出来很快，并且结果很大，出乎我的意料。

Excel计算结果

后面详细用Python进行编写代码。

---

递归方式编写算法

上图是运用迭代的方式计算的结果，取n=12，进行了以下验证。

但是如果n=123的时候，python由于递归导致的临时的栈太多，运行卡住了。

技术总监提示我可以尝试用数组的方式模拟Excel的计算方式进行改进我的代码。

思路也是先尝试的把有4层，有5层，用代码实现。

实现有4层的方法数

然后在进行修改，用循环，计算出123层的结果。

用循环的方式实现

但是为什么递归就会有这么严重的问题呢，如果在实际的编写代码的情况下，这样的代码就是一个有bug的。

晚上在网上查了很多资料。也询问了一些python群里面的大牛。他们教我可以利用尾递归的方式处理这样的问题。

尾递归处理

同一个题目，不一样的处理方式，哪一个更高效呢？

数组的方式 尾递归的方式

---

一个问题，有很多种方式方法。每个人看待问题的关注点不一样。他觉得好的，别人可能有另一种方法。

要求同存异。不断吸收。