impressive_i

swap elemets

Sep 23rd, 2020 (edited)
994
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×