Java dasturchisi Fibonachchi raqamlari haqida nimani bilishi kerak

Ko'pincha intervyu paytida, ayniqsa xorijiy kompaniyalarda, odamlardan algoritmlar haqida so'rashlari mumkin va stressli vaziyatda biror narsani eslab qolish har doim ham oson emas. Shuning uchun siz tayyorgarlik ko'rishingiz kerak. Boshlash uchun, hech bo'lmaganda asosiy algoritmlar haqida xotirangizni yangilang. Bugun biz Fibonachchi raqamlari kabi hodisani va ular bilan bog'liq muammolarning eng keng tarqalgan variantlarini tahlil qilamiz. Fibonachchi raqamlari - bu nol va bir raqamlardan boshlanadigan natural sonlar ketma-ketligi va har bir keyingi son oldingi ikkitasining yig'indisiga teng: 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

Shuni ta'kidlash joizki, ba'zan 0 tushirilib, qator 1 1 2 3 dan boshlanadi... Qoidaga ko'ra, masalaning shartlarida qator birinchi ikki raqamdan (0,1 yoki 1,1) boshlanishi darhol ko'rsatiladi. shuning uchun biz ikkala holat uchun ham echimlarni ko'rib chiqamiz.

Java-da birinchi n Fibonachchi raqamlarini olish

Faraz qilaylik, bizda birinchi n Fibonachchi raqamini olish vazifasi bor.

• 0.1 holat:

  Bizga ma'lum bir n raqami keladi:

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

  Biz n o'lchamli massivni yaratamiz. Birinchi ikkita element nolga va bittaga teng bo'ladi, qolgan elementlar esa ushbu tsikldan o'tib, massivdagi oldingi raqamlardan foydalangan holda olinadi.

  Va biz ko'rsatamiz:

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

  int n = 10 ni o'rnating;

  Va biz olamiz:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• 1.1-holat uchun yechim aslida farq qilmaydi:

  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] massivning birinchi elementini o‘zgartirishimiz kerak edi: 0 dan 1 gacha. Shunga ko‘ra, dastlabki 10 ta element quyidagilar bo‘ladi:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Oqim orqali birinchi n Fibonachchi raqamlari

Lekin biz o'z darajamizni ko'rsatmoqchimiz. Keling, ushbu yechim stream yordamida qanday ko'rinishini ko'rib chiqaylik .

• 0,1 uchun:

  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 sinfining statik takrorlash usuli funktsiyani boshlang'ich massivga qo'llash orqali yaratilgan cheksiz tartiblangan oqimni qaytaradi. Bizning holatda, funktsiya avvalgisiga asoslanib, har bir yangi massivni tuzish qoidasini o'rnatishdan iborat. Natijada biz massivlar oqimini olamiz:

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

  Lekin ularning soni cheksiz bo'ladi va shuning uchun .limit(n) dan foydalanib biz elementlar sonini birinchi n gacha (bizning holimizda 10 tagacha) kamaytiramiz.

  Biroq, bizga massivlar oqimi kerak emas, shuning uchun .map(y -> y[0]) yordamida biz har bir massivning birinchi elementini tanlaymiz va kerakli raqamlar bilan oqim olamiz va forEach yordamida konsolga chop etamiz. .

  Salqinroq ko'rinadi, shunday emasmi?

  birinchi elementlar 1,1 bo'lsa, bu kod ham deyarli bir xil bo'ladi:

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

  Shunga qaramay, farqlar boshlang'ich elementda: {0, 1} o'rniga biz {1, 1} ni o'rnatamiz.

  Aslida, natijalar avvalgi misoldagi kabi bo'ladi.

Fibonachchi raqamlari yig'indisi

Agar bizdan Fibonachchi raqamlari yig'indisini n-chi elementgacha olish so'ralsa-chi? Bu bizga hech qanday qiyinchilik tug'dirmasligi kerak. Keling, oqim bilan yechimni olamiz va forEach ni bir nechta boshqa usullar bilan almashtiramiz:

• 0,1 uchun:

  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) yordamida biz oqimimizni raqamli IntStreamga aylantiramiz va barcha elementlarning yig'indisini olish uchun uning .sum() usulidan foydalanamiz.

• 1,1 boshlang'ich elementli holat uchun {0, 1} o'rniga {1, 1} ni o'rnatamiz.

Fibonachchi qatoridagi n-sonni olish

Ba'zan sizdan raqamlar qatorini emas, balki Fibonachchi seriyasidagi n-sonni chop etishingiz so'raladi. Qoida tariqasida, bu faqat vazifani osonlashtiradi, chunki siz buning uchun oldingi echimlarni osongina moslashingiz mumkin. Xo'sh, muammoni rekursiya orqali hal qilish haqida nima deyish mumkin?

1. 0,1 uchun:

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

   Algoritmni 0,1 bilan ishga tushirish uchun birinchi elementni olishga harakat qilganimizda biz 0 ni, ikkinchisini esa 1 ga olishini aniqlab olishimiz kerak.Aslida biz avvalgi yechimlarda bo'lgani kabi birinchi ikkitasini o'rnatishimiz kerak. elementlar.

2. 1.1 uchun amalga oshirish biroz boshqacha bo'ladi:

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

   Bunday holda, biz faqat birinchi elementni 1 deb belgilashimiz kerak, chunki ikkinchi element bir xil bo'ladi va usulning javobi bir xil bo'ladi.

   Shu bilan birga, biz usulning reaktsiyasini 0 ga qo'yamiz, chunki agar biz uni qo'ymasak, argument sifatida 2 kelganda, xuddi shu usul rekursiv chaqiriladi, lekin argument 0 bilan. Keyin xuddi shu usul ishga tushiriladi. , lekin manfiy sonlar bilan va manfiy cheksizgacha davom etadi. Natijada biz StackOverflowError ni olamiz .

Biroq, rekursiv usul tavsiya etilmaydi, chunki chiziqli O(n) vaqtida ishlaydigan oldingi usullardan farqli o'laroq, rekursiv usulni bajarish ancha uzoq davom etishi mumkin. Nega? Rekursiv usul uzoq vaqt talab qilishi mumkin, chunki hisoblash jarayonida funktsiya bir xil argumentdan ko'p marta chaqiriladi. Masalan, getFibonacciValue(7) ni baholashda funksiya getFibonacciValue(5) va getFibonacciValue(6) ga rekursiv qo‘ng‘iroqlarni amalga oshiradi, ikkala rekursiv qo‘ng‘iroq getFibonacciValue(4) ni chaqiradi, bu esa bir xil operatsiyalarni bir necha marta chaqirishga olib keladi. Suhbatda siz ushbu usulni yechim sifatida ko'rsatishingiz mumkin, lekin ayni paytda uning kamchiliklari haqida gapirib, evaziga boshqa usulni taklif qilishingiz mumkin. Shuni ham ta'kidlash joizki, Java-dagi int turi -2147483648 dan 2147483647 gacha saqlash imkonini beradi, shuning uchun siz faqat birinchi 46 Fibonachchi raqamini hisoblashingiz mumkin bo'ladi: agar biz keyingi 47-raqamni olishga harakat qilsak, to'lib-toshish bo'ladi va biz salbiy raqamni olamiz. Agar biz int o'rniga uzun ma'lumotlar turidan foydalansak, biz birinchi 91 ta Fibonachchi raqamini to'g'ri hisoblashimiz mumkin bo'ladi. Keyingi Fibonachchi raqamlarini hisoblash uchun siz haqiqatan ham KATTA raqamlarni saqlash va arifmetik operatsiyalar uchun mantiqni amalga oshiradigan BigInteger sinfidan foydalanishingiz kerak.