Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Работа № 123423
Наименование:
Контрольная Решение задач с использованием хеш-функций
Информация:
Тип работы: Контрольная.
Предмет: Программирование.
Добавлен: 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, то переходит к предыдущему и действует точно также, если
* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.
