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 тіліндегі алғашқы 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 жағдай үшін шешім іс жүзінде өзгеше емес:

  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 Фибоначчи сандары

Бірақ біз өз деңгейімізді көрсеткіміз келеді. Сонымен, 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 класының статикалық қайталау әдісі функцияны бастапқы массив массивіне қолдану арқылы жасалған шексіз реттелген ағынды қайтарады. Біздің жағдайда, функция алдыңғысына негізделген әрбір жаңа массив құру ережесін орнату болып табылады. Нәтижесінде біз массивтер ағынын аламыз:

  {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) деп шақырады, бұл бірдей әрекеттерді бірнеше рет шақыруға әкеледі. Сұхбатта сіз бұл әдісті шешім ретінде көрсете аласыз, бірақ сонымен бірге оның кемшіліктері туралы айтып, орнына басқа әдісті ұсына аласыз. Сондай-ақ, Java тіліндегі int түрі сізге -2147483648-ден 2147483647-ге дейін сақтауға мүмкіндік беретінін атап өткен жөн, сондықтан сіз тек алғашқы 46 Фибоначчи санын есептей аласыз: егер келесі 47-ні алуға тырыссақ, толып кету болады және теріс сан аламыз. Егер біз int орнына ұзын деректер түрін қолдансақ, біз алғашқы 91 Фибоначчи санын дұрыс есептей аламыз. Кейінгі Фибоначчи сандарын есептеу үшін шын мәнінде ҮЛКЕН сандарды сақтау және арифметикалық амалдар логикасын жүзеге асыратын BigInteger сыныбын пайдалану қажет.