5

私はフィボナッチ数列のN番目の数を決定するための「単純な」プログラムを書いています。例：シーケンスの7番目の数字は次のとおりです。13。プログラムの作成が終了しましたが、動作しますが、40番目の数字から遅延が始まり、時間がかかります。私のプログラムはシリーズの100番目の場所に行かなければなりません。

これを修正して、それほど時間がかからないようにするにはどうすればよいですか？これは非常に基本的なプログラムなので、すべての凝った構文コードを知っているわけではありません。私の式は次のとおりです。

if n =1 || n = 0
   return n;

else 
    return F(n-1) + F(n-2);

これは、40期を過ぎるまでうまく機能します。数字が大きいほど速くなるために、他にどのようなステートメントを追加する必要がありますか？

4

15 に答える 15

10

問題は、単純な再帰を使用しているため、F（n）を複数回再評価し、実行時間が指数関数的になることです。

これを修正する簡単な方法は2つあります。

1）F（n）の値を最初に評価するときにキャッシュします。F（n）を評価する前に、まずキャッシュをチェックして、このnに対してすでにキャッシュを計算しているかどうかを確認します。

2）反復アプローチを使用します。必要な数に達するまで、F（1）、F（2）、F（3）などを計算します。

于 2009-11-25T21:17:32.610 に答える
7

問題は、数学的に純粋な（そして素晴らしい）アルゴリズムがあまり良くないことです。
計算するすべての数値について、2 つの低い数値を計算し、次に 2 つの低い数値を計算する必要があります。現在のアルゴリズムのBig O 表記の複雑さは約O(1.6 n )であるため、非常に大きな数値の場合 ( 100 など) 時間がかかります。

この本、Structure and Interpretation of Computer programs には素晴らしい図fib 5があります: アルゴリズムで生成すると何が起こるかを示しています(出典: mit.edu )

最も簡単な方法は、F - 1 と F - 2 を保存して、毎回最初から計算する必要がないようにすることです。つまり、再帰を使用するのではなく、ループを使用します。これは、アルゴリズムの複雑さが O(1.6 n ) から O(n) になることを意味します。

于 2009-11-25T21:20:59.670 に答える
6

いくつかの解決策があります。最も簡単なのは、メモ化を使用することです。定数時間でn番目のフィボナッチ数を与えるBinetの式もあります。

メモ化のために、F[a_i]の結果をマップまたはある種のリストに保存します。単純な再帰では、たとえば、F[4]を数十万回計算します。これらすべての結果を見つけたときに保存することにより、再帰はツリーのように進行しなくなり、単純な反復ソリューションのように見えます。

これが宿題でない場合は、Binetの式を使用してください。これは、利用可能な最速の方法です。

于 2009-11-25T21:15:57.980 に答える
5

この例を試してみてください。精度を損なうことなく、適切な時間枠で 100 万番目のフィボナッチ数を計算します。

import java.math.BigInteger;

/*
250000th fib # is: 36356117010939561826426 .... 10243516470957309231046875
Time to compute: 3.5 seconds.
1000000th fib # is: 1953282128707757731632 .... 93411568996526838242546875
Time to compute: 58.1 seconds.
*/
public class Fib {
    public static void main(String... args) {
        int place = args.length > 0 ? Integer.parseInt(args[0]) : 1000 * 1000;
        long start = System.nanoTime();
        BigInteger fibNumber = fib(place);
        long time = System.nanoTime() - start;

        System.out.println(place + "th fib # is: " + fibNumber);
        System.out.printf("Time to compute: %5.1f seconds.%n", time / 1.0e9);
    }

    private static BigInteger fib(int place) {
        BigInteger a = new BigInteger("0");
        BigInteger b = new BigInteger("1");
        while (place-- > 1) {
            BigInteger t = b;
            b = a.add(b);
            a = t;
        }
        return b;
    }
}
于 2009-11-25T21:38:38.390 に答える
2

100 個の値を持つ配列を作成し、Fib(n) の値を計算するときに、それを配列に格納し、その配列を使用して Fib(n-1) と Fib(n-2) の値を取得します。

以前に計算された値を保存せずに Fib(100) を呼び出すと、Java ランタイムが爆発します。

擬似コード:

array[0] = 0;
array[1] = 1;
for 2:100
array[n] = array[n-1] + array[n-2];
于 2009-11-25T21:20:13.247 に答える
1

問題はJAVAではなく、フィボナッチアルゴリズムの実装方法です。同じ値を何度も計算しているため、プログラムの速度が低下しています。

次のようなものを試してください：メモ化されたフィボナッチ

于 2009-11-25T21:18:04.853 に答える
0

遅すぎる...

より良い:(JavaScriptの例）

function fibonacci(n) {
    var a = 0, b = 1;

    for (var i = 0; i < n; i++) {
        a += b;
        b = a - b;
    }
    return a;
}
于 2011-10-03T20:55:27.070 に答える
0

三項演算子の複数のステートメントで見栄えがします。

static int fib(int n) {
        return  n > 5 ? fib(n-2) + fib(n-1)
                      : n < 2 || n == 5 ? n
                                        : n - 1;
}
于 2016-01-30T21:46:04.837 に答える
0

単純なアプローチを使用すると、同じ計算が爆発的に増えることになります。つまり、fib(n) を計算するには、fib(n-1) と fib(n-2) を計算する必要があります。次に、fib(n-1) を計算するには、fib(n-2) と fib(n-3) などを計算する必要があります。より良いアプローチは、逆を行うことです。fib(0)、fib(1)、fib(2) から計算を開始し、値をテーブルに格納します。次に、テーブル (配列) に格納されている値を使用して後続の値を計算します。これはメモ化とも呼ばれます。これを試してみると、大きな fib 数を計算できるはずです。

于 2009-11-25T21:19:56.850 に答える
0

単純な実装は自然で洗練されていますが、実行中に再帰呼び出しによってバイナリ ツリーが作成されます。前述のメモ化、以前の F(n) 結果のキャッシュ、不要なツリー トラバーサルの回避に加えて、前述の反復または行列乗算のテール コールの最適化を行うことができます。たとえば、Java 8 メモ化:

private static final Map<Long, Long> memo = new HashMap<>();
static {
  memo.put(0L, 0L);
  memo.put(1L, 1L);
}
public static void main(String[] args) {
  System.out.println(fibonacci(0));
  System.out.println(fibonacci(43));
  System.out.println(fibonacci(92));
}
public static long fibonacci(long n) {
  return memo.computeIfAbsent(n, m -> fibonacci(m - 1) + fibonacci(m - 2));
}

または、テールコール最適化バージョン:

interface FewArgs<T, U, V, R> {
  public R apply(T t, U u, V v);
}

static FewArgs<Long, Long, Long, Long> tailRecursive;

static {
  tailRecursive = (a, b, n) -> {
    if (n > 0)
      return tailRecursive.apply(b, a + b, n - 1);
    return a;
  };
}

a = 0、b = 1 で呼び出します。n は n 番目のフィボナッチ数である必要がありますが、93 より小さい必要があります。フィボナッチ数を計算するより効率的な方法は行列の二乗です。

于 2015-05-16T03:54:34.893 に答える
0

これは Python のコードで、C/Java に簡単に変換できます。1 つ目は再帰的で、2 つ目は反復ソリューションです。

def fibo(n, i=1, s=1, s_1=0):
    if n <= i: return s
    else: return fibo(n, i+1, s+s_1, s)


def fibo_iter_code(n):
    s, s_1 = 1, 0
    for i in range(n-1):
       temp = s
       s, s_1 = s+s_1, temp
       print(s)
于 2010-03-05T20:37:18.357 に答える
0 
import java.util.*;
public class FibonacciNumber
{

  public static void main(String[] args)
  {
    int high = 1, low = 1;
    int num;
    Scanner in = new Scanner(System.in);
    try
    {
      System.out.print("Enter Number : " );
      num = in.nextInt(); 
      System.out.println( low);
      while(high < num && num < 2000000000)
      {
        System.out.println(high);
        high = low + high;
        low = high - low;
      }
     } catch (InputMismatchException e) {
       System.out.print("Limit Exceeded");
     }
   }
}

/* Ouput : 
Enter Number : 1999999999
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863
-1109825406
-1408458269
 1776683621
 368225352   */
于 2014-09-19T12:50:53.063 に答える