StoneHaos

6

Nov 28th, 2021
831
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int fibonaccianSearch(int arr[], int n, int x){
  9.     /* Инициализация чисел Фибоначчи */
  10.     int fibMMm2 = 0; // (m-2)-е число Фибоначчи
  11.     int fibMMm1 = 1; // (m-1)-е число Фибоначчи
  12.     int fibM = fibMMm2 + fibMMm1; // m-е число Фибоначчи
  13.     /* Находим диапазон чисел Фибоначчи, в котором находится
  14.     число n */
  15.     while (fibM < n){
  16.         fibMMm2 = fibMMm1;
  17.         fibMMm1 = fibM;
  18.         fibM = fibMMm2 + fibMMm1;
  19.     }
  20.     // отмечаем выбранный диапазон
  21.     int offset = -1;
  22.     while (fibM > 1){
  23.         // Проверяем, является ли fibMm2 допустимым местоположением
  24.         int i = min(offset+fibMMm2, n-1);
  25.         /* Если X больше, чем значение индекса fibMm2,
  26.         исключить подмассив массива от offset to i */
  27.         if (arr[i] < x){
  28.             fibM = fibMMm1;
  29.             fibMMm1 = fibMMm2;
  30.             fibMMm2 = fibM - fibMMm1;
  31.             offset = i;
  32.         }
  33.         /* Если X меньше, чем значение индекса fibMm2,
  34.         исключить подмассив массива после i+1 */
  35.         else if (arr[i] > x){
  36.             fibM = fibMMm2;
  37.             fibMMm1 = fibMMm1 - fibMMm2;
  38.             fibMMm2 = fibM - fibMMm1;
  39.         }
  40.         /* Элемент найден. Возвращаем индекс */
  41.         else return i;
  42.     }
  43.     /* сравнение последнего элемента с x */
  44.     if(fibMMm1 && arr[offset+1]==x)return offset+1;
  45.     /*Элемент не найден. Возвращаем -1 */
  46.     return -1;
  47. }
  48.  
  49. int main() {
  50.     srand(time(NULL));
  51.     int n;
  52.     cin >> n;
  53.     int *a = new int[n];
  54.     for (int i = 0; i < n; i++) a[i] = rand() % 50;
  55.     sort(a, a + n);
  56.     for (int i = 0; i < n; i++) cout << a[i] << " ";
  57.     cout << endl;
  58.     int key;
  59.     cin >> key;
  60.     cout << "index " << fibonaccianSearch(a, n, key) << endl;
  61.     delete [] a;
  62.     return 0;
  63. }
RAW Paste Data