Оценка сложности: подсчёт вместо поиска

Домашнее задание

  1. {i} Прочитать про хеш-таблицы в Википедии

  2. Реализовать тип «множество» для произвольно больших целых неотрицательных чисел. Программа должна уметь добавлять число в множество, удалять его оттуда и проверять, содержится ли число в множестве. В частности, должен быстро работать поиск по 106 элементам (например, 104 таких поисков :) ); пользоваться dict не разрешается :)) .

    • Решение: Придумаем функцию H(число), которая для любого числа даёт результат в диапазоне, скажем, 0…105. Создадим список T пустых списков из 105 элементов. Тогда добавление числа будет происходит в список T[H(число)], равно как и удаление, и поиск. Тем самым поиск по большому списку сводится к индексированию и поиску по маленькому списку. H(x) — это и есть хеш-функция, а T[] — хеш-таблица

    • В качестве H(x) в случае случайных чисел можно взять просто x%10**5: longint_hash.py

    • Написать генератор тестовых данных (в частности, генератор длинных случайных чисел)" longint.py

    • Как будет выглядеть H(x), если x — это строки маленьких латинских букв?

  3. Определить, достаточно ли велик период последовательности вида ri=(a·ri-1+b) mod m для заданных a, b и m при i < n << m. Решение: за хеш-функцию взять H(ri)=ri%10000. В таблице хранить не просто списки ri, для которых H(ri) одинаково, а пары вида (ri,количество_появлений) (то есть T[rk%10000]=[[ri, 0], [rj, 0], [rk, 0], …]). Остальное см. выше.

  4. /!\ MCCME Постройте все циклические перестановки строки, отсортируйте их и выпишите последний столбец. Вводится строка, состоящая из маленьких латинских букв, ее длина не превосходит 30000 символов.

Условные обозначения


CategoryClass CategoryVmsh

LecturesVMSH/2012-04-04 (последним исправлял пользователь FrBrGeorge 2012-04-11 14:28:56)