Perkara yang perlu diketahui oleh pengaturcara Java tentang nombor Fibonacci

Selalunya semasa temu duga, terutamanya di syarikat asing, orang ramai mungkin ditanya tentang algoritma, dan dalam situasi yang tertekan, terkapai-kapai mengingati sesuatu tidak selalunya mudah. Oleh itu, anda perlu bersedia. Sebagai permulaan, sekurang-kurangnya segarkan semula ingatan anda tentang algoritma asas. Hari ini kita akan menganalisis fenomena seperti nombor Fibonacci dan varian paling biasa masalah yang berkaitan dengannya. Nombor Fibonacci ialah jujukan nombor asli yang bermula dengan nombor sifar dan satu, dan setiap nombor berikutnya adalah sama dengan jumlah dua 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 diingat bahawa kadang-kadang 0 diabaikan, dan siri itu bermula dengan 1 1 2 3... Sebagai peraturan, dalam keadaan masalah ia segera ditentukan yang mana dua nombor pertama siri itu bermula dengan (0.1 atau 1.1), jadi selanjutnya kami akan mempertimbangkan penyelesaian untuk kedua-dua kes.

Mendapatkan n nombor Fibonacci pertama di Jawa

Katakan kita mempunyai tugas untuk mendapatkan n nombor Fibonacci pertama.

• kes 0.1:

  Nombor n tertentu datang kepada kami:

  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 mencipta pelbagai saiz n. Dua elemen pertama akan sama dengan sifar dan satu, dan elemen yang selebihnya diperoleh dengan melalui gelung ini dan menggunakan nombor sebelumnya dari tatasusunan.

  Dan kami memaparkan:

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

  Tetapkan int n = 10;

  Dan kami mendapat:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• untuk kes 1.1 penyelesaiannya sebenarnya tidak berbeza:

  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];
  }

  Apa yang perlu kami ubah ialah elemen pertama array arr[0]: daripada 0 hingga 1. Sehubungan itu, 10 elemen pertama ialah:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Nombor Fibonacci n pertama melalui strim

Tetapi kami mahu menunjukkan tahap kami. Jadi mari kita lihat bagaimana penyelesaian ini akan kelihatan 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));

  Kaedah lelaran statik kelas Strim mengembalikan strim tertib tak terhingga yang dibuat dengan menggunakan fungsi pada arr tatasusunan awal. Dalam kes kami, fungsinya adalah untuk menetapkan peraturan untuk mengarang setiap tatasusunan baharu, berdasarkan yang sebelumnya. Akibatnya, kami akan mendapat aliran tatasusunan:

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

  Tetapi akan terdapat bilangan yang tidak terhingga, dan oleh itu menggunakan .limit(n) kita mengurangkan bilangan elemen kepada n pertama (dalam kes kita kepada 10).

  Walau bagaimanapun, kami tidak memerlukan aliran tatasusunan, jadi menggunakan .map(y -> y[0]) kami memilih elemen pertama setiap tatasusunan dan mendapatkan aliran dengan nombor yang kami perlukan dan mencetaknya ke konsol menggunakan forEach .

  Nampak lebih sejuk, bukan?

  dengan elemen pertama ialah 1,1 kod 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, perbezaan adalah dalam elemen awal: bukannya {0, 1} kami tetapkan {1, 1}

  Sebenarnya, hasilnya akan sama seperti dalam contoh sebelumnya.

Jumlah nombor Fibonacci

Bagaimana jika kami diminta untuk mendapatkan jumlah nombor Fibonacci sehingga elemen ke-n termasuk? Ini tidak sepatutnya menyebabkan kita mengalami kesulitan. Mari kita ambil penyelesaian dengan aliran dan gantikan untukSetiap dengan beberapa kaedah 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);

  Menggunakan .mapToInt(Integer::intValue) kami menukar strim kami kepada IntStream berangka dan menggunakan kaedah .sum() untuk mendapatkan jumlah semua elemen.

• untuk kes dengan 1,1 elemen awal, bukannya {0, 1} kami tetapkan {1, 1}.

Mendapat nombor ke-n dalam siri Fibonacci

Kadangkala anda diminta untuk mencetak bukan siri nombor, tetapi khususnya nombor ke-n dalam siri Fibonacci. Sebagai peraturan, ini hanya menjadikan tugas lebih mudah, kerana anda boleh dengan mudah menyesuaikan penyelesaian sebelumnya untuk ini. Nah, bagaimana pula 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 algoritma dengan 0,1, adalah perlu untuk menentukan bahawa apabila kita cuba mendapatkan elemen pertama, kita mendapat 0, dan yang kedua - 1. Malah, kita, seperti dalam penyelesaian sebelumnya, perlu menetapkan dua yang pertama elemen.

2. pelaksanaan untuk 1.1 akan sedikit berbeza:

   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 kes ini, kita hanya perlu menetapkan elemen pertama sebagai 1, kerana elemen kedua adalah sama, dan tindak balas kaedah akan sama.

   Pada masa yang sama, kami menetapkan tindak balas kaedah kepada 0, kerana jika kami tidak menetapkannya, maka apabila 2 datang sebagai hujah, kaedah yang sama dipanggil secara rekursif, tetapi dengan hujah 0. Seterusnya, kaedah yang sama akan dilancarkan , tetapi dengan nombor negatif, dan seterusnya sehingga infiniti negatif. Akibatnya, kami akan menerima StackOverflowError .

Walau bagaimanapun, kaedah rekursif tidak disyorkan kerana tidak seperti kaedah sebelumnya, yang berjalan dalam masa O(n) linear, kaedah rekursif boleh mengambil masa yang lebih lama untuk disiapkan. kenapa? Kaedah rekursif boleh mengambil masa yang lama, kerana semasa proses pengiraan fungsi akan dipanggil berkali-kali daripada hujah yang sama. Contohnya, apabila menilai getFibonacciValue(7), fungsi akan membuat panggilan rekursif untuk getFibonacciValue(5) dan getFibonacciValue(6), kedua-dua panggilan rekursif akan memanggil getFibonacciValue(4)), yang akan mengakibatkan panggilan operasi yang sama beberapa kali. Pada temu bual, anda boleh menunjukkan kaedah ini sebagai penyelesaian, tetapi pada masa yang sama bercakap tentang kekurangannya dan menawarkan kaedah lain sebagai balasan. Perlu diingatkan juga bahawa jenis int dalam Java membolehkan anda menyimpan dari -2147483648 hingga 2147483647, jadi anda hanya akan dapat mengira 46 nombor Fibonacci pertama: jika kita cuba mendapatkan nombor ke-47 seterusnya, akan berlaku limpahan dan kita akan mendapat nombor negatif. Jika kami menggunakan jenis data panjang dan bukannya int, kami akan dapat mengira 91 nombor Fibonacci pertama dengan betul. Untuk mengira nombor Fibonacci seterusnya, anda perlu menggunakan kelas BigInteger, yang melaksanakan logik untuk menyimpan dan operasi aritmetik nombor yang benar-benar BESAR.