maxtravПопалась задачка. Есть ее решение. Но не могу понять хоть убей, как ее решает автор. Пожалуйста помогите. Растолкуйте решение.
http://www.lotos-khv.narod.ru/dist/lek6.htm

Больше всего улыбнуло желание автора статьи доказать свою правоту, а потому "неудачные" решения расчитываются исходя их миллиарда элементов, а удачное - из миллиона. Круто конечно ))) откуда взято число миллиард?! Да от балды...

Перефразирую. В файле записаны 1'000'000 чисел из интервала 1 - 1'000'001 в случайном порядке. Найти пропущенное число. Как уже сказали, и в том и в другом случае будет как минимум одно число пропущено, нам осталось его найти.

Вот теперь оцениваем задачу правильно. :)

В итоге представленное решение (точнее идея) неплохое. Хотя я предложу немного лучше :)

Я по подобному принципу (на основании, кстати, метода быстрой сортировки) сортировал все числа у себя в программках (когда учился или участвовал в олимпиадах). Сортировка разумеется была побитная (то есть меняем местами числа, если число с соответствующим битом равным 1 стоит левее числа с тем же битом равным нулю. Таким образом рекурсия уходит максимум на n уровней, где n - число бит в числе)

Отвлёкся :) Итак... поясняю решение автора:

У нас есть миллион чисел, которыми можно заполнить без пробелов только миллион первых позиций. Потому, если есть пробел, то он находится в позиции от 1 до 1000000. Этот интервал мы и проверяем. Берём число 500000, начинаем читать файл и сравнивать каждое число с данным. Если прочитанное из файла меньше - прибавляем 1 к счётчику. Если в итоге счётчик равен 500000 - значит первые пол миллиона позиций заполнены без пробелов и нас интересует вторая половина миллиона. Итак, когда мы узнали в какой половине миллиона интересующий нас пропуск, повторяем то же действие для соответствующей половины миллиона, и делим ещё на 2 интервала... и так пока у нас не останется интервал в 1... именно он и будет нашим искомым пропуском.

Это всё нормальными словами и без лишних действий, которые он описал...

Не буду сильно комментировать его решение... из недостатков отмечу - он говорит о миллиардах операций, зато его программа сама вынуждена провести чтение 20'000'000 чисел по 4 байта (при чтении с диска в 512 байт, то есть по одному сектору, это будет около 16000 операций чтения). Замечу что методу быстрой сортировки потребуется приблизительно столько же... просто у него ещё будут затраты на запись чисел в их новые позиции.


На практике такая задача решилась бы в разы легче (мной по крайней мере). Я бы завёл файл на миллион байт и заполнил бы его нулями. А потом читая число из первого файла, выставлял бы байт во втором файле с соответствующим смещением в единицу (можно и с битами работать конечно, но тут вопрос простоты реализации. С битами не удобно работать). В итоге, задача свелась бы к чтению и записи миллиона чисел. После записи второго файла читаем его побайтово и смещении байта со значением 0 даёт нам искомое число (пропущенную позицию).

Кстати... на практике не бывает ограничения "не использовать массивы". :) А учитывая метод решения, если заюзать массив как напрерывный набор двоичных флагов, то и памяти на такой массив потребуется 8МБ. Большинству даже вэб приложений такое количество памяти спокойно выделяется (им выделяется даже в разы больше). Потому правильно тут сказали, при разумных ограничениях задача решаема в 2 прохода... 1 - пишем массив, второй - ищем пропуск.