impressive_i

swap elemets

Sep 23rd, 2020 (edited)
885
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Пусть все натуральные числа исходно организованы в список в естественном порядке.
  3. Разрешается выполнить следующую операцию: 𝑠𝑤𝑎𝑝(𝑎, 𝑏). Эта операция возвращает в
  4. качестве результата расстояние в текущем списке между числами 𝑎 и 𝑏 и меняет их местами.
  5. Задана последовательность операций 𝑠𝑤𝑎𝑝. Требуется вывести в выходной файл результат всех этих операций.
  6. Первая строка входного файла содержит число 𝑛 (1 6 𝑛 6 200 000) — количество операций.
  7. Каждая из следующих 𝑛 строк содержит по два числа в диапазоне от 1 до 10^9 — аргументы операций 𝑠𝑤𝑎𝑝.
  8. Хеш-таблицы из STL (unordered_map и т.д.) получат TL.
  9. Придётся писать свою хеш-таблицу.
  10. Самая быстрая и простая хеш-таблица – хеш-таблица с открытой адресацией.
  11. */
  12.  
  13. #include "stdafx.h"
  14. #include "iostream"
  15. #include "ctime"
  16. #include "string"
  17.  
  18. using namespace std;
  19.  
  20. int mabs(int x) { return (x >= 0)? x : -x; }
  21.  
  22. // Поиск индекса числа по значению
  23. // - 1 если не найдено
  24. int getIndexByValue(int *arr, int N, int value) {
  25.     for (int k = 0; k < N; k++) {
  26.         if (arr[k] == value) { return k; }
  27.     }
  28.     return -1;
  29. }
  30.  
  31. // Замена местами элементов с индексами first_index и second_index в массивe arr
  32. int swap(int *arr, int first_index, int second_index) {
  33.     int temp = arr[first_index];
  34.     arr[first_index] = arr[second_index];
  35.     arr[second_index] = temp;
  36.     return mabs(second_index - first_index);
  37. }
  38.  
  39. // Генерации массива
  40. void input(int *arr, int N) {
  41.     for (int k = 0; k < N; k++) {
  42.         arr[k] = k + 1;
  43.     }
  44. }
  45.  
  46. // Вывод массива на экран
  47. void output(int *arr, int N) {
  48.     for (int k = 0; k < N; k++) { cout << arr[k] << ' '; }
  49.     cout << '\n';
  50. }
  51.  
  52. int main() {
  53.     setlocale(LC_ALL, "Rus");
  54.  
  55.     srand(time(0)); //чтобы начальное число, к которому привязан метод rand(), менялось с каждым запуском программы
  56.  
  57.     int N = 5; //размер массива
  58.     int arr[100];
  59.     int oper[4][2] = { {1, 4}, {1, 3}, {4, 5}, {1, 4} };
  60.     int CountOper = 4;
  61.  
  62.     unsigned int start_time = clock(); // начальное время
  63.  
  64.     input(arr, N); // генерация массива
  65.  
  66.     int first_value;
  67.     int second_value;
  68.     for (int k = 0; k < CountOper; k++) {
  69.         cout << k + 1 << " итерации: " << endl;
  70.         first_value = oper[k][0];
  71.         second_value = oper[k][1];
  72.  
  73.         int first_index = getIndexByValue(arr, N, first_value);
  74.         int second_index = getIndexByValue(arr, N, second_value);
  75.  
  76.         cout << " Расстояние: " << swap(arr, first_index, second_index) << endl;
  77.         cout << " Текущий массива: "; output(arr, N);
  78.     }
  79.  
  80.     unsigned int end_time = clock(); //конечное время
  81.     unsigned int search_time = end_time - start_time;
  82.     cout << " Время работы программы: " << search_time / 1000.0 << " сек" << endl;
  83.  
  84.     system("pause"); //Ожидание, позволяющее увидеть результат программы
  85.     return 0;
  86. }
RAW Paste Data