A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 周刚 中级黑马   /  2012-7-13 23:13  /  4797 人查看  /  24 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 周刚 于 2012-7-13 23:21 编辑

也是很常见的一个递归算法问题,供大家练习
斐波那锲数列:1,1,2,3,5,8,13,21...求出第100项是多少?如果说这一问可以用循环实现。
那么下一问:102334155是数列中的多少项?像这种循环次数未知的,恐怕递归是最好的方法

评分

参与人数 1黑马币 +30 收起 理由
蒋映辉 + 30 赞一个!

查看全部评分

24 个回复

倒序浏览
嗯  其实我也想出这个的,后来觉得这个太没难度了,而且这个不用递归也可以做出来  而且不用递归还好做一些  在算法中  能不用递归就尽量不要用,毕竟递归传递过去又传递回来很耗时....
回复 使用道具 举报
蒋映辉 发表于 2012-7-13 23:14
嗯  其实我也想出这个的,后来觉得这个太没难度了,而且这个不用递归也可以做出来  而且不用递归还好做一些 ...


嗯,你说得很有道理!递归空间复杂度、时间复杂度都比较大。很多时候如果用非递归的可以做出来,当然就非递归更优。但很多时候程序的结束点是未知的,循环次数也不能确定,此时恐怕只能用递归,比如说此题的第二问

点评

恩咯 确实。。在很多情况下递归还是要用的。比如遍历文件目录的时候  发表于 2012-7-13 23:28
回复 使用道具 举报
蒋映辉 发表于 2012-7-13 23:14
嗯  其实我也想出这个的,后来觉得这个太没难度了,而且这个不用递归也可以做出来  而且不用递归还好做一些 ...

递归确实太耗时了 ,你出的那个汉诺塔的 运行了2个多小时,输出的文本记录1300多个 8G 多 ,还没运行完

点评

恩咯 实在人啊 其实把数字出大点就是希望大家都明白这个原理  发表于 2012-7-13 23:30
回复 使用道具 举报
丁二跃 发表于 2012-7-13 23:26
递归确实太耗时了 ,你出的那个汉诺塔的 运行了2个多小时,输出的文本记录1300多个 8G 多 ,还没运行完
...

不会吧,这么夸张?!两个多小时,哥们真可以。你把层数设成了多少?
回复 使用道具 举报
public class Test
{
    public int compute(int a)
    {
        if(a == 1 || a ==2)
        {
            return 1;
        }
        else
        {
            return compute(a - 1) + compute(a - 2);
        }
    }
   
    public static void main(String[] args)
    {
        Test test = new Test();
        System.out.println(test.compute(8));
    }
}


用递归很简单吧 斐波那锲

点评

你试试用循环和数组做呢 更简单.....  发表于 2012-7-13 23:31

评分

参与人数 1技术分 +1 收起 理由
蒋映辉 + 1

查看全部评分

回复 使用道具 举报
许瑞航 发表于 2012-7-13 23:29
public class Test
{
    public int compute(int a)

果然是这么回事、我还是回去老实的看视频吧、
回复 使用道具 举报
周刚 发表于 2012-7-13 23:27
不会吧,这么夸张?!两个多小时,哥们真可以。你把层数设成了多少?

64 ………… 一直在跑着:(
回复 使用道具 举报
韦念欣 黑马帝 2012-7-13 23:45:58
9#
使用动态规划,这样快一些,时间复杂度也比较小。
回复 使用道具 举报
丁二跃 发表于 2012-7-13 23:39
64 ………… 一直在跑着

呵呵,这是个问题,我设成20,共移动了1048575次。
回复 使用道具 举报
求项数也能不用递归吧,从头求各项,然后判断就可以了

  1. public class Fibonacci{
  2.         private static int[] add=new int[100];
  3.         private static int pos=0;
  4.         public static int getPos(int i){
  5.                 if(i<2)
  6.                         return -1;
  7.                 add[0]=1;
  8.                 add[1]=1;
  9.                 pos=1;
  10.                 while(i-add[pos]>0){
  11.                         pos++;
  12.                         add[pos]=add[pos-1]+add[pos-2];
  13.                 }
  14.                 if(i-add[pos]==0)
  15.                         return pos;
  16.                 else
  17.                         return -1;
  18.         }
  19.         public static void main(String[] args){
  20.                 System.out.println(getPos(102334155));
  21.         }
  22. }
复制代码

评分

参与人数 1技术分 +1 收起 理由
蒋映辉 + 1 赞一个!

查看全部评分

回复 使用道具 举报
算法没问题 关键是第100项到底是什么数字呢,应该用什么类型来存储?

评分

参与人数 1技术分 +1 收起 理由
蒋映辉 + 1

查看全部评分

回复 使用道具 举报
温少邦 发表于 2012-7-13 23:48
求项数也能不用递归吧,从头求各项,然后判断就可以了


嗯,兄弟很有才!思路很活跃,建议加分!
回复 使用道具 举报
黑马振鹏 发表于 2012-7-13 23:58
算法没问题 关键是第100项到底是什么数字呢,应该用什么类型来存储?

哦,sorry我随便写的,100项可能太大了,可能Long都不能表示,那用BigDecimal不知道可否?
回复 使用道具 举报
周刚 发表于 2012-7-14 00:00
哦,sorry我随便写的,100项可能太大了,可能Long都不能表示,那用BigDecimal不知道可否? ...

....................
回复 使用道具 举报
发现第一个弄了好久第一百项却没有弄出来,所以就先把第二个发上来了
import java.util.LinkedList;
class Demo {
        public static void main(String[] args) {
                //思路:可以用循环来实现,用数组来存储,发现不行,可不可以转成字符串来进行呢
                long [] arr = new long[100];
                arr[0]=arr[1] = 1;
               
                for (int x=2;x<=100 ;x++ )
                {
                        arr[x] = arr[x-1]+arr[x-2];
                        if(arr[x]==102334155)
                                {
                                        System.out.println(x);
                                        break;
                                }
                }
               
        }
}
打印的结果是第39项,

点评

还是你真个清晰,代码清晰,思路清晰,我喜欢!  发表于 2012-7-14 01:38

评分

参与人数 1技术分 +1 收起 理由
蒋映辉 + 1

查看全部评分

回复 使用道具 举报
在网上搜索了一下,发现有一篇类似的帖子,不过求的结果是前100项的和,厚颜学习,改进了一下,哎,结果可以打印出第一百项了
import java.util.ArrayList;
import java.util.List;

public class TestDemo {
        public static void main(String[] args) {
                List<Long> list = new ArrayList<Long>();
               
                for(int i = 1;i <= 100;i++){
                        if(i <= 2){
                                list.add(new Long(1));
                        }else{
                                long value = list.get(i-2) + list.get(i - 3);
                                list.add(new Long(value));
                        }
                       
                }
                        System.out.print(list.get(list.size()-1).longValue() + "  ");
        }
}
第一百项是
3736710778780434371  
回复 使用道具 举报
yufeiant 发表于 2012-7-14 01:23
在网上搜索了一下,发现有一篇类似的帖子,不过求的结果是前100项的和,厚颜学习,改进了一下,哎,结果可 ...

你都肯承认是搜的还厚颜?真正厚颜的是那些直接百度来答案 改改骗分的人 呵呵
回复 使用道具 举报
achilles 发表于 2012-7-14 03:23
你都肯承认是搜的还厚颜?真正厚颜的是那些直接百度来答案 改改骗分的人 呵呵 ...

嗯  这位哥们儿正解..
回复 使用道具 举报
  1. //我的算法就是在第一个地方补上0,可能跟别的有点不一样
  2. class Test  {
  3.   

  4.     public static int no=1;


  5.     void cau(double n,double m){
  6.         no++;//用来表示当前算的是第几个数
  7.         double temp=m;
  8.         m=n+m;
  9.         n=temp;
  10.       
  11.         if(100==no){
  12.             System.out.println(m);
  13.             System.exit(0);
  14.         }
  15.           cau(n,m);
  16.     }
  17.     public static void main(String[] args) {
  18.         new Test().cau(0,1);
  19.     }
  20. }
复制代码
亲自手打  附上测试图

QQ拼音截图未命名.png (52.89 KB, 下载次数: 85)

QQ拼音截图未命名.png

评分

参与人数 1技术分 +1 收起 理由
蒋映辉 + 1

查看全部评分

回复 使用道具 举报
12下一页
您需要登录后才可以回帖 登录 | 加入黑马