23
Сен
2014

Найти время подсчета каждого числа Фибоначчи заданного индекса

Дан рекурсивный алгоритм вычисления чисел Фибоначчи. Задача состоит в том, чтобы найти время подсчета каждого числа Фибоначчи заданного индекса.
После 40 программа начинает виснуть. Как подсчитать время для больших индексов?
(Задача была до 100 посчитать время в секундах, больше 100 или 100 в годах.)

public class ulesanne3 {
    public static void main(String[] args) {
        try{
            /**
             * open input file
             */
            BufferedReader in = new BufferedReader 
                    (new FileReader ("./src/kodtoo1/kodtoo1.in"));

            /**
             * open output file
             */
            PrintWriter out = new PrintWriter("./src/kodtoo1/kodtoo1.out");

            /**
            * String , where we write .in information.
            */
            String s;

            /**
            * Read information from input file by lines.
            */
            while((s=in.readLine())!=null){

            /**
             * Convert information from string to int.
             */
            int n = Integer.parseInt(s);

                /**
                 * fib_time algorithm
                 */
                fib_time(n);

                 /**
                 * print result to the file
                 */
                out.println(fib_time(n));
                /**
                 * print result to the console.
                 */
                System.out.println(fib_time(n));

            }   
            /**
             * close in and out file
             */
                in.close();
                out.close();

            }   
            /**
             * exception if we don't find  file kodtoo1.in
             */
            catch (IOException e ){
                System.out.println("No file!"); 
            }

    }

/**
 * fib_time
 * @param n
 * @return
 */
public static String fib_time(int n){
    double timeSpent,start ;

    /**
     * Time starts in nanoseconds 
     */
    start = System.nanoTime();

       fib(n);
    /**
     * delta = end time - start time
     */
    timeSpent =( System.nanoTime() - start);

    String result = "";
    /**
     * if n is smaller than 100 , make time in a seconds
     */
    if (n<100){
        double Time = timeSpent/1000000000;
        result  = "Spent time:" + Time +   "  seconds" ;
    }
    /**
     * if n is bigger than 100 or its 100 , make time in years
     */
    if(n>=100){
        double Time = timeSpent/1000000000;
        result ="Spent time:" + Time +   "  years";
    }

/**
 * Strings
 */

 String index = "index:" +n;
 String fibonacci = "Fibonacci:" + fib(n);
 String total = result +"\n" + index + "\n"+ fibonacci +"\n";

return total;
}

/**
 * fibonacci 
 * @param n
 * @return
 */
public static int fib(int n)
{

    if( n <= 2) return 1;
    else return fib(n-1) + fib(n-2);

}
}

Источник: https://ru.stackoverflow.com/questions/362784/%D0%9D%D0%B0%D0%B9%D1%82%D0%B8-%D0%B2%D1%80%D0%B5%D0%BC%D1%8F-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%B0-%D0%BA%D0%B0%D0%B6%D0%B4%D0%BE%D0%B3%D0%BE-%D1%87%D0%B8%D1%81%D0%BB%D0%B0-%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8-%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0

Share

Тебе может это понравится...