Apa programer Java kudu ngerti babagan nomer Fibonacci

Asring sajrone wawancara, utamane ing perusahaan manca, wong bisa ditakoni babagan algoritma, lan ing kahanan sing stres, ngeling-eling soko ora gampang. Mulane, sampeyan kudu nyiapake. Kanggo miwiti, paling refresh memori saka algoritma dhasar. Dina iki kita bakal njelasno fenomena kayata nomer Fibonacci lan varian paling umum saka masalah related kanggo wong-wong mau. Nomer Fibonacci minangka urutan nomer alami sing diwiwiti kanthi nomer nol lan siji, lan saben nomer sabanjure padha karo jumlah saka rong sadurunge: 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

Wigati dicathet menawa kadhangkala 0 diilangi, lan seri kasebut diwiwiti kanthi 1 1 2 3 ... Minangka aturan, ing kondisi masalah kasebut langsung ditemtokake sing nomer loro pisanan seri kasebut diwiwiti (0,1 utawa 1,1), supaya luwih kita bakal nimbang solusi kanggo loro kasus.

Njupuk nomer pisanan n Fibonacci ing Jawa

Upaminipun kita duwe tugas diwenehi nomer pisanan n Fibonacci.

• kasus 0.1:

  A nomer tartamtu n teka kanggo 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];
  }

  Kita nggawe array ukuran n. Loro unsur pisanan bakal padha karo nul lan siji, lan unsur isih dijupuk dening liwat daur ulang iki lan nggunakake nomer sadurungé saka Uploaded.

  Lan kita nampilake:

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

  Setel int n = 10;

  Lan kita entuk:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• kanggo kasus 1.1 solusi kasebut ora beda:

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

  Kabeh sing kudu diganti yaiku unsur pisanan saka array arr[0]: saka 0 nganti 1. Dadi, 10 unsur pisanan bakal dadi:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Pisanan n Fibonacci nomer liwat stream

Nanging kita pengin nuduhake level kita. Dadi ayo ndeleng apa solusi iki bakal katon kaya nggunakake stream .

• kanggo 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 iterate statis saka kelas Stream ngasilake stream dhawuh tanpa wates sing digawe kanthi nggunakake fungsi kasebut menyang arr array awal. Ing kasus kita, fungsi kasebut yaiku nyetel aturan kanggo nyusun saben array anyar, adhedhasar sing sadurunge. Akibaté, kita bakal entuk stream arrays:

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

  Nanging bakal ana nomer tanpa wates mau, lan mulane nggunakake .limit (n) kita nyuda nomer unsur kanggo n pisanan (ing kasus kita 10).

  Nanging, kita ora perlu stream array, supaya nggunakake .map (y -> y [0]) kita milih unsur pisanan saben Uploaded lan njaluk stream karo nomer kita perlu lan print menyang console nggunakake forEach .

  Katon luwih keren, ta?

  kanthi unsur pisanan yaiku 1,1 kode iki uga meh padha:

  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));

  Maneh, bedane ana ing unsur wiwitan: tinimbang {0, 1} kita nyetel {1, 1}

  Bener, asil bakal padha karo conto sadurunge.

Jumlah angka Fibonacci

Apa yen kita dijaluk entuk jumlah nomer Fibonacci nganti unsur nth kalebu? Iki ngirim ora nimbulaké kita kangelan. Ayo njupuk solusi karo stream lan ngganti forEach karo sawetara cara liyane:

• kanggo 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);

  Nggunakake .mapToInt (Integer ::intValue) kita Ngonversi stream menyang IntStream numerik lan nggunakake cara .sum () kanggo njaluk jumlah kabeh unsur.

• kanggo kasus karo 1,1 unsur awal, tinimbang {0, 1} kita nyetel {1, 1}.

Entuk nomer nth ing seri Fibonacci

Kadhangkala sing dijaluk print ora seri nomer, nanging khusus nomer n ing seri Fibonacci. Minangka aturan, iki mung nggawe tugas luwih gampang, amarga sampeyan bisa kanthi gampang ngganti solusi sadurunge kanggo iki. Nah, kepiye carane ngrampungake masalah liwat rekursi?

1. kanggo 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);
     }
   }

   Kanggo nglakokake algoritma kanthi 0,1, perlu kanggo nemtokake yen nalika nyoba entuk unsur pisanan, kita entuk 0, lan kaloro - 1. Ing kasunyatan, kita, kaya ing solusi sadurunge, kudu nyetel loro pisanan. unsur.

2. implementasine kanggo 1.1 bakal rada beda:

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

   Ing kasus iki, kita mung kudu nyetel unsur pisanan minangka 1, amarga unsur kapindho bakal padha, lan respon cara bakal padha.

   Ing wektu sing padha, kita nyetel reaksi metode kasebut dadi 0, amarga yen kita ora nyetel, banjur nalika 2 teka minangka argumen, metode sing padha diarani rekursif, nanging kanthi argumen 0. Sabanjure, metode sing padha bakal diluncurake. , nanging kanthi angka negatif, lan sateruse nganti tanpa wates negatif. Akibaté, kita bakal nampa StackOverflowError .

Nanging, cara rekursif ora dianjurake amarga ora kaya cara sadurunge, sing mlaku ing O(n) wektu linear, cara rekursif bisa njupuk wektu luwih suwe kanggo ngrampungake. Kenging punapa? Cara rekursif bisa njupuk wektu suwe, amarga sajrone proses pitungan fungsi kasebut bakal diarani kaping pirang-pirang saka argumen sing padha. Contone, nalika ngevaluasi getFibonacciValue (7), fungsi bakal nggawe telpon rekursif kanggo getFibonacciValue (5) lan getFibonacciValue (6), loro telpon rekursif bakal nelpon getFibonacciValue (4)), kang bakal kasil nelpon operasi padha kaping pirang-pirang. Ing wawancara, sampeyan bisa nuduhake cara iki minangka solusi, nanging ing wektu sing padha ngomong babagan kekurangane lan menehi cara liya minangka imbalan. Wigati uga yen jinis int ing Jawa ngidini sampeyan nyimpen saka -2147483648 nganti 2147483647, dadi sampeyan mung bisa ngetung 46 nomer Fibonacci pisanan: yen kita nyoba entuk 47 sabanjure, bakal ana overflow lan kita bakal entuk nomer negatif. Yen kita nggunakake jinis data dawa tinimbang int, kita bakal bisa kanggo bener ngetung pisanan 91 Fibonacci nomer. Kanggo ngetung nomer Fibonacci sakteruse, sampeyan kudu nggunakake kelas BigInteger, kang ngleksanakake logika kanggo nyimpen lan operasi aritmetika nomer tenan BIG.