黑马程序员技术交流社区

标题: 也出一个递归算法题 [打印本页]
作者: 周刚    时间: 2012-7-13 23:13
标题: 也出一个递归算法题
本帖最后由 周刚 于 2012-7-13 23:21 编辑

也是很常见的一个递归算法问题，供大家练习
斐波那锲数列：1，1，2，3，5，8，13，21...求出第100项是多少？如果说这一问可以用循环实现。
那么下一问：102334155是数列中的多少项？像这种循环次数未知的，恐怕递归是最好的方法
作者: 蒋映辉    时间: 2012-7-13 23:14
嗯  其实我也想出这个的，后来觉得这个太没难度了，而且这个不用递归也可以做出来  而且不用递归还好做一些  在算法中  能不用递归就尽量不要用，毕竟递归传递过去又传递回来很耗时....
作者: 周刚    时间: 2012-7-13 23:25
蒋映辉 发表于 2012-7-13 23:14
嗯  其实我也想出这个的，后来觉得这个太没难度了，而且这个不用递归也可以做出来  而且不用递归还好做一些 ...


嗯，你说得很有道理！递归空间复杂度、时间复杂度都比较大。很多时候如果用非递归的可以做出来，当然就非递归更优。但很多时候程序的结束点是未知的，循环次数也不能确定，此时恐怕只能用递归，比如说此题的第二问
作者: 丁二跃    时间: 2012-7-13 23:26
蒋映辉 发表于 2012-7-13 23:14
嗯  其实我也想出这个的，后来觉得这个太没难度了，而且这个不用递归也可以做出来  而且不用递归还好做一些 ...

递归确实太耗时了 ，你出的那个汉诺塔的 运行了2个多小时，输出的文本记录1300多个 8G 多 ，还没运行完
作者: 周刚    时间: 2012-7-13 23:27
丁二跃 发表于 2012-7-13 23:26
递归确实太耗时了 ，你出的那个汉诺塔的 运行了2个多小时，输出的文本记录1300多个 8G 多 ，还没运行完
...

不会吧，这么夸张？！两个多小时，哥们真可以。你把层数设成了多少？
作者: 许瑞航老师    时间: 2012-7-13 23:29
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:34
许瑞航 发表于 2012-7-13 23:29
public class Test
{
    public int compute(int a)

果然是这么回事、我还是回去老实的看视频吧、
作者: 丁二跃    时间: 2012-7-13 23:39
周刚 发表于 2012-7-13 23:27
不会吧，这么夸张？！两个多小时，哥们真可以。你把层数设成了多少？

64 ………… 一直在跑着:(
作者: 韦念欣    时间: 2012-7-13 23:45
使用动态规划，这样快一些，时间复杂度也比较小。
作者: 周刚    时间: 2012-7-13 23:46
丁二跃 发表于 2012-7-13 23:39
64 ………… 一直在跑着

呵呵，这是个问题，我设成20，共移动了1048575次。
作者: 温少邦    时间: 2012-7-13 23:48
求项数也能不用递归吧，从头求各项，然后判断就可以了

  2. public class Fibonacci{
  3.         private static int[] add=new int[100];
  4.         private static int pos=0;
  5.         public static int getPos(int i){
  6.                 if(i<2)
  7.                         return -1;
  8.                 add[0]=1;
  9.                 add[1]=1;
  10.                 pos=1;
  11.                 while(i-add[pos]>0){
  12.                         pos++;
  13.                         add[pos]=add[pos-1]+add[pos-2];
  14.                 }
  15.                 if(i-add[pos]==0)
  16.                         return pos;
  17.                 else
  18.                         return -1;
  19.         }
  20.         public static void main(String[] args){
  21.                 System.out.println(getPos(102334155));
  22.         }
  23. }
复制代码
作者: 黑马振鹏    时间: 2012-7-13 23:58
算法没问题 关键是第100项到底是什么数字呢，应该用什么类型来存储？
作者: 周刚    时间: 2012-7-13 23:58
温少邦 发表于 2012-7-13 23:48
求项数也能不用递归吧，从头求各项，然后判断就可以了


嗯，兄弟很有才！思路很活跃，建议加分！
作者: 周刚    时间: 2012-7-14 00:00
黑马振鹏 发表于 2012-7-13 23:58
算法没问题 关键是第100项到底是什么数字呢，应该用什么类型来存储？

哦，sorry我随便写的，100项可能太大了，可能Long都不能表示，那用BigDecimal不知道可否？
作者: 游兴钟    时间: 2012-7-14 00:05
周刚 发表于 2012-7-14 00:00
哦，sorry我随便写的，100项可能太大了，可能Long都不能表示，那用BigDecimal不知道可否？ ...

....................
作者: 贾飞雨    时间: 2012-7-14 01:21
发现第一个弄了好久第一百项却没有弄出来，所以就先把第二个发上来了
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:23
在网上搜索了一下，发现有一篇类似的帖子，不过求的结果是前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  
作者: 游兴钟    时间: 2012-7-14 03:23
yufeiant 发表于 2012-7-14 01:23
在网上搜索了一下，发现有一篇类似的帖子，不过求的结果是前100项的和，厚颜学习，改进了一下，哎，结果可 ...

你都肯承认是搜的还厚颜?真正厚颜的是那些直接百度来答案 改改骗分的人 呵呵
作者: 蒋映辉    时间: 2012-7-14 06:52
achilles 发表于 2012-7-14 03:23
你都肯承认是搜的还厚颜?真正厚颜的是那些直接百度来答案 改改骗分的人 呵呵 ...

嗯  这位哥们儿正解..
作者: 李思静    时间: 2012-7-14 09:18
  1. //我的算法就是在第一个地方补上0，可能跟别的有点不一样
  2. class Test  {
  3.   

  5.     public static int no=1;


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

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

QQ拼音截图未命名.png
作者: 陈冲    时间: 2012-7-14 09:24
本帖最后由 陈冲 于 2012-7-14 09:43 编辑

昨天晚上睡觉前写的，刚开始学，很多东西都不会，有写的不对的地方，请大家帮忙给指出来
试着运行了一下，递归方法求求斐波那锲数列的时候速度真慢……
  1. /*递归方式求斐波那锲数列*/
  2. class Test
  3. {
  4.     public static void main(String[] args)
  5.     {
  6.         int n=100;
  7.         pringFib(n);
  8.     }

  10.     public static double Fib(int n)
  11.     {
  12.         if(n>2)
  13.         {
  14.             return Fib(n-2)+Fib(n-1);
  15.         }
  16.         else
  17.         {
  18.             return 1;
  19.         }
  20.     }
  21.     public static void pringFib(int n)
  22.     {
  23.         for(int x=1;x<=n;x++)
  24.             if(x!=n)
  25.         {
  26.                 System.out.print(Fib(x)+"    ");
  27.                 if(x%5==0)
  28.                     System.out.println();
  29.         }
  30.             else
  31.                 System.out.print(Fib(x));
  32.         System.out.println();
  33.     }
  34. }
复制代码
  1. /*循环方式求斐波那锲数列*/
  2. class Test
  3. {
  4.     public static void main(String[] args)
  5.     {
  6.         printFib(100);
  7.     }
  8.     public static double[] Fib(double[] arr)
  9.     {
  10.         arr[0]=1;
  11.         arr[1]=1;
  12.         for (int i = 2; i < arr.length; i++) {
  13.             arr[i]=arr[i-2]+arr[i-1];
  14.         }
  15.         return arr;
  16.         
  17.     }
  18.     public static void printFib(int n)
  19.     {
  20.         double[] arr=new double[n];
  21.         Fib(arr);
  22.         for (int i = 0; i < arr.length; i++) {
  23.             if(i!=arr.length-1)
  24.                 System.out.print(arr[i]+"    ");
  25.             else
  26.                 System.out.println(arr[i]);
  27.             if((i+1)%5==0)
  28.                 System.out.println();
  29.         }        
  30.     }
  31. }
复制代码
作者: 何旭栋    时间: 2012-7-14 09:52
  1. class demo {
  2.         public static void main(String[] args) {
  3.                 int n = IndexOf(102334155);
  4.                 System.out.println(n);
  5.                 System.out.println(feibo(n));
  6.         }

  8.         public static int feibo(int num){
  9.                 if(num==1||num==2)
  10.                         return 1;
  11.                
  12.                 return feibo(num-2)+feibo(num-1);
  13.         }

  15.         public static int IndexOf(int num){
  16.                 int sum = 1;
  17.                 int last = 1;
  18.                 int temp;

  20.                 int i = 2;
  21.                 while(true){
  22.                         temp = sum;
  23.                         sum += last;
  24.                         last = temp;
  25.                         i++;
  26.                         if (num <= sum)
  27.                         {
  28.                                 return i;
  29.                         }
  30.                 }
  31.         }
  32. }
复制代码
还是循环省事啊
作者: 韩伟    时间: 2012-7-14 10:52
小弟刚学不久，功力不够深厚，但为了能得分也只好献丑了。
一般情况下能用循环解决问题的，都不建议用递归，根据问题要求，我用while循环写了两个函数，并且已经在我机子上运行
class Num
{
        public static long getNum(int n)
        {
                long [] num = new long [n];
                if(n<=2)
                {
                        return 1;
                }
                num[0] = 1;
                num[1] = 1;
                int i = 2;
                while(i<n)
                {
                        num[i] = num[i-1] + num[i-2];
                        i++;
                }
                return num[i-1];
        }
       
        public static int getIndex(long num)
        {
               
                long arr [] = new long[200] ;
                if(num<2)
                {
                        return 1;
                }
                arr[0] = 1;
                arr[1] = 2;
                int n=2;
                do
                {
                        arr[n] = arr[n-1] + arr[n-2];
                        n++;
                }while (arr[n-1]<num);
                if(arr[n -1] == num)
                   return n;
                else
                {
                        System.out.println(num+"不是数列中的元素");
                        return 0;
                }
        }
                public static void main(String args[])
                {
                        long i = getNum(100);
                        int j = getIndex(102334155L);
                        System.out.println("i="+i);
                        System.out.println("j="+j);
                }
       
}
都与LZ提到的第二个问题，也很简单，只要判断每一项的值是否小于给定的数就行了，如果不小于就只有两种情况，要么等于，那么返回下标就行了，如果不等于，那么就说明该数在数列中不存在.
作者: 位雪    时间: 2012-7-14 12:53

复制代码

无标题.png (291.84 KB, 下载次数: 29)

无标题.png




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