Fibonacci, limpahan integer, hafalan dan exagero

Jom buat senaman.
Di bawah saya tinggalkan kod yang mengembalikan nombor dalam kedudukan n jujukan Fibonacci:

public static int fib(int n){
   if (n <= 1){
     return n;
   }
   return fib(n-1) + fib(n-2);
}

Bagaimana kalau kita cuba tunjukkan dalam terminal kita semua nombor dalam jujukan Fibonacci yang lebih kecil daripada 2147483647?

    public static int fib(int n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int position = 1;
        int currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Masalahnya

Apabila menjalankan kod, anda akan melihat dua masalah utama:

• Gelung kami tidak pernah berakhir dan, anehnya, nombor negatif mula muncul dalam konsol.
  

• Kod semakin perlahan dan semakin perlahan apabila masa berlalu.

Masalah 1: Nombor negatif

Abaikan semua bahan Fibonacci ini seketika dan lihat kod ini.

public static void main(String[] args) {
   int a = 2_000_000_000;
   int b = 2_000_000_000;
   System.out.println(a + b);
}

Pada pendapat anda, berapakah hasil daripada ini? 2 bilion 2 bilion = 4 bilion bukan? Jadi dalam kod kami hasilnya akan menjadi 4 bilion... betul?

SALAH!

Jalan keluar sebenarnya ialah:

Sebab hasil ini melimpah. Jenis int mempunyai had maksimum 2147483647 (atau 2^31 - 1). Apabila had ini melebihi, nilai "kembali" kepada nilai jenis int yang paling rendah, iaitu -2147483648.

Mengapa gelung kami tidak berhenti?

Gelung kami sepatutnya berhenti apabila kami mencapai nombor yang lebih besar daripada atau sama dengan 2147483647, tetapi apabila nilai Fibonacci melebihi had int, nombor negatif mula dijana. Memandangkan kami tidak pernah mencapai nombor yang lebih besar daripada 2147483647, gelung itu tidak pernah berhenti.

Penyelesaian masalah 1

Untuk memastikan perkara mudah, saya hanya akan menukar jenis pemulangan fungsi fib kami daripada int kepada long yang mempunyai had yang lebih besar. Kod kami akan kelihatan seperti ini:

    public static long fib(long n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Kini, dengan jenis yang panjang, kita boleh mencetak nombor Fibonacci dengan betul sehingga nombor terbesar yang lebih kecil daripada 2147483647.

Menyelesaikan masalah 2: kelambatan

Awak dah perasan sesuatu belum? Setiap lelaran gelung kami, fungsi fib mengira semula semua nombor sebelumnya dalam jujukan. Dalam erti kata lain, kami mengulangi pengiraan yang tidak perlu.

Bagaimana untuk mengelakkan pengiraan semula yang tidak perlu? Saya mempersembahkan kepada anda: Menghafal. Teknik hafalan ialah cara menyimpan hasil yang telah dikira supaya tidak melalui proses pengiraan lagi.

Mari laksanakan HashMap untuk menyimpan nilai yang telah ditemui, di mana kuncinya ialah kedudukan dan nilainya ialah nombor itu sendiri.

    static HashMap<Long, Long> memo = new HashMap<>();

    public static long fib(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 1) {
            return n;
        }
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Cantik! Kini kod kami berjalan lebih pantas dan kami menyelesaikan masalah kami.

keterlaluan

Sebenarnya, hafalan tidak diperlukan di sini. Saya hanya mahu membawa konsep ini untuk mengajar. Kami hanya boleh mengira setiap nombor Fibonacci sehingga kami menyelesaikan keadaan kami seperti ini:

    public static void main(String[] args) {
        long prev1 = 0;
        long prev2 = 1;
        long current;

        System.out.println(prev1);

        while (prev2 < 2147483647) {
            System.out.println(prev2);
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
    }

Saya sudah selesai dengan keseronokan, bukan? Maaf! Tetapi sekurang-kurangnya anda belajar sesuatu yang baru.

---

Kulit artikel oleh: Gerd Altmann daripada Pixabay

Atas ialah kandungan terperinci Fibonacci, limpahan integer, hafalan dan exagero. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!