[JAVA] Finden Sie die Fibonacci-Nummer mit dem Fork / Join Framework

Lassen Sie uns die Fibonacci-Nummer mit dem Fork / Join Framework finden.

Was ist die Fibonacci-Nummer?

[Anzahl der Fibonacci-Wikipedia](https://ja.wikipedia.org/wiki/Number of Fibonacci)

Die Fibonacci-Nummer (Fibonacci-Nummer) ist nach dem italienischen Mathematiker Leonardo Fibonacci (Pisa Leonardo) benannt.

Finden Sie die Fibonacci-Nummer

Wenn die $ n $ -te Fibonacci-Zahl durch $ F_n $ dargestellt wird, ist $ F_n $ rekursiv

$ F_0 = 0 $ $ F_1 = 1 $ $ F_{n+2} = F_n + F_{n+1}\quad(n\geqq1) $

Definiert in.

FibonacciTask.java

import java.util.concurrent.RecursiveTask;

public class FibonacciTask extends RecursiveTask<Integer> {
    private final int n;

    FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    protected Integer compute() {
        if (n <= 1) {
            //Wenn n 0 oder 1 ist, kehren Sie unverändert zurück
            return n;
        }

        // n-Finden Sie die Fibonacci-Nummer für 1
        FibonacciTask f1 = new FibonacciTask(n - 1);
        f1.fork();

        // n-Finden Sie die Fibonacci-Nummer für 2
        FibonacciTask f2 = new FibonacciTask(n - 2);

        //Addieren Sie die Verarbeitungsergebnisse, um die Fibonacci-Zahl von n zu erhalten
        return f2.compute() + f1.join();
    }
}

Main.java

import java.util.concurrent.ForkJoinPool;

public class Main {
    public static void main(String[] args) {
        ForkJoinPool pool = new ForkJoinPool();
        for (int n = 0; n < 40; n++) {
            int result = pool.invoke(new FibonacciTask(n));
            System.out.println("F[" + n + "]:" + result);
        }
    }
}

Ich werde das machen.

$ java Main
F[0]:0
F[1]:1
F[2]:1
F[3]:2
F[4]:3
F[5]:5
F[6]:8
F[7]:13
F[8]:21
F[9]:34
F[10]:55
F[11]:89
F[12]:144
F[13]:233
F[14]:377
F[15]:610
F[16]:987
F[17]:1597
F[18]:2584
F[19]:4181
F[20]:6765
F[21]:10946
F[22]:17711
F[23]:28657
F[24]:46368
F[25]:75025
F[26]:121393
F[27]:196418
F[28]:317811
F[29]:514229
F[30]:832040
F[31]:1346269
F[32]:2178309
F[33]:3524578
F[34]:5702887
F[35]:9227465
F[36]:14930352
F[37]:24157817
F[38]:39088169
F[39]:63245986

Es ist langsam, also notieren Sie es sich.

FibonacciTask.java

import java.util.concurrent.RecursiveTask;
import java.util.Map;
import java.util.HashMap;

public class FibonacciTask extends RecursiveTask<Integer> {
    private final int n;

    private static Map<Integer, Integer> sequence = new HashMap<>();

    static {
        sequence.put(0, 0);
        sequence.put(1, 1);
    }

    FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    protected Integer compute() {
        return sequence.computeIfAbsent(this.n, x -> fibonacci(this.n));
    }

    private static Integer fibonacci(int n) {
        // n-Finden Sie die Fibonacci-Nummer für 1
        FibonacciTask f1 = new FibonacciTask(n - 1);
        f1.fork();

        // n-Finden Sie die Fibonacci-Nummer für 2
        FibonacciTask f2 = new FibonacciTask(n - 2);

        //Addieren Sie die Verarbeitungsergebnisse, um die Fibonacci-Zahl von n zu erhalten
        return f2.compute() + f1.join();
    }
}