Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Пусть все натуральные числа исходно организованы в список в естественном порядке.
- Разрешается выполнить следующую операцию: 𝑠𝑤𝑎𝑝(𝑎, 𝑏). Эта операция возвращает в
- качестве результата расстояние в текущем списке между числами 𝑎 и 𝑏 и меняет их местами.
- Задана последовательность операций 𝑠𝑤𝑎𝑝. Требуется вывести в выходной файл результат всех этих операций.
- Первая строка входного файла содержит число 𝑛 (1 6 𝑛 6 200 000) — количество операций.
- Каждая из следующих 𝑛 строк содержит по два числа в диапазоне от 1 до 10^9 — аргументы операций 𝑠𝑤𝑎𝑝.
- Хеш-таблицы из STL (unordered_map и т.д.) получат TL.
- Придётся писать свою хеш-таблицу.
- Самая быстрая и простая хеш-таблица – хеш-таблица с открытой адресацией.
- */
- #include "stdafx.h"
- #include "iostream"
- #include "ctime"
- #include "string"
- using namespace std;
- int mabs(int x) { return (x >= 0)? x : -x; }
- // Поиск индекса числа по значению
- // - 1 если не найдено
- int getIndexByValue(int *arr, int N, int value) {
- for (int k = 0; k < N; k++) {
- if (arr[k] == value) { return k; }
- }
- return -1;
- }
- // Замена местами элементов с индексами first_index и second_index в массивe arr
- int swap(int *arr, int first_index, int second_index) {
- int temp = arr[first_index];
- arr[first_index] = arr[second_index];
- arr[second_index] = temp;
- return mabs(second_index - first_index);
- }
- // Генерации массива
- void input(int *arr, int N) {
- for (int k = 0; k < N; k++) {
- arr[k] = k + 1;
- }
- }
- // Вывод массива на экран
- void output(int *arr, int N) {
- for (int k = 0; k < N; k++) { cout << arr[k] << ' '; }
- cout << '\n';
- }
- int main() {
- setlocale(LC_ALL, "Rus");
- srand(time(0)); //чтобы начальное число, к которому привязан метод rand(), менялось с каждым запуском программы
- int N = 5; //размер массива
- int arr[100];
- int oper[4][2] = { {1, 4}, {1, 3}, {4, 5}, {1, 4} };
- int CountOper = 4;
- unsigned int start_time = clock(); // начальное время
- input(arr, N); // генерация массива
- int first_value;
- int second_value;
- for (int k = 0; k < CountOper; k++) {
- cout << k + 1 << " итерации: " << endl;
- first_value = oper[k][0];
- second_value = oper[k][1];
- int first_index = getIndexByValue(arr, N, first_value);
- int second_index = getIndexByValue(arr, N, second_value);
- cout << " Расстояние: " << swap(arr, first_index, second_index) << endl;
- cout << " Текущий массива: "; output(arr, N);
- }
- unsigned int end_time = clock(); //конечное время
- unsigned int search_time = end_time - start_time;
- cout << " Время работы программы: " << search_time / 1000.0 << " сек" << endl;
- system("pause"); //Ожидание, позволяющее увидеть результат программы
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement