博文视点算法题目解答2

引用

博文视点有奖答题第二题：青蛙跳台阶问题


（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
（2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？

这种题目层出不穷。说白了，有点无聊。
主要是为了考察面试者的思维表达能力。除此之外再无他用。
对于 （1）
假设有n 级台阶，那么会有
         An-1 + An-2   n>2
An =     1             n=1
         2             n=2

这个问题就是一个递归的问题。
基本类似 费布纳西数列
不详解了。

对于 （2）
按照我的理解，其实这个题目完全可以理解成如何插空。
也有说法是，如何分解n，使得 n可以由小于他的若干数字的加和。
简单来说， 我们假定如下一个形式。
AAAA
如何来分拆这个字符串呢。
不外乎以下几种形式：
AAAA
A|AA|A
AA|AA
AA|A|A
A|AAA
AAA|A
A|A|AA
A|A|A|A
你从中看出了什么吗？

呵呵，大概你看出什么端倪了。
其实没什么名堂的，就是如何在这些A之间进行插空。
那么具体的插空我也就不说了。
答案，显而易见。就是2^^(n-1).

评论

1 楼 helloqyq 2012-01-03  

这个想法牛逼！哈哈！受教了！