Реализовать алгоритм поиска минимального элемента заданной последовательности…
- User
Реализовать алгоритм поиска минимального элемента заданной последовательности размерностью N (250<N<1000), используя метод SQRT - декомпозиции на языке C++
- Assistant
Алгоритм SQRT-декомации — это удобный подход для решения задач, которые требуют частых запросов, но редких обновлений. В случае поиска минимального элемента в заданной последовательности можно разбить массив на блоки и использовать предварительно рассчитанные минимумы для быстрого ответа на запросы.
Вот пример реализации алгоритма поиска минимального элемента с использованием SQRT-декомпозиции в C++:
#include <iostream> #include <vector> #include <cmath> #include <limits> class SqrtDecomposition { public: SqrtDecomposition(const std::vector<int>& arr) : original(arr), n(arr.size()) { blockSize = static_cast<int>(sqrt(n)); blocks.resize((n + blockSize - 1) / blockSize, std::numeric_limits<int>::max()); // Создание блоков for (int i = 0; i < n; ++i) { blocks[i / blockSize] = std::min(blocks[i / blockSize], arr[i]); } } // Метод для обновления элемента в массиве void update(int index, int value) { original[index] = value; // Обновление соответствующего блока int blockIndex = index / blockSize; blocks[blockIndex] = std::numeric_limits<int>::max(); // Пересчитываем минимумы в блоке for (int i = blockIndex * blockSize; i < std::min(n, (blockIndex + 1) * blockSize); ++i) { blocks[blockIndex] = std::min(blocks[blockIndex], original[i]); } } // Метод для поиска минимума в диапазоне [l, r] int query(int l, int r) { int blockL = l / blockSize; int blockR = r / blockSize; int minVal = std::numeric_limits<int>::max(); // Обработка полных блоков if (blockL == blockR) { for (int i = l; i <= r; ++i) { minVal = std::min(minVal, original[i]); } } else { // Левый неполный блок for (int i = l; i < (blockL + 1) * blockSize && i < n; ++i) { minVal = std::min(minVal, original[i]); } // Полные блоки for (int i = blockL + 1; i < blockR; ++i) { minVal = std::min(minVal, blocks[i]); } // Правый неполный блок for (int i = blockR * blockSize; i <= r && i < n; ++i) { minVal = std::min(minVal, original[i]); } } return minVal; } private: std::vector<int> original; // Исходный массив std::vector<int> blocks; // Блоки и их минимумы int n; // Размер исходного массива int blockSize; // Размер блока }; int main() { std::vector<int> arr = {5, 2, 3, 9, 8, 6, 7, 10, 1, 4}; // пример массива SqrtDecomposition sqrtDec(arr); std::cout << "Минимум в диапазоне [0, 5]: " << sqrtDec.query(0, 5) << std::endl; std::cout << "Минимум в диапазоне [2, 9]: " << sqrtDec.query(2, 9) << std::endl; sqrtDec.update(4, 0); // обновляем элемент arr[4] на 0 std::cout << "Минимум в диапазоне [0, 5] после обновления: " << sqrtDec.query(0, 5) << std::endl; return 0; }Описание кода:
-
Класс
SqrtDecomposition: данный класс принимает исходный массив и создает блоки с минимальными значениями для ускорения поиска минимума. -
Методы:
update(int index, int value)обновляет элемент массива и пересчитывает минимум в соответствующем блоке.query(int l, int r)возвращает минимальное значение в диапазоне [l, r].
-
Пример использования: В
mainсоздается пример массива, выполняются запросы на минимум, и демонстрируется обновление элемента.
Этот код должен работать для пределах, указанных в вашем запросе (250 < N < 1000).
-
- User
убери классы
- Assistant
Если убрать классы и реализовать алгоритм с помощью простых функций, то код будет выглядеть следующим образом:
#include <iostream> #include <vector> #include <cmath> #include <limits> const int MAX_N = 1000; // Максимальный размер массива const int MIN_N = 250; // Минимальный размер массива // Функция для инициализации блоков и минимальных значений void initSqrtDecomposition(const std::vector<int>& arr, int n, int blockSize, std::vector<int>& blocks) { for (int i = 0; i < n; ++i) { blocks[i / blockSize] = std::min(blocks[i / blockSize], arr[i]); } } // Функция для обновления элемента в массиве void update(int index, int value, std::vector<int>& arr, std::vector<int>& blocks, int blockSize, int n) { arr[index] = value; int blockIndex = index / blockSize; blocks[blockIndex] = std::numeric_limits<int>::max(); for (int i = blockIndex * blockSize; i < std::min(n, (blockIndex + 1) * blockSize); ++i) { blocks[blockIndex] = std::min(blocks[blockIndex], arr[i]); } } // Функция для поиска минимума в диапазоне [l, r] int query(int l, int r, const std::vector<int>& arr, const std::vector<int>& blocks, int blockSize, int n) { int blockL = l / blockSize; int blockR = r / blockSize; int minVal = std::numeric_limits<int>::max(); if (blockL == blockR) { for (int i = l; i <= r; ++i) { minVal = std::min(minVal, arr[i]); } } else { // Левый неполный блок for (int i = l; i < (blockL + 1) * blockSize && i < n; ++i) { minVal = std::min(minVal, arr[i]); } // Полные блоки for (int i = blockL + 1; i < blockR; ++i) { minVal = std::min(minVal, blocks[i]); } // Правый неполный блок for (int i = blockR * blockSize; i <= r && i < n; ++i) { minVal = std::min(minVal, arr[i]); } } return minVal; } int main() { int n; std::cout << "Введите размер массива (250 < N < 1000): "; std::cin >> n; if (n <= MIN_N || n >= MAX_N) { std::cerr << "Ошибка: размер массива должен быть в пределах от 250 до 1000." << std::endl; return 1; } std::vector<int> arr(n); std::cout << "Введите элементы массива: "; for (int i = 0; i < n; ++i) { std::cin >> arr[i]; } int blockSize = static_cast<int>(sqrt(n)); std::vector<int> blocks((n + blockSize - 1) / blockSize, std::numeric_limits<int>::max()); // Инициализация блоков initSqrtDecomposition(arr, n, blockSize, blocks); // Примеры запросов std::cout << "Минимум в диапазоне [0, 5]: " << query(0, 5, arr, blocks, blockSize, n) << std::endl; std::cout << "Минимум в диапазоне [2, 9]: " << query(2, 9, arr, blocks, blockSize, n) << std::endl; // Обновление элемента массива int index, value; std::cout << "Введите индекс элемента для обновления: "; std::cin >> index; std::cout << "Введите новое значение: "; std::cin >> value; update(index, value, arr, blocks, blockSize, n); std::cout << "Минимум в диапазоне [0, 5] после обновления: " << query(0, 5, arr, blocks, blockSize, n) << std::endl; return 0; }Описание кода:
-
Функции:
initSqrtDecomposition: инициализирует блоки с минимальными значениями.update: обновляет заданный элемент в массиве и пересчитывает минимум в соответствующем блоке.query: возвращает минимальное значение в диапазоне [l, r].
-
Основная программа (
main):- Просит пользователя ввести размер массива и сам массив.
- Инициализирует блоки с минимальными значениями.
- Приводит примеры вызовов функции
queryиupdate.
Этот код позволяет вам находить минимальные значения в заданных диапазонах и обновлять элементы, без использования классов.
-