Ano ang dapat malaman ng isang Java programmer tungkol sa mga numero ng Fibonacci

Kadalasan sa mga panayam, lalo na sa mga dayuhang kumpanya, ang mga tao ay maaaring tanungin tungkol sa mga algorithm, at sa isang nakababahalang sitwasyon, ang galit na galit na pag-alala sa isang bagay ay hindi laging madali. Samakatuwid, kailangan mong maghanda. Upang magsimula, i-refresh man lang ang iyong memorya ng mga pangunahing algorithm. Ngayon ay susuriin natin ang gayong kababalaghan bilang mga numero ng Fibonacci at ang pinakakaraniwang mga variant ng mga problemang nauugnay sa kanila. Ang mga numerong Fibonacci ay isang pagkakasunud-sunod ng mga natural na numero na nagsisimula sa mga numerong zero at isa, at ang bawat kasunod na numero ay katumbas ng kabuuan ng naunang dalawa: 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

Ito ay nagkakahalaga ng pagpuna na kung minsan ay 0 ay tinanggal, at ang serye ay nagsisimula sa 1 1 2 3... Bilang isang patakaran, sa mga kondisyon ng problema ay agad na tinukoy kung aling unang dalawang numero ang serye ay nagsisimula sa (0.1 o 1.1), kaya higit pang isasaalang-alang namin ang mga solusyon para sa parehong mga kaso.

Pagkuha ng unang n Fibonacci na numero sa Java

Ipagpalagay na mayroon tayong gawain upang makuha ang unang n Fibonacci na numero.

• kaso 0.1:

  Isang tiyak na numero n ang dumating sa amin:

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

  Lumilikha kami ng isang hanay ng laki n. Ang unang dalawang elemento ay magiging katumbas ng zero at isa, at ang natitirang mga elemento ay nakukuha sa pamamagitan ng pagdaan sa loop na ito at gamit ang mga nakaraang numero mula sa array.

  At ipinapakita namin:

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

  Itakda ang int n = 10;

  At nakukuha namin:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• para sa kaso 1.1 ang solusyon ay talagang hindi naiiba:

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

  Ang kailangan lang naming baguhin ay ang unang elemento ng array arr[0]: mula 0 hanggang 1. Alinsunod dito, ang unang 10 elemento ay:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Una n Fibonacci numero sa pamamagitan ng stream

Ngunit nais naming ipakita ang aming antas. Kaya tingnan natin kung ano ang magiging hitsura ng solusyon na ito gamit ang stream .

• para sa 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));

  Ang static na umuulit na paraan ng klase ng Stream ay nagbabalik ng walang katapusang ordered stream na nilikha sa pamamagitan ng paglalapat ng function sa paunang array arr. Sa aming kaso, ang function ay upang itakda ang panuntunan para sa pagbuo ng bawat bagong array, batay sa nauna. Bilang resulta, makakakuha tayo ng isang stream ng mga array:

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

  Ngunit magkakaroon ng walang katapusang bilang ng mga ito, at samakatuwid gamit ang .limit(n) binabawasan namin ang bilang ng mga elemento sa unang n (sa aming kaso hanggang 10).

  Gayunpaman, hindi namin kailangan ng stream ng mga array, kaya gamit ang .map(y -> y[0]) pipiliin namin ang unang elemento ng bawat array at kumuha kami ng stream na may mga numerong kailangan namin at i-print ito sa console gamit ang forEach .

  Mukhang mas cool, hindi ba?

  na ang mga unang elemento ay 1,1 ang code na ito ay halos pareho din:

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

  Muli, ang mga pagkakaiba ay nasa paunang elemento: sa halip na {0, 1} itinakda namin ang {1, 1}

  Sa totoo lang, ang mga resulta ay magiging katulad ng sa nakaraang halimbawa.

Kabuuan ng mga numero ng Fibonacci

Paano kung hihilingin sa amin na kunin ang kabuuan ng mga numero ng Fibonacci hanggang sa ika-n na elemento kasama? Hindi ito dapat magdulot sa atin ng anumang kahirapan. Kumuha tayo ng solusyon sa isang stream at palitan ang forEach ng ilang iba pang mga pamamaraan:

• para sa 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);

  Gamit ang .mapToInt(Integer::intValue) kino-convert namin ang aming stream sa isang numeric na IntStream at ginagamit ang .sum() na paraan nito upang makuha ang kabuuan ng lahat ng elemento.

• para sa kaso na may 1,1 paunang elemento, sa halip na {0, 1} itinakda namin ang {1, 1}.

Pagkuha ng nth number sa Fibonacci series

Minsan hihilingin sa iyo na mag-print ng hindi isang serye ng mga numero, ngunit partikular na ang ika-n na numero sa serye ng Fibonacci. Bilang isang patakaran, pinapadali lamang nito ang gawain, dahil madali mong iakma ang mga nakaraang solusyon para dito. Well, ano ang tungkol sa paglutas ng problema sa pamamagitan ng recursion?

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

   Upang patakbuhin ang algorithm na may 0,1, kinakailangang tukuyin na kapag sinubukan nating makuha ang unang elemento, makakakuha tayo ng 0, at ang pangalawa - 1. Sa katunayan, tayo, tulad ng sa mga nakaraang solusyon, kailangan nating itakda ang unang dalawa mga elemento.

2. ang pagpapatupad para sa 1.1 ay bahagyang naiiba:

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

   Sa kasong ito, kailangan lang nating itakda ang unang elemento bilang 1, dahil ang pangalawang elemento ay magiging pareho, at ang tugon ng pamamaraan ay magiging pareho.

   Kasabay nito, itinakda namin ang reaksyon ng pamamaraan sa 0, dahil kung hindi namin ito itatakda, kung gayon kapag ang 2 ay dumating bilang isang argumento, ang parehong pamamaraan ay tinatawag na recursively, ngunit may argumento 0. Susunod, ang parehong paraan ay ilulunsad , ngunit may mga negatibong numero, at iba pa hanggang sa negatibong infinity. Bilang resulta, makakatanggap kami ng StackOverflowError .

Gayunpaman, hindi inirerekomenda ang recursive na paraan dahil hindi tulad ng mga naunang pamamaraan, na tumatakbo sa linear na O(n) na oras, ang recursive na paraan ay maaaring tumagal nang mas matagal bago makumpleto. Bakit? Ang recursive na paraan ay maaaring tumagal ng mahabang panahon, dahil sa panahon ng proseso ng pagkalkula ang function ay tatawagin ng maraming beses mula sa parehong argumento. Halimbawa, kapag sinusuri ang getFibonacciValue(7), ang function ay gagawa ng mga recursive na tawag upang getFibonacciValue(5) at getFibonacciValue(6), ang parehong recursive na tawag ay tatawag sa getFibonacciValue(4)), na magreresulta sa pagtawag sa parehong mga operasyon nang maraming beses. Sa panayam, maaari mong ipakita ang pamamaraang ito bilang isang solusyon, ngunit sa parehong oras ay pag-usapan ang tungkol sa mga pagkukulang nito at nag-aalok ng isa pang paraan bilang kapalit. Kapansin-pansin din na ang uri ng int sa Java ay nagpapahintulot sa iyo na mag-imbak mula -2147483648 hanggang 2147483647, kaya magagawa mo lamang na kalkulahin ang unang 46 na numero ng Fibonacci: kung susubukan nating makuha ang susunod na ika-47, magkakaroon ng overflow at makakakuha tayo ng negatibong numero. Kung gagamitin namin ang mahabang uri ng data sa halip na int, magagawa naming kalkulahin nang tama ang unang 91 Fibonacci na numero. Upang kalkulahin ang kasunod na mga numero ng Fibonacci, kailangan mong gamitin ang klase ng BigInteger, na nagpapatupad ng lohika para sa pag-iimbak at mga pagpapatakbo ng aritmetika ng talagang MALAKING numero.