黑马程序员技术交流社区

标题: 斐波那契数列死锁 [打印本页]
作者: 潜行的羔羊    时间: 2015-9-8 14:03
标题: 斐波那契数列死锁
直接上代码：
import java.io.*;
class test4
{
        public static void main(String[] args) throws Exception
        {

               
                long[] arr=new long[30];

                System.out.print("please input n:");

               
       

                InputStreamReader bur=new InputStreamReader(System.in);
                int n=(int)bur.read();
               

                int num=fun(n);

                System.out.print("answer is"+ num);
        }
                public static int fun(int n)
                        {
               
                if (n==1|n==2)
                return 1;
                else
                return fun(n-1)+fun(n-2);
               
                        }
}

程序编译没问题  ，但是死锁，何解？？
作者: MilesMatheson    时间: 2015-9-8 14:45
我只听说在多线程里面有死锁，这个哪里来的死锁捏？？
作者: 潜行的羔羊    时间: 2015-9-8 15:34
是锁死。。。运行没反应
作者: lion_good    时间: 2015-9-8 15:55
首先 , InputStreamReader.read() 只能读取一个字符 , 要读取一个整数,可以使用java.util.Scanner.
  1. import java.io.InputStreamReader;
  2. import java.util.Scanner;
  3. public class Test4 {
  4.     public static void main(String[] args) throws Exception {
  5.         System.out.print("please input n:");
  6.         InputStreamReader bur = new InputStreamReader(System.in);
  7.         Scanner scanner=new Scanner(bur);
  8.         int n = scanner.nextInt();
  9.         int num = fun(n);
  10.         System.out.print("answer is " + num);
  11.     }
  12.     public static int fun(int n) {
  13.         if (n == 1 || n == 2)
  14.             return 1;
  15.         else
  16.             return fun(n - 1) + fun(n - 2);
  17.     }
  18. }
复制代码


然后,这种斐波那契数列的算法,只是定义算法,只能用来计算斐波那契数列的前面几项,其运行时间是成指数型增长的,当n=50时就要算半天了,另外斐波那契数列的数值增长速度是非常快的,用int来存储数值太小了.下面提供了一种解决方案:
  1. import java.math.BigInteger;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. public class Test4 {
  5.     private static List<BigInteger> results;//将中间结果存储起来
  6.     static {
  7.         //初始化 results
  8.         results = new ArrayList<>();
  9.         results.add(new BigInteger("0"));
  10.         results.add(new BigInteger("1"));
  11.     }
  12.     public static void main(String[] args) throws Exception {
  13.         for (int i =1000 ; i<2000 ;++i)
  14.             System.out.println(fun(i));
  15.     }
  16.     public static BigInteger fun(int n) {
  17.         //如果所求的数在results中直接返回
  18.         if (n < results.size())
  19.             return results.get(n);
  20.         else {
  21.             for (int i = results.size(); i < n + 1; ++i)
  22.                 results.add(results.get(i - 1).add(results.get(i - 2)));
  23.             return results.get(n);
  24.         }
  25.     }
  26. }
复制代码

计算一千,一万,一亿都是秒杀啊 ,当然用 斐波那契数列的数学公式更快哈(请找百度)
作者: 潜行的羔羊    时间: 2015-9-8 17:38
lion_good 发表于 2015-9-8 15:55
首先 , InputStreamReader.read() 只能读取一个字符 , 要读取一个整数,可以使用java.util.Scanner.

了解了解  多谢多谢~~



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