Пропавшие числа - 11 Сентября 2015

Главная » » Пропавшие числа

07:14 Пропавшие числа
Вот интересная задачка. Надеюсь не баян:Имеется файл, заполненный всевозможными (без повторов) 32-битными числами кроме каких-то четырех. Необходимо определить эти 4 числа.UPD: считаем что метод с использованием большого объема памяти найден. Ищем метод использующий мало памяти (<512 Mb).UPD2 (Решения. Для просмотра требуется выделить участок мышкой):Итак подводим итоги. Были предложены следующие правильные решения (в порядке увеличения эффективности):1) Вариации Counting Sort, то есть подсчет по битовой маске каких элементов не хватает. В лучшем случае требует 512 Мбайт памяти.2) Улучшенный Counting Sort на некотором доступном участке памяти. То есть интервал 4 млрд. разбивается на 4 части. Делается 4 отдельных прохода в итоге за счет увеличения времени выполнения добиваемся сокращения памяти.3) Бинарный поиск по отрезку - значения не храним, память требуется буквально для нескольких переменных. Сначала считаем количество чисел на отрезке от 0 до 2 млрд, если какого то числа не хватает делим интервал дальше и.т.д. В худшем случае имеем 128 проходов, что долго.4) Ну и наконец ИМХО самый эффективный способ. Задача решается в 2 прохода. Памяти требуется около 4Кбайт. Число разбивается на 4 части по байту каждое, для каждого отдельного значения байта считается количество его вхождений. Там где видим недобор по количеству вхождений, понимаем, что этот байт входит в состав отсутствующего числа. Далее заводим булевый массив [4][4][4][4] и за второй проход находим какие числа входят в него, а там где остались 4 нолика - те и есть наши искомые числа. Этот же метод можно использовать разделив число на 2 части, вместо 4, но количество памяти в этом случае увеличится.Отдельно отмечу метод предложенный akkort'ом он мне показался довольно сложным. Его правильность ещё предстоит проверить. =)Все комменты открыты
1 2 3 4 5 Просмотров: 488 \| Добавил: admin \| Рейтинг: 0.0/0