vadimk772336

заготовка мейна

Nov 22nd, 2021 (edited)
649
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib> // для функций rand() и srand()
  4. #include <list>
  5. using namespace std;
  6.  
  7. const int p = 2000000033;
  8.  
  9. int rand_int(int min, int max)
  10. {
  11.     static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);
  12.     // Равномерно распределяем рандомное число в нашем диапазоне
  13.     return static_cast<int>(rand() * fraction * (max - min + 1) + min);
  14. }
  15.  
  16. int uni_hash(int a, int b, int k)
  17. {
  18.     return a * k + b;
  19. }
  20.  
  21. int main()
  22. {
  23.     srand(4541);
  24.     int n, a, b;
  25.     int alpha_k, beta_k;
  26.  
  27.     cin >> n;
  28.     const int m = 3 * n;
  29.  
  30.     vector<int> A(m); //Массив меток (i-я ячейка хранит число которое стоит над вершиной i)
  31.     vector<int> K(n); //Массив ключей
  32.  
  33.     for (int i = 0; i < n; ++i)
  34.         cin >> K[i];
  35.  
  36.  
  37.     bool flag = True;
  38.     while (flag)
  39.     {
  40.         Graph g(m);
  41.  
  42.         a1 = rand_int(1, p - 1);
  43.         b1 = rand_int(0, p - 1);
  44.         a2 = rand_int(1, p - 1);
  45.         b2 = rand_int(0, p - 1);
  46.  
  47.         for (int i = 0; i < n; ++i)
  48.         {
  49.             alpha_k = uni_hash(a1, b1, K[i]);
  50.             beta_k = uni_hash(a2, b2, K[i]);
  51.             g.addEdge(alpha_k, beta_k);
  52.         }
  53.  
  54.         //Граф построен, осталось проверить что он корректный. Вызову DFS и он ответит yes or no
  55.  
  56.         if (!Graph.DFS())
  57.         {
  58.             flag = true; //Граф некоррек, придется делать по новой
  59.         }
  60.         else
  61.         {
  62.             flag = false; //Граф корректен, выходим из while
  63.         }
  64.     }
  65.  
  66.     //Массив А заполнен, можно заполнить хэш таблицу используя построенную ХФ
  67.     int idx;
  68.     vector<int> set(m);
  69.     for (int i = 0; i < n; ++i)
  70.     {
  71.         idx = (A[uni_hash(a1, b1, K[i])] + A[uni_hash(a2, b2, K[i])]) % m;
  72.         set[idx] = K[i];
  73.     }
  74.  
  75.  
  76.     return 0;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment