黑马程序员技术交流社区

标题: 第一帖!面试题,继续求各种解法! [打印本页]
作者: 白堇翎    时间: 2013-8-21 18:52
标题: 第一帖!面试题,继续求各种解法!
有一个100个台阶的阶梯，一次可以选择上一个台阶，或者两个台阶，问从第一层到最后一层有多少种走法


要求代码实现

作者: 神之梦    时间: 2013-8-21 20:56
神马都是浮云
作者: lihaotian_120    时间: 2013-8-22 14:05
本帖最后由 lihaotian_120 于 2013-8-22 16:22 编辑

好像是蓝桥杯初试的一个题目，不过100层的数据貌似很大。把递归方程写出来之后就会发现是斐波那契数列
  1. class Test2
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 System.out.println(fun(100));
  6.         }
  7.         //递归方程 ：f(n)=f(n-1)+f(n-2)  f(i)为走到第i层的时候的种数。
  8.         //边界：f(0)=1;f(n<0)=0;  
  9.         public static long fun(int n)
  10.         {
  11.                 long temp1=1,temp2=1,tempn=0;
  12.                 if(n==1||n==2)return 1;
  13.                 for(int i=3;i<=n;i++)
  14.                 {
  15.                         tempn=temp1+temp2;
  16.                         temp1=temp2;
  17.                         temp2=tempn;
  18.                 }
  19.                 return tempn;
  20.         }
  21. }
复制代码
这种方法最好想，当然，你也可以用递推，不过感觉数据好大，是我想错了吗?PS：换成递推了，但是数据存不下，要高精度处理


作者: hll    时间: 2013-8-22 16:04
假设最后到达第n层分为两种情况，一步迈一个台阶上去和一步迈两个台阶上去
那么到达第n层的方法f[n]就分为了两大类
第一类是迈上第（n-1）的方法f[n-1]，第二类是迈上第（n-2）层的方法f[n-2]
so  f[n]=f[n-1]+f[n-2]
f[1]=1
f[2]=2
so 用一个for循环就可以了，搞什么递归啊{:soso_e113:}
作者: lihaotian_120    时间: 2013-8-22 16:18
lihaotian_120 发表于 2013-8-22 14:05
好像是蓝桥杯初试的一个题目，不过100层的数据貌似很大。把递归方程写出来之后就会发现是斐波那契数列这种 ...

原理是一样的，现在的问题不是说算法，估计是大数据的处理问题
作者: lihaotian_120    时间: 2013-8-22 16:35
  1. import java.math.*;
  2. class Test2
  3. {
  4.         public static void main(String[] args)
  5.         {               
  6.                 System.out.println(fun(100));
  7.         }
  8.         //递归方程 ：f(n)=f(n-1)+f(n-2)  f(i)为走到第i层的时候的种数。
  9.         //边界：f(0)=1;f(n<0)=0;  
  10.         public static BigInteger  fun(int n)
  11.         {
  12.                 BigInteger temp1=new BigInteger("1");
  13.                 BigInteger temp2=new BigInteger("1");
  14.                 BigInteger tempn=new BigInteger("0");
  15.                
  16.                 for(int i=3;i<=n;i++)
  17.                 {
  18.                         tempn=temp1.add(temp2);
  19.                         temp1=temp2;
  20.                         temp2=tempn;
  21.                 }
  22.                 return tempn;
  23.         }
  24. }
  25. //运行结果：354224848179261915075
复制代码
这样应该可以了吧
作者: 白堇翎    时间: 2013-8-22 16:47
lihaotian_120 发表于 2013-8-22 16:35
这样应该可以了吧

其实没必要用BigInteger..用double就可以.
另外这一题正确答案约为5.7E20

这道题不能用递归解.原因是用递归的话,函数每次就要调用自己2次,而这里传了一个100进来 可想而知这里调用总次数大概是2的100次方次.
2的100次方具体是多少我不知道,但是可以确定的是他肯定比5.7E20要大.运算次数已经超过了实际的结果..这样的算法是不明智的.
所以用for循环是比较简单的一种方法..
我是来求其他方法的..
作者: lihaotian_120    时间: 2013-8-22 17:00
白堇翎 发表于 2013-8-22 16:47
其实没必要用BigInteger..用double就可以.
另外这一题正确答案约为5.7E20

嗯嗯，谢谢指导{:soso_e113:}



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2