grigory51

dz_4.cpp

May 30th, 2014
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using std::cin;
  5. using std::cout;
  6. using std::vector;
  7.  
  8. class FixedSet {
  9. private:
  10.     vector<int> numbers; //хранимый массив
  11.     int** hash_table; //хэш-таблица
  12.     int a_hash_index, b_hash_index; //индексы для хэш-функции первого уровня
  13.     int** table_hash_index; //таблица с индексами для хэш-функций второго уровня
  14.     vector<int>* temp_hash; // временный массив векторов. Позволяет определить идеальную хэш-функцию.
  15.     int numbers_size; //число входных данных
  16. public:
  17.     FixedSet(const vector<int>&);
  18.     ~FixedSet();
  19.     const bool Contains(int);
  20. };
  21.  
  22. const unsigned int big_prime = 1000000007; //очень большое простое число
  23. void Enter(vector<int>&);//ввод
  24. int Random(int, int); //случайное число в указаном диапозоне.
  25. int Hash_function(int, int, int, int); //хэш-функция. a, b, x, n.
  26. bool Collizion(vector<int>&, int, int); //определяет есть ли коллизии для данных коэфициентов хэш-функции и данного набора данных
  27.  
  28. int main() {
  29.     vector<int> numbers;
  30.     vector<int> numbers_for_find;
  31.  
  32.     Enter(numbers);
  33.     Enter(numbers_for_find);
  34.    
  35.     FixedSet set(numbers);
  36.    
  37.     for(unsigned int index_number_for_find = 0; index_number_for_find < numbers_for_find.size(); ++index_number_for_find) {
  38.         if (set.Contains(numbers_for_find[index_number_for_find]) == true) {
  39.             cout << "Yes\n";
  40.         }
  41.         else {
  42.             cout << "No\n";
  43.         }
  44.     }
  45.     return 0;
  46. }
  47.  
  48. void Enter(vector<int>& numbers) {
  49.     int num_elements;
  50.     int buffer;
  51.     cin >> num_elements;
  52.     for(int number_of_number = 0; number_of_number < num_elements; ++number_of_number) {
  53.         cin >> buffer;
  54.         numbers.push_back(buffer);
  55.     }
  56. }
  57.  
  58. FixedSet::FixedSet(const vector<int>& input) {
  59.     numbers = input; //копирование
  60.     numbers_size = numbers.size(); //установка кол-ва элементов
  61.     hash_table = new int*[numbers.size()]; //создание хэш-таблицы
  62.     table_hash_index = new int*[numbers.size()]; //создание таблицы с параметрами функций
  63.     temp_hash = new vector<int>[numbers.size()]; //временная таблица
  64.  
  65.     for(unsigned int i = 0; i < numbers.size(); ++i) {
  66.         hash_table[i] = NULL;
  67.         table_hash_index[i] = NULL;
  68.     }
  69.  
  70.     a_hash_index = Random(1, big_prime - 1);//Генерирование хэш-функции
  71.     b_hash_index = Random(0, big_prime - 1);//первгого уровня
  72.  
  73.     for (int i = 0; i < numbers.size(); ++i) {
  74.         int hash_value = Hash_function(a_hash_index, b_hash_index, numbers[i], numbers.size()); //"Расбрасывание" значений во временную таблицу
  75.         temp_hash[hash_value].push_back(numbers[i]);                                            // для вычисления идеальных хэш-функций
  76.     }
  77.  
  78.     for (int index_first_hash = 0; index_first_hash < numbers.size(); ++index_first_hash) {
  79.         int size = temp_hash[index_first_hash].size();
  80.         if (size > 0) {
  81.             hash_table[index_first_hash] = new int[size * size]; //создание в хэш-таблице квадратичного массива
  82.             for(int j = 0; j < size * size; j++) {
  83.                 hash_table[index_first_hash][j]= -2147483648;
  84.             }
  85.  
  86.             int temp_a = Random(1, big_prime - 1), temp_b = Random(1, big_prime); //генерирование случайных параметров хэш-функции
  87.  
  88.             while (Collizion(temp_hash[index_first_hash], temp_a, temp_b)) { //пока есть коллизии
  89.                 temp_a = Random(1, big_prime - 1);//Генерируем параметры функции
  90.                 temp_b = Random(1, big_prime);    //
  91.             }
  92.  
  93.             table_hash_index[index_first_hash] = new int[3]; //заполнение
  94.             table_hash_index[index_first_hash][0] = temp_a;  //таблицы
  95.             table_hash_index[index_first_hash][1] = temp_b;  //хэш-функций
  96.             table_hash_index[index_first_hash][2] = size*size;//
  97.  
  98.             for(int runner = 0; runner < temp_hash[index_first_hash].size(); ++runner) { //пробегая по массиву
  99.                 int second_hash = Hash_function(temp_a, temp_b, temp_hash[index_first_hash][runner], size*size); //считаем хэш
  100.                 hash_table[index_first_hash][second_hash] = temp_hash[index_first_hash][runner]; //заносим по хэшам в ячейку
  101.             }
  102.         }
  103.     }
  104.     delete[] temp_hash; //удаляем временную таблицу
  105. }
  106.  
  107. FixedSet::~FixedSet() {
  108.     if (hash_table != NULL) {
  109.         for (unsigned int runner = 0; runner < numbers.size(); ++runner) {
  110.             if (hash_table[runner] != NULL) {
  111.                 delete[] hash_table[runner];
  112.             }
  113.         }
  114.         delete[] hash_table;
  115.     }
  116.     if (table_hash_index != NULL)
  117.     {
  118.         for (unsigned int runner = 0; runner < numbers.size(); ++runner) {
  119.             if (table_hash_index[runner] != NULL) {
  120.                 delete[] table_hash_index[runner];
  121.             }
  122.         }
  123.         delete[] table_hash_index;
  124.     }
  125. }
  126.  
  127. const bool FixedSet::Contains(int num_for_search) {
  128.      int first_hash = Hash_function(a_hash_index, b_hash_index, num_for_search, numbers_size); //считаем хэш-первого уровня
  129.      if (hash_table[first_hash] == NULL) {
  130.          return false;
  131.      }
  132.      int a = table_hash_index[first_hash][0]; // Определяем хэш-функцию
  133.      int b = table_hash_index[first_hash][1]; // второго
  134.      int size = table_hash_index[first_hash][2]; // уровня
  135.      int second_hash = Hash_function(a, b, num_for_search, size); // считаем хэш второго уровня
  136.      if (hash_table[first_hash][second_hash] == num_for_search) { //сравниваем
  137.          return true;
  138.      }
  139.      return false;
  140. }
  141.  
  142. int Random(int from, int till) {
  143.     if (till > from) {
  144.         return (from + (((rand() * rand()) % (till - from)) + 1));
  145.     }
  146.     return 0;
  147. }
  148.  
  149. int Hash_function(int a, int b, int x, int n) {
  150.     return ((a * x + b) % big_prime) % n;
  151. }
  152.  
  153. bool Collizion(vector<int>& Array, int a, int b) {
  154.     vector<int> hash_value;
  155.     for(int i = 0; i < Array.size(); ++i) {
  156.         int temp = Hash_function(a, b, Array[i], Array.size() * Array.size()); //считаем хэши
  157.         for(int j = 0; j < hash_value.size(); ++j) {
  158.             if (hash_value[j] == temp && Array[j] != Array[i]) {//если находим такой-же выходим
  159.                 return true;
  160.             }
  161.         }
  162.         hash_value.push_back(temp); //иначе заносим хэш в базу
  163.     }
  164.     return false;
  165. }
Advertisement
Add Comment
Please, Sign In to add comment