Як барномасози Java бояд дар бораи рақамҳои Фибоначчи чиро донад

Аксар вақт ҳангоми мусоҳибаҳо, бахусус дар ширкатҳои хориҷӣ, аз мардум дар бораи алгоритмҳо пурсон мешаванд ва дар вазъияти стресс, ба таври возеҳ ёд кардани чизе на ҳамеша осон аст. Аз ин рӯ, шумо бояд омода бошед. Барои оғоз кардан, ҳадди аққал хотираи алгоритмҳои асосиро нав кунед. Имрӯз мо як падидаи монанди рақамҳои Фибоначиро ва вариантҳои маъмултарини мушкилоти марбут ба онҳо таҳлил хоҳем кард. Рақамҳои Фибоначӣ пайдарпаии ададҳои табиӣ мебошанд, ки бо рақамҳои сифр ва як оғоз мешаванд ва ҳар як рақами минбаъда ба маблағи дуи қаблӣ баробар аст: 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

Бояд гуфт, ки баъзан 0-ро партофта, силсила бо 1 1 2 3 сар мешавад... Одатан, дар шароити масъала фавран нишон дода мешавад, ки силсила бо кадом ду адади аввал сар мешавад (0,1 ё 1,1), Пас, минбаъд мо роҳҳои ҳалли ҳарду ҳолатро баррасӣ хоҳем кард.

Гирифтани аввалин рақамҳои Фибоначӣ дар Java

Фарз мекунем, ки мо вазифаи ба даст овардани рақамҳои аввалини Фибоначиро дорем.

• Ҳолати 0.1:

  Шумораи муайяни n ба мо меояд:

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

  Мо массиви андозаи n месозем. Ду унсури аввал ба сифр ва як баробар хоҳанд буд ва унсурҳои боқимонда бо роҳи гузаштан аз ин давра ва истифодаи рақамҳои қаблии массив ба даст оварда мешаванд.

  Ва мо нишон медиҳем:

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

  Танзими int n = 10;

  Ва мо ба даст меорем:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• барои ҳолати 1.1 ҳалли воқеан фарқ надорад:

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

  Барои тағир додани мо танҳо элементи якуми массиви arr[0] лозим буд: аз 0 то 1. Мутаносибан, 10 элементи аввал инҳо хоҳанд буд:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Аввалин рақамҳои Фибоначӣ тавассути ҷараён

Аммо мо мехоҳем сатҳи худро нишон диҳем. Пас биёед бубинем, ки ин ҳалли истифодаи stream чӣ гуна хоҳад буд .

• барои 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));

  Усули такрории статикии синфи Stream ҷараёни беохири тартибдодашударо бармегардонад, ки тавассути татбиқи функсия ба массиви ибтидоии arr сохта шудааст. Дар ҳолати мо, функсия муқаррар кардани қоида барои эҷоди ҳар як массиви нав дар асоси массиви қаблӣ мебошад. Дар натиҷа, мо ҷараёни массивҳоро мегирем:

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

  Аммо шумораи беохири онҳо хоҳад буд ва аз ин рӯ бо истифода аз .limit(n) шумораи элементҳоро ба n-и аввал кам мекунем (дар ҳолати мо то 10).

  Аммо, мо ба ҷараёни массивҳо ниёз надорем, аз ин рӯ бо истифода аз .map(y -> y[0]) мо элементи якуми ҳар як массивро интихоб мекунем ва ҷараёнро бо рақамҳои лозима мегирем ва онро бо истифода аз forEach дар консол чоп мекунем. .

  Ба назар сардтар аст, ҳамин тавр не?

  бо унсурҳои аввал 1,1 ин code низ тақрибан якхела хоҳад буд:

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

  Боз, фарқиятҳо дар унсури ибтидоӣ ҳастанд: ба ҷои {0, 1} мо {1, 1}-ро муқаррар мекунем.

  Дар асл, натиҷаҳо ҳамон тавре ки дар мисоли қаблӣ буданд, хоҳанд буд.

Маҷмӯи рақамҳои Фибоначӣ

Чӣ мешавад, агар аз мо хоҳиш карда шавад, ки маблағи рақамҳои Фибоначиро то унсури n-умро дар бар гирем? Ин набояд ба мо ягон душворй расонад. Биёед ҳалли худро бо ҷараён гирем ва forEach-ро бо якчанд усули дигар иваз кунем:

• барои 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);

  Бо истифода аз .mapToInt(Integer::intValue) мо ҷараёни худро ба IntStream ададӣ табдил медиҳем ва усули .sum()-и онро барои ба даст овардани маблағи ҳамаи элементҳо истифода мебарем.

• барои ҳолати дорои 1,1 элементҳои ибтидоӣ, ба ҷои {0, 1} мо {1, 1} муқаррар мекунем.

Гирифтани рақами n-ум дар силсилаи Фибоначчи

Баъзан аз шумо хоҳиш карда мешавад, ки на як қатор рақамҳо, балки махсусан рақами n-и силсилаи Фибоначиро чоп кунед. Чун қоида, ин танҳо вазифаро осон мекунад, зеро шумо метавонед ҳалли қаблиро барои ин ба осонӣ мутобиқ кунед. Хуб, дар бораи ҳалли мушкилот тавассути рекурсия чӣ гуфтан мумкин аст?

1. барои 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);
     }
   }

   Барои иҷро кардани алгоритми 0,1 бояд муайян кард, ки ҳангоми кӯшиши ба даст овардани элементи якум, мо 0 мегирем ва дуюм - 1. Дар асл, мо, мисли ҳалли қаблӣ, бояд дуи аввалро муқаррар кунем. унсурҳо.

2. татбиқи 1.1 каме фарқ мекунад:

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

   Дар ин ҳолат, мо бояд танҳо унсури аввалро ҳамчун 1 муқаррар кунем, зеро элементи дуюм якхела хоҳад буд ва посухи усул якхела хоҳад буд.

   Дар айни замон, мо реаксияи методро ба 0 муқаррар мекунем, зеро агар мо онро муқаррар накунем, вақте ки 2 ҳамчун аргумент меояд, ҳамон усул ба таври рекурсивӣ даъват карда мешавад, аммо бо аргументи 0. Баъдан, ҳамон усул оғоз мешавад. , аммо бо рақамҳои манфӣ ва ғайра то беохири манфӣ. Дар натиҷа, мо StackOverflowError мегирем .

Аммо, усули рекурсивӣ тавсия дода намешавад, зеро бар хилофи усулҳои қаблӣ, ки дар вақти хаттии O(n) кор мекунанд, усули рекурсивӣ метавонад ба таври назаррас тӯл кашад. Чаро? Усули рекурсивӣ метавонад вақти зиёдро талаб кунад, зеро дар ҷараёни ҳисобкунӣ функсия аз як аргумент чандин маротиба даъват карда мешавад. Масалан, ҳангоми арзёбии getFibonacciValue(7), функсия ба getFibonacciValue(5) ва getFibonacciValue(6) зангҳои рекурсивӣ мекунад, ҳарду зангҳои рекурсивӣ getFibonacciValue(4)-ро даъват мекунанд, ки ин боиси чанд маротиба даъват шудани ҳамон амалҳо мегардад. Дар мусоҳиба шумо метавонед ин усулро ҳамчун роҳи ҳал нишон диҳед, аммо дар айни замон дар бораи камбудиҳои он сӯҳбат кунед ва дар иваз усули дигарро пешниҳод кунед. Инчунин бояд қайд кард, ки навъи int дар Java ба шумо имкон медиҳад, ки аз -2147483648 то 2147483647 захира кунед, бинобар ин шумо танҳо 46 рақами аввалини Фибоначиро ҳисоб карда метавонед: агар мо кӯшиш кунем, ки 47-уми ояндаро ба даст орем, зиёдшавӣ ба амал меояд ва рақами манфӣ мегирем. Агар мо ба ҷои int навъи маълумоти дарозро истифода барем, мо метавонем 91 адади Фибоначиро дуруст ҳисоб кунем. Барои ҳисоб кардани рақамҳои минбаъдаи Фибоначӣ, шумо бояд синфи BigInteger-ро истифода баред, ки мантиқи нигоҳдорӣ ва амалиёти арифметикии рақамҳои воқеан BIG-ро амалӣ мекунад.