Java программисти Fibonacci сандары жөнүндө эмнени билиши керек

Көбүнчө интервью учурунда, өзгөчө чет элдик компанияларда, адамдардан алгоритмдер жөнүндө суралышы мүмкүн, ал эми стресстик кырдаалда бир нерсени эстеп калуу дайыма эле оңой боло бербейт. Ошондуктан, даярдоо керек. Баштоо үчүн, жок дегенде, негизги алгоритмдердин эс тутумун жаңыртыңыз. Бүгүн биз Fibonacci сандары сыяктуу көрүнүштү жана аларга байланыштуу маселелердин эң кеңири таралган варианттарын талдайбыз. Фибоначчи сандары нөл жана бир сандарынан башталган натурал сандардын ырааттуулугу жана ар бир кийинки сан мурунку экөөнүн суммасына барабар: 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'да биринчи n Fibonacci сандарын алуу

Бизде биринчи n Фибоначчи сандарын алуу милдети бар дейли.

• 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 учур үчүн чечим чындыгында айырмаланbyte:

  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

Биринчи n Fibonacci сандары агым аркылуу

Бирок биз өзүбүздүн деңгээлибизди көрсөткүбүз келет. Келгиле, бул чечим 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} койдук.

  Чынында, натыйжалар мурунку мисалдагыдай болот.

Fibonacci сандарынын суммасы

Эгер бизден 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} койдук.

Fibonacci сериясындагы n-санды алуу

Кээде сизден сандарды эмес, Fibonacci сериясындагы 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 алабыз .

Бирок, рекурсивдүү ыкма сунушталbyte, анткени сызыктуу O(n) убакытта иштеген мурунку методдордон айырмаланып, рекурсивдүү ыкманы аяктоо бир кыйла узакка созулушу мүмкүн. Неге? Рекурсивдүү ыкма көп убакытты талап кылышы мүмкүн, анткени эсептөө процессинде функция бир эле аргументтен көп жолу чакырылат. Мисалы, getFibonacciValue(7) баалоодо, функция getFibonacciValue(5) жана getFibonacciValue(6) үчүн рекурсивдүү чалууларды жасайт, эки рекурсивдүү чалуулар getFibonacciValue(4) деп аталат, бул бир эле операцияларды бир нече жолу чакырууга алып келет. Интервьюда сиз бул ыкманы чечим катары көрсөтүп, ошол эле учурда анын кемчorктерин айтып, анын ордуна башка ыкманы сунуштай аласыз. Белгилей кетчү нерсе, Javaдагы int түрү -2147483648ден 2147483647ге чейин сактоого мүмкүндүк берет, андыктан сиз Fibonacciнин биринчи 46 санын гана эсептей аласыз: эгерде биз кийинки 47-санды алууга аракет кылсак, толуп кетет жана биз терс санды алабыз. Эгерде биз int ордуна узун маалымат түрүн колдонсок, биз Fibonacci биринчи 91 санын туура эсептей алабыз. Кийинки Фибоначчи сандарын эсептөө үчүн сиз BigInteger классын колдонушуңуз керек, ал чындыгында ЧОҢ сандарды сактоо жана арифметикалык операциялар үчүн логиканы ишке ашырат.