`
lykm02
  • 浏览: 50965 次
  • 性别: Icon_minigender_2
  • 来自: 上海
社区版块
存档分类
最新评论

博文视点算法题目解答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).
2
0
分享到:
评论
1 楼 helloqyq 2012-01-03  
这个想法牛逼!哈哈!受教了!

相关推荐

Global site tag (gtag.js) - Google Analytics