Теперь, когда мы слегка размялись, можно обратиться к задаче 1. На вход поступает последовательный файл (записанный на каком-либо носителе или на диске — хотя к диску и можно обращаться произвольно, последовательное чтение обычно осуществляется с гораздо большей скоростью). Этот файл содержит не более четырех миллиардов 32-битных целых чисел в произвольном порядке, а нам необходимо найти число, отсутствующее в этом файле. Такое число обязательно есть, поскольку 32-битных целых чисел всего 242, или 4 294 967 296. При наличии неограниченного объема памяти мы могли бы воспользоваться битовым массивом, описанным в главе 1, и выделить 536 870 912 байт (по 8 бит каждый) под все возможные целые числа. Однако нам предлагается найти недостающее число, используя лишь несколько сот байт оперативной памяти и несколько вспомогательных файлов последовательного доступа. Чтобы реализовать двоичный поиск в этой ситуации, прежде всего нужно определить диапазон, представление элементов диапазона и метод проверки, позволяющий определить, в какой половине этого диапазона не хватает числа.
Диапазоном у нас будет набор целых чисел, в котором заведомо недостает по крайней мере одного элемента, а представлять мы его будем в виде файла, содержащего все числа этого диапазона. И вот: озарение! Мы можем проверять диапазон, подсчитывая количество элементов, меньших и больших значения середины диапазона. Либо в верхней, либо в нижней половине диапазона будет не более половины общего количества чисел в диапазоне. Поскольку хотя бы один элемент во всем диапазоне обязательно отсутствует, в одной из половин диапазона также будет отсутствовать по крайней мере одни элемент, и в этой половине будет меньшее число элементов. Вот основные составляющие алгоритма двоичного поиска. Попробуйте соединить их вместе самостоятельно, прежде чем подсмотреть ответ Эда Рейнгольда (Ed Reingold).
Опубликовал vovan666
April 16 2013 23:34:32 ·
0 Комментариев ·
3118 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
