Довольно общих слов! Эта глава посвящена трем небольшим задачам. Попробуйте решить их самостоятельно, прежде чем продолжить ознакомление с этой главой.
0. Пусть есть некий файл, содержащий не более четырех миллиардов 32-битных целых чисел в случайном порядке. Нужно найти число, которое отсутствует в файле (а хотя бы одно число будет отсутствовать наверняка — почему?). Как бы вы решили эту задачу при наличии неограниченной оперативной памяти? Как вы решите ее, если оперативная память ограничена парой сотен килобайт, но разрешается использование нескольких временных файлов?
1. Осуществите циклический сдвиг одномерного массива из п элементов на i позиций влево. Например, если n=8, a i=3, вектор abcdefgh превращается в defghabc. Простейшая программа использует n-элементный вспомогательный массив и выполняет задачу за п шагов. Можете ли вы сдвинуть массив за время, пропорциональное п, используя лишь несколько десятков байт под дополнительные переменные?
Дан словарь английского языка. Требуется найти все наборы анаграмм. Например, слова pots, stop и tops являются анаграммами друг для друга, поскольку каждое из этих слов может быть получено перестановкой букв любого другого.
Опубликовал vovan666
April 16 2013 23:34:26 ·
0 Комментариев ·
3534 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
