Java proqramçısı Fibonaççi nömrələri haqqında nə bilməlidir

Çox vaxt müsahibələr zamanı, xüsusən də xarici şirkətlərdə insanlardan alqoritmlər barədə soruşulur və stresli vəziyyətdə nəyisə çılğınlıqla xatırlamaq həmişə asan olmur. Buna görə də hazırlamaq lazımdır. Başlamaq üçün, heç olmasa əsas alqoritmlər haqqında yaddaşınızı təzələyin. Bu gün biz Fibonacci nömrələri kimi bir fenomeni və onlarla əlaqəli problemlərin ən ümumi variantlarını təhlil edəcəyik. Fibonaççi ədədləri sıfır və bir ədədləri ilə başlayan natural ədədlər ardıcıllığıdır və hər bir sonrakı ədəd əvvəlki ikisinin cəminə bərabərdir: 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

Qeyd etmək lazımdır ki, bəzən 0 buraxılır və sıra 1 1 2 3 ilə başlayır... Bir qayda olaraq, məsələnin şərtlərində seriyanın hansı ilk iki rəqəmlə başlaması dərhal göstərilir (0,1 və ya 1,1), buna görə də hər iki hal üçün həll yollarını nəzərdən keçirəcəyik.

Java-da ilk n Fibonacci nömrələrini əldə etmək

Tutaq ki, ilk n Fibonaççi ədədini əldə etmək vəzifəmiz var.

• hal 0.1:

  Müəyyən bir n nömrəsi bizə gəlir:

  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 ölçülü massiv yaradırıq. İlk iki element sıfıra və birə bərabər olacaq, qalan elementlər isə bu döngədən keçərək massivdən əvvəlki nömrələrdən istifadə etməklə əldə edilir.

  Və göstəririk:

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

  int n = 10 təyin edin;

  Və əldə edirik:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• 1.1 hal üçün həll əslində fərqli deyil:

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

  Dəyişdirməyimiz lazım olan tək şey arr[0] massivinin ilk elementi idi: 0-dan 1-ə. Müvafiq olaraq, ilk 10 element belə olacaq:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Axın vasitəsilə ilk n Fibonacci nömrələri

Amma biz öz səviyyəmizi göstərmək istəyirik. Beləliklə, axın istifadə edərək bu həllin necə görünəcəyini görək .

• 0.1 üçün:

  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 sinifinin statik təkrarlama metodu funksiyanı ilkin massiv arr-a tətbiq etməklə yaradılmış sonsuz sıralı axını qaytarır. Bizim vəziyyətimizdə funksiya əvvəlki birinə əsaslanaraq hər bir yeni massiv tərtib etmək qaydasını təyin etməkdir. Nəticədə massiv axını alacağıq:

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

  Lakin onların sonsuz sayda olacaq və buna görə də .limit(n) istifadə edərək elementlərin sayını birinci n-ə (bizim halda 10-a qədər) azaldırıq.

  Bununla belə, bizə massiv axınına ehtiyac yoxdur, ona görə də .map(y -> y[0]) istifadə edərək biz hər massivin birinci elementini seçirik və bizə lazım olan nömrələrlə axın əldə edirik və forEach istifadə edərək onu konsolda çap edirik. .

  Daha sərin görünür, elə deyilmi?

  ilk elementlərin 1,1 olması ilə bu kod da demək olar ki, eyni olacaq:

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

  Yenə də fərqlər ilkin elementdədir: {0, 1} əvəzinə biz {1, 1} təyin etdik.

  Əslində, nəticələr əvvəlki nümunədə olduğu kimi olacaq.

Fibonaççi ədədlərinin cəmi

Əgər bizdən n-ci element daxil olmaqla Fibonaççi ədədlərinin cəmini almaq istənsəydi? Bu, bizə heç bir çətinlik yaratmamalıdır. Gəlin axınla həll edək və forEach-i bir neçə başqa üsulla əvəz edək:

• 0.1 üçün:

  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) istifadə edərək biz axınımızı rəqəmsal IntStream-ə çeviririk və bütün elementlərin cəmini almaq üçün onun .sum() metodundan istifadə edirik.

• 1,1 ilkin elementli hal üçün {0, 1} əvəzinə {1, 1} təyin etdik.

Fibonaççi seriyasında n-ci ədədin alınması

Bəzən sizdən nömrələr seriyasını deyil, Fibonaççi seriyasındakı n-ci rəqəmi çap etməyiniz xahiş olunur. Bir qayda olaraq, bu, yalnız tapşırığı asanlaşdırır, çünki bunun üçün əvvəlki həlləri asanlıqla uyğunlaşdıra bilərsiniz. Yaxşı, problemi rekursiya vasitəsilə həll etmək haqqında nə demək olar?

1. 0.1 üçün:

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

   Alqoritmi 0,1-lə işlətmək üçün qeyd etmək lazımdır ki, birinci elementi almağa cəhd etdikdə 0, ikinci elementi isə 1 alırıq. Əslində, biz əvvəlki həllərdə olduğu kimi, ilk ikisini təyin etməliyik. elementləri.

2. 1.1 üçün tətbiq bir qədər fərqli olacaq:

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

   Bu halda, yalnız birinci elementi 1 olaraq təyin etməliyik, çünki ikinci element eyni olacaq və metodun cavabı eyni olacaq.

   Eyni zamanda, metodun reaksiyasını 0-a təyin edirik, çünki onu təyin etməsək, arqument olaraq 2 gələndə eyni metod rekursiv çağırılır, lakin 0 arqumenti ilə. Sonra eyni metod işə salınacaq. , lakin mənfi ədədlərlə və mənfi sonsuzluğa qədər. Nəticədə StackOverflowError alacağıq .

Bununla belə, rekursiv metod tövsiyə edilmir, çünki xətti O(n) zamanında işləyən əvvəlki metodlardan fərqli olaraq, rekursiv metodun tamamlanması xeyli uzun çəkə bilər. Niyə? Rekursiv metod uzun müddət çəkə bilər, çünki hesablama prosesi zamanı funksiya eyni arqumentdən dəfələrlə çağırılacaqdır. Məsələn, getFibonacciValue(7)-ni qiymətləndirərkən funksiya getFibonacciValue(5) və getFibonacciValue(6)-a rekursiv zənglər edəcək, hər iki rekursiv zəng getFibonacciValue(4)-ə zəng edəcək, bu da eyni əməliyyatların bir neçə dəfə çağırılması ilə nəticələnəcək. Müsahibədə siz bu üsulu həll yolu kimi göstərə bilərsiniz, eyni zamanda onun çatışmazlıqlarından danışıb əvəzində başqa üsul təklif edə bilərsiniz. Onu da qeyd etmək lazımdır ki, Java-da int növü sizə -2147483648-dən 2147483647-yə qədər saxlamağa imkan verir, buna görə də siz yalnız ilk 46 Fibonaççi nömrəsini hesablaya biləcəksiniz: növbəti 47-ni almağa çalışsaq, daşqın olacaq və mənfi bir rəqəm alacağıq. Əgər int əvəzinə uzun məlumat tipindən istifadə etsək, ilk 91 Fibonaççi rəqəmini düzgün hesablaya bilərik. Sonrakı Fibonaççi ədədlərini hesablamaq üçün həqiqətən BÖYÜK ədədlərin saxlanması və hesab əməliyyatları üçün məntiqi həyata keçirən BigInteger sinifindən istifadə etməlisiniz.