Предмет: Программирование. Добавлен: 13.11.2020. Год: 2018. Страниц: 9. Оригинальность по antiplagiat.ru: 20% |
|
A. Хеш-функция В задачах поиска часто используются так называемые хеш-функции. Хеш-функции могут определяться самым разнообразным образом — например, так: • Вначале число возводится в квадрат. • Если полученное число имеет три и более цифр, то первая и последняя его цифры отбрасываются. • Ответом будет остаток от деления числа на M (где M – заданное заранее значение). Рассмотрим пример. Пусть M = 10, входное число = -37. 1. Возводим в квадрат: ?-?372?=?1369. 2. Число имеет более двух цифр, поэтому отбрасываем первую и последнюю цифру — получаем 36. 3. Берём остаток от деления на M — получаем ответ 6. Реализуйте вычисление такой хеш-функции и вычислите её для каждого из N входных чисел. Входные данные В первой строке входных данных записаны два целых числа M и N (1???M,?N???105). Во второй строке записаны N целых чисел, для каждого из которых вы должны сосчитать и вывести значение хеш-функции. Все числа не превышают по модулю 109. Выходные данные Выведите N целых чисел — ответы. Пример входные данные 10 5 -37 37 5 2 -352145261 выходные данные 6 6 5 4 2 Код программы: #include ‹iostream› using namespace std; long long hash_function(long long a,int m){ a *= a; if (a›99){ long long p = 1; while (a / p › 9) p *= 10; a = a % p; a = a/10; } return a%m; } int main() { int n,m; long long a; cin ›› m; cin ›› n; for (int i = 0;i‹n;i++){ cin ›› a; cout ‹‹ hash_function(a,m) ‹‹ " "; } } Описание программы: процедура hash_function реализует заданный алгоритм хеширования: возводит число в квадрат, если число больше 100, то удаляет первую и последнюю цифры, выводит остаток от деления на m. B. Хеширование с цепочками Одним из эффективных способов реализации множеств в памяти компьютера является хеш-таблица. Вставка нового элемента в хеш-таблицу начинается с вычисления хеш-функции от ключа. Получающееся значение является индексом в хеш-таблице. В данной задаче используется простейший вариант хеш-функции: h(x)?=?x mod M (где M – размер хеш-таблицы). Заметим, что возможна ситуация, когда для разных ключей хеш-функция даст одно и то же значение. Такая ситуация называется коллизией. Одним из способов разрешения коллизий является метод цепочек: элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку — связный список. На рисунке показан пример результирующей хеш-таблицы после вставки последовательности чисел 75, 66, 42, 192, 91, 40, 49, 87, 67, 16, 417, 130, 372, 227 в хеш-таблицу размера M?=?10... Описание алгоритма: выполняется цикл, пока полиномиальная функция не станет равна v, внутри цикла идет подбор сроки t. Подбор осуществляется следующим образом: процедура next каждый раз увеличивает последний элемент строки на 1,если значение стало равно 9, то переходит к предыдущему и действует точно также, если |
|
Перейти к полному тексту работы |