Java programmistiniň Fibonacci sanlary barada bilmeli zatlary

Köplenç söhbetdeşlik wagtynda, esasanam daşary ýurt kompaniýalarynda adamlardan algoritmler barada soralyp bilner we dartgynly ýagdaýda bir zady ýada salmak hemişe aňsat däl. Şonuň üçin taýýarlanmaly. Ilki bilen, iň bolmanda esasy algoritmleri ýatda saklaň. Bu gün Fibonacci sanlary we olar bilen baglanyşykly meseleleriň iň köp ýaýran görnüşleri ýaly hadysany seljereris. Fibonacci sanlary nol we bir sanlardan başlanýan tebigy sanlaryň yzygiderliligi we indiki her san öňki ikisiniň jemine deňdir: 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

Käwagt 0-dan aýrylýandygyny we seriýanyň 1 1 2 3 bilen başlaýandygyny bellemelidiris ... Düzgün bolşy ýaly, meseläniň şertlerinde serialyň ilkinji iki belgisiniň haýsy (0,1 ýa-da 1.1) bilen başlaýandygy derrew kesgitlenýär, mundan beýläk iki meseläniň çözgüdine serederis.

Java-da ilkinji n Fibonacci sanlaryny almak

Ilkinji n Fibonacci sanlaryny almak borjumyz bar diýeliň.

• ýagdaý 0.1:

  Belli bir san bize gelýär:

  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 ululykdaky massiw döredýäris. Ilkinji iki element nola we birine deň bolar, galan elementler bu aýlawdan geçip we massiwdäki öňki sanlary ulanmak arkaly alynýar.

  We görkezýäris:

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

  Int n = 10 düzüň;

  We alýarys:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• 1.1 ýagdaýynda çözgüt aslynda üýtgeşik däl:

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

  Üýtgetmeli zadymyz, massiwiň birinji elementi [0]: 0-dan 1-e çenli. Şoňa laýyklykda ilkinji 10 element bolar:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Ilki n Fibonacci sanlary akym arkaly

Emma öz derejämizi görkezmek isleýäris. Geliň, bu çözgüdiň akymy ulanmagyň nähili boljakdygyny göreliň .

• 0,1 üçin:

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

  Akym synpynyň statiki gaýtalama usuly, funksiýany başlangyç massiwde ulanmak arkaly döredilen çäksiz sargyt akymyny gaýtaryp berýär. Biziň ýagdaýymyzda, funksiýa her täze massiwiň öňki düzgünine esaslanmak düzgüni düzmekdir. Netijede, massiwleriň akymyny alarys:

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

  Themöne olaryň çäksiz sany bolar, şonuň üçin .limit (n) ulanyp, elementleriň sanyny birinji n-a çenli azaldarys (biziň ýagdaýymyzda 10).

  Şeýle-de bolsa, bize massiw akymy gerek däl, şonuň üçin .map (y -> y [0]) ulanyp, her massiwiň birinji elementini saýlaýarys we zerur sanlar bilen akym alýarys we forEach ulanyp konsola çap edýäris. .

  Salkyn görünýär, şeýlemi?

  ilkinji elementleriň 1,1 bolmagy bilen bu kod hem birmeňzeş bolar:

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

  Againene-de tapawutlar başlangyç elementde: {0, 1} ýerine {1, 1 set goýýarys

  Aslynda, netijeler öňki mysaldaky ýaly bolar.

Fibonacci sanlarynyň jemi

Fibonacci sanlarynyň jemini n elementine çenli öz içine alsak näme etmeli? Bu bize hiç hili kynçylyk döretmeli däldir. Geliň, akym bilen çözgüt alalyň we “Each” -y başga-da birnäçe usul bilen çalyşalyň:

• 0,1 üçin:

  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) ulanyp, akymymyzy san IntStream-e öwürýäris we ähli elementleriň jemini almak üçin onuň .sum () usulyny ulanýarys.

• 1,1 başlangyç elementi bolan ýagdaý üçin, {0, 1} ýerine {1, 1 set goýýarys.

Fibonacci seriýasynda 9-njy belgini almak

Käwagt sanlaryň bir toparyny däl-de, esasanam Fibonacci seriýasyndaky n-nji belgini çap etmegiňizi haýyş edýärler. Düzgün bolşy ýaly, bu diňe meseläni aňsatlaşdyrýar, sebäbi munuň üçin öňki çözgütleri aňsatlyk bilen uýgunlaşdyryp bilersiňiz. Dogrusy, meseläni gaýtalamak arkaly çözmek näme?

1. 0,1 üçin:

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

   Algoritmi 0,1 bilen işletmek üçin, birinji elementi aljak bolanymyzda 0, ikinjisini - 1 alýandygymyzy kesgitlemeli, aslynda, öňki çözgütlerdäki ýaly, ilkinji ikisini bellemeli; elementleri.

2. 1.1 üçin ýerine ýetiriş birneme üýtgeşik bolar:

   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 ýagdaýda diňe birinji elementi 1 hökmünde bellemeli, sebäbi ikinji element birmeňzeş bolar we usulyň jogaby birmeňzeş bolar.

   Şol bir wagtyň özünde, usulyň reaksiýasyny 0-a belledik, sebäbi kesgitlemesek, 2-nji argument hökmünde gelende şol bir usul gaýtalanýar, ýöne 0-njy argument bilen. Soňra indiki usul şol bir usul bilen işe giriziler. , ýöne otrisatel sanlar we ş.m. Netijede, “StackOverflowError” alarys .

Şeýle-de bolsa, gaýtalanýan usul maslahat berilmeýär, sebäbi çyzykly O (n) wagty bilen işleýän öňki usullardan tapawutlylykda, gaýtalanýan usul gutarmak üçin ep-esli wagt alyp biler. Näme üçin? Gaýtalanýan usul köp wagt alyp biler, sebäbi hasaplama prosesi şol bir argumentden birnäçe gezek çagyrylar. Mysal üçin, getFibonacciValue (7) baha berlende, funksiýa getFibonacciValue (5) we getFibonacciValue (6) üçin gaýtalanýan jaňlar eder, iki gezek gaýtalanýan jaňlar getFibonacciValue (4) diýer, bu bolsa birmeňzeş amallary birnäçe gezek çagyrar. Söhbetdeşlikde bu usuly çözgüt hökmünde görkezip bilersiňiz, ýöne şol bir wagtyň özünde kemçilikleri barada gürleşiň we öwezine başga bir usul teklip edip bilersiňiz. Şeýle hem, Java-daky int görnüşiniň -2147483648-den 2147483647-e çenli saklamaga mümkinçilik berýändigini bellemelidiris, şonuň üçin diňe ilkinji 46 Fibonacci belgisini hasaplap bilersiňiz: indiki 47-ni aljak bolsak, suw joşmagy bolar we otrisatel san alarys. Int ýerine derek uzyn maglumat görnüşini ulansak, ilkinji 91 Fibonacci sanlaryny dogry hasaplap bileris. Soňky Fibonacci sanlaryny hasaplamak üçin, hakykatdanam BIG sanlaryň saklanmagy we arifmetiki amallary üçin logikany ýerine ýetirýän BigInteger synpyny ulanmaly.