3

システムに表示できる最大のフィボナッチ数を計算するように求められます。それについてどうやって行くのか考えていますか？

4

4 に答える 4

7

システムに表示できる最大のフィボナッチ数を決定します

そのためにはBigIntegerを使用する必要があります

リソースが不足したためにアプリケーションが停止するまで、これを実行します。

public static void main(String... args) {
    BigInteger a = BigInteger.ONE;
    BigInteger b = BigInteger.ONE;
    String last = null;
    try {
        for (long count = 1; ; count++) {
            BigInteger c = a.add(b);
            last = c.toString();
            a = b;
            b = c;
            if (count % 10000 == 0)
                System.out.println("... " + count);
        }
    } catch (Throwable e) {
        System.out.println("The largest value which was calculated was");
        System.out.println(last);
    }
}

最初は少量のメモリで試してみます。-mx16m

更新：16 MBの制限があっても、13Kの用語を計算し、実行されています。

于 2012-11-21T12:33:59.617 に答える
5

intJavaで最大のフィボナッチ数：

public class FibonacciTest
{
    public static void main(String[] args)
    {
        System.out.printf("%d\n", largestFibonacciInt());
    }

    public static int largestFibonacciInt()
    {
        int temp;
        int last = 1;
        int fib = 1;

        while (fib + last > fib) {
            temp = fib;
            fib += last;
            last = temp;
        }

        return fib;
    }
}

longのすべての出現箇所を置き換えるだけで、これをで行うこともできますint。

于 2012-11-21T12:22:29.687 に答える
2

Javaで表現できる最大のフィボナッチ数を見つけることが目標である場合は、intオーバーフローするまで次の数を計算するだけです。

public static void main(String[] args) {
    System.out.println("Largest integer Fibonacci number: " + maxFibonacci());
}

public static int maxFibonacci() {
    int n = Integer.MAX_VALUE;
    int fib = 1;
    int temp = 0;

    for (int i = 2; i < n; i++) {
        int last = fib;
        fib += temp;
        if (fib < 0) return last; //overflow, we are done
        temp = last;
    }
    return 0; //unreachable
}

これで明らかに、システムは、たとえばBigIntegerを使用して、はるかに高い数値を計算できるようになります。そのシナリオでは、制限は次のいずれかになります。

  • 処理時間
  • 使用可能なメモリまたは
  • （メモリと時間がたくさんある場合）BigIntegerの制限。これは、によってサポートされているint[]ため、2^31の配列サイズに制限されます。

最後に、あなたの問題は数学的にもっとよく解決できると言う価値があるでしょう。

特定の数よりも小さい最大のフィボナッチ数を見つける必要がある場合は、丸め計算Nを使用することもできます。

phi^n / sqrt(5) < N

それはあなたに与えます：

n < log(N x sqrt(5)) / log(phi)

次に、選択した右側の部分を計算Nし、それを切り捨てて見つけn、対応するフィボナッチ数を次のように計算できます。

F(n) = floor(phi^n / sqrt(5))
于 2012-11-21T12:18:49.707 に答える
0

100K以上で計算できます。私のコンピューターの100kの場合、結果の計算には1.4秒しかかかりません。

private static final Map<Integer, BigInteger> fbNumbers = new HashMap<>();

public static void main(String[] args) {
    fbNumbers.put(0, BigInteger.valueOf(1));
    fbNumbers.put(1, BigInteger.valueOf(1));
    long start = System.currentTimeMillis();
    System.out.println(fbCalculationForBigNumbers(100000));
    System.out.println(String.format("%d ms", System.currentTimeMillis() - start));
}

private static BigInteger fbCalculationForBigNumbers(int num) {
    return IntStream.rangeClosed(0, num).mapToObj(i -> fbCalculation(i)).max((x,y) -> x.compareTo(y)).get();
}

private static BigInteger fbCalculation(int num) {

    if (fbNumbers.containsKey(num)) {
        return fbNumbers.get(num);
    }

    BigInteger result = fbCalculation(num - 1).add(fbCalculation(num - 2));
    fbNumbers.put(num, result);
    return result;

}
于 2017-03-28T20:09:45.237 に答える