StoneHaos

misha_shik_m2

Mar 31st, 2021
351
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <time.h>
  5. #include <stdlib.h>
  6.  
  7. using namespace std;
  8.  
  9. int LS(vector<int> arr, int a) {
  10.     arr.push_back(a);
  11.     int i = 0;
  12.     for (; i < arr.size(); ++i) {
  13.         if (arr[i] == a)
  14.             break;
  15.     }
  16.     return (i == arr.size() - 1) ? -1 : i;
  17. }
  18.  
  19.  
  20. ostream& operator<<(ostream& out, vector<int> v) {
  21.     for (int i = 0; i < v.size(); ++i)
  22.         out << v[i] << " ";
  23.     return out;
  24. }
  25.  
  26. void FastS(vector<int>::iterator begin, vector<int>::iterator end) {
  27.     if (end - begin <= 1)
  28.         return;
  29.     auto left = begin;
  30.     auto right = end - 1;
  31.     auto pivot = begin + (end - begin) / 2;
  32.     while (left < right) {
  33.         while (left < pivot && *left <= *pivot) ++left;
  34.         while (right > pivot && *right >= *pivot) --right;
  35.         if (left < right) {
  36.             if (left == pivot) {
  37.                 swap(*left, *right);
  38.                 pivot = right;
  39.             }
  40.             else if (right == pivot) {
  41.                 swap(*left, *right);
  42.                 pivot = left;
  43.             }
  44.             else {
  45.                 swap(*left, *right);
  46.             }
  47.         }
  48.         if (left >= right) break;
  49.     }
  50.     FastS(begin, pivot);
  51.     FastS(pivot, end);
  52. }
  53.  
  54. static int Fibb(vector<int> arr, int elem) {
  55.     int l = 0, r = arr.size() - 1;
  56.     while (r - l > 1) {
  57.         int a = 1, b = 2, c;
  58.         while (l + b - 1 <= r && arr[l + b - 1] < elem) {
  59.             c = a + b;
  60.             a = b;
  61.             b = c;
  62.         }
  63.         l = max(l + a - 1, 0);
  64.         r = min(l + b - 1, int(arr.size() - 1));
  65.     }
  66.     int ret = -1;
  67.     if (arr[l] == elem)
  68.         ret = l;
  69.     else if (arr[r] == elem)
  70.         ret = r;
  71.     return ret;
  72. }
  73.  
  74.  
  75. int main(void) {
  76.     setlocale(LC_ALL, "Russian");
  77.     srand(time(NULL));
  78.  
  79.     int n;
  80.     cout << "Введите длину: ";
  81.     cin >> n;
  82.     vector<int> arr;
  83.     for (int i = 0; i < n; ++i)
  84.         arr.push_back(rand() % 100 - 50);
  85.  
  86.     cout << arr << endl;
  87.     int a;
  88.     cout << "Введите искомый элемент: ";
  89.     cin >> a;
  90.     cout << "Результат линейного поиска: " << LS(arr, a) << endl;
  91.  
  92.     FastS(arr.begin(), arr.end());
  93.     cout << arr << endl;
  94.     cin >> a;
  95.     cout << "Результат поиска Фибоначчи: " << Fibb(arr, a) << endl;
  96.  
  97.     return 0;
  98. }
RAW Paste Data