Apa yang harus diketahui oleh seorang programmer Java tentang angka Fibonacci

Seringkali selama wawancara, terutama di perusahaan asing, orang mungkin ditanya tentang algoritma, dan dalam situasi stres, mengingat sesuatu dengan panik tidak selalu mudah. Oleh karena itu, Anda perlu bersiap. Untuk memulainya, setidaknya segarkan ingatan Anda tentang algoritma dasar. Hari ini kita akan menganalisis fenomena seperti bilangan Fibonacci dan varian paling umum dari soal yang terkait dengannya. Bilangan Fibonacci adalah barisan bilangan asli yang diawali dengan bilangan nol dan satu, dan setiap bilangan berikutnya sama dengan jumlah dua bilangan sebelumnya: F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F ₀ = 0, F ₁ = 1, F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0, n ∈ Z

Perlu dicatat bahwa terkadang 0 dihilangkan, dan deret dimulai dengan 1 1 2 3... Sebagai aturan, dalam kondisi soal segera ditentukan dua angka pertama mana yang dimulai dengan deret tersebut (0,1 atau 1,1), jadi selanjutnya kami akan mempertimbangkan solusi untuk kedua kasus tersebut.

Mendapatkan n angka Fibonacci pertama di Java

Misalkan kita mempunyai tugas untuk mendapatkan n bilangan Fibonacci pertama.

• kasus 0.1:

  Sejumlah n tertentu datang kepada kita:

  int[] arr = new int[n];
  arr[0] = 0;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  Kami membuat array ukuran n. Dua elemen pertama akan sama dengan nol dan satu, dan elemen lainnya diperoleh dengan melalui loop ini dan menggunakan angka sebelumnya dari array.

  Dan kami menampilkan:

  for (int i = 0; i < arr.length; ++i) {
    System.out.println(arr[i]);
  }

  Tetapkan int n = 10;

  Dan kami mendapatkan:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• untuk kasus 1.1 solusinya sebenarnya tidak berbeda:

  int[] arr = new int[n];
  arr[0] = 1;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  Yang perlu kita ubah hanyalah elemen pertama array arr[0]: dari 0 ke 1. Oleh karena itu, 10 elemen pertama adalah:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

n angka Fibonacci pertama melalui aliran

Namun kami ingin menunjukkan level kami. Jadi mari kita lihat seperti apa solusi ini menggunakan stream .

• untuk 0,1:

  Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));

  Metode iterasi statis dari kelas Stream mengembalikan aliran terurut tak terbatas yang dibuat dengan menerapkan fungsi ke arr array awal. Dalam kasus kita, fungsinya adalah untuk menetapkan aturan untuk menyusun setiap larik baru, berdasarkan larik sebelumnya. Hasilnya, kita akan mendapatkan aliran array:

  {0,1}
  {1,1}
  {1, 2}
  {2, 3}
  {3, 5}
  {5, 8}
  {8, 13}
  {13, 21}
  {21, 34}
  {34, 55}
  …..

  Namun jumlahnya tidak terhingga, dan oleh karena itu dengan menggunakan .limit(n) kita mengurangi jumlah elemen menjadi n pertama (dalam kasus kita menjadi 10).

  Namun, kita tidak memerlukan aliran array, jadi menggunakan .map(y -> y[0]) kita memilih elemen pertama dari setiap array dan mendapatkan aliran dengan nomor yang kita perlukan dan mencetaknya ke konsol menggunakan forEach .

  Terlihat lebih keren, bukan?

  dengan elemen pertama adalah 1,1 kode ini juga akan hampir sama:

  Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(y -> y[0])
       .forEach(x -> System.out.println(x));

  Sekali lagi, perbedaannya terletak pada elemen awal: alih-alih {0, 1} kita menetapkan {1, 1}

  Sebenarnya hasilnya akan sama seperti pada contoh sebelumnya.

Jumlah angka Fibonacci

Bagaimana jika kita diminta untuk menjumlahkan angka-angka Fibonacci hingga elemen ke-n inklusif? Hal ini seharusnya tidak menimbulkan kesulitan bagi kita. Mari kita ambil solusi dengan aliran dan ganti forEach dengan beberapa metode lain:

• untuk 0,1:

  int n = 10;
  int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(t -> t[0])
       .mapToInt(Integer::intValue)
       .sum();
  System.out.println(result);

  Dengan menggunakan .mapToInt(Integer::intValue) kami mengonversi aliran kami menjadi IntStream numerik dan menggunakan metode .sum() untuk mendapatkan jumlah semua elemen.

• untuk kasus dengan 1,1 elemen awal, alih-alih {0, 1} kita menetapkan {1, 1}.

Mendapatkan angka ke-n dalam deret Fibonacci

Terkadang Anda diminta untuk mencetak bukan rangkaian angka, melainkan khususnya angka ke-n dalam deret Fibonacci. Biasanya, ini hanya membuat tugas lebih mudah karena Anda dapat dengan mudah menyesuaikan solusi sebelumnya untuk ini. Nah, bagaimana dengan menyelesaikan masalah melalui rekursi?

1. untuk 0,1:

   public int getFibonacciValue(int n) {
     if (n <= 1) {
        return 0;
     } else if (n == 2) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   Untuk menjalankan algoritme dengan 0,1, perlu ditentukan bahwa ketika kita mencoba mendapatkan elemen pertama, kita mendapatkan 0, dan elemen kedua - 1. Faktanya, kita, seperti dalam solusi sebelumnya, perlu menyetel dua elemen pertama. elemen.

2. implementasi untuk 1.1 akan sedikit berbeda:

   public int getFibonacciValue(int n) {
     if (n == 0) {
        return 0;
     } else if (n == 1) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   Dalam hal ini, kita hanya perlu menyetel elemen pertama sebagai 1, karena elemen kedua akan sama, dan respons metode juga akan sama.

   Pada saat yang sama, kita menyetel reaksi metode ke 0, karena jika kita tidak menyetelnya, maka ketika 2 muncul sebagai argumen, metode yang sama dipanggil secara rekursif, tetapi dengan argumen 0. Selanjutnya, metode yang sama akan diluncurkan , tetapi dengan bilangan negatif, dan seterusnya hingga negatif tak terhingga. Hasilnya, kita akan menerima StackOverflowError .

Namun, metode rekursif tidak disarankan karena tidak seperti metode sebelumnya, yang dijalankan dalam waktu linier O(n), metode rekursif dapat memerlukan waktu penyelesaian yang jauh lebih lama. Mengapa? Metode rekursif bisa memakan waktu lama, karena selama proses perhitungan fungsi akan dipanggil berkali-kali dari argumen yang sama. Misalnya, saat mengevaluasi getFibonacciValue(7), fungsi akan melakukan panggilan rekursif ke getFibonacciValue(5) dan getFibonacciValue(6), kedua panggilan rekursif akan memanggil getFibonacciValue(4)), yang akan mengakibatkan pemanggilan operasi yang sama beberapa kali. Saat wawancara, Anda dapat menunjukkan metode ini sebagai solusi, tetapi pada saat yang sama membicarakan kekurangannya dan menawarkan metode lain sebagai balasannya. Perlu juga dicatat bahwa tipe int di Java memungkinkan Anda untuk menyimpan dari -2147483648 hingga 2147483647, jadi Anda hanya dapat menghitung 46 angka Fibonacci pertama: jika kita mencoba mendapatkan angka ke-47 berikutnya, akan ada overflow dan kita akan mendapatkan angka negatif. Jika kita menggunakan tipe data panjang dan bukan int, kita akan dapat menghitung 91 angka Fibonacci pertama dengan benar. Untuk menghitung bilangan Fibonacci selanjutnya, Anda perlu menggunakan kelas BigInteger, yang mengimplementasikan logika untuk menyimpan dan operasi aritmatika bilangan yang sangat BESAR.