Тогда и я для Вас тоже что-нибудь заблокирую, потому что этот сайт существует только на доходы от показа рекламы.
Для восстановления полноценного доступа к содержимому сайта нужно совсем немного:
На ленте записано 10^9 различных 32-битных чисел.
Найти одно 32-битное число, которое отсутствует на ленте,
используя как можно меньше памяти. Ленту, как обычно,
можно только читать.
...
Найти одно 32-битное число, которое отсутствует на ленте,
используя как можно меньше памяти. Ленту, как обычно,
можно только читать.
...
Если под "различных" подразумевается, что все числа уникальны, то задача
решается так.
Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M = 2^31.
Делаем полный просмотр ленты отдельно подчитывая общее количество чисел из
диапазона D, которые <M и которые >=M. Финальные значения счетчиков сразу
скажут нам в какой половине диапазона D не хватает числа. Принимаем эту
половину за новый D и рассматриваем его по тому же принципу, пока не
добреремся до конкретного значения (каждый раз, разумеется, придется
просмативать ленту целиком).
(J. Bentley, Programming Pearls)
Найти одно 32-битное число, которое отсутствует на ленте,
используя как можно меньше памяти. Ленту, как обычно,
можно только читать.
...
Если под "различных" подразумевается, что все числа уникальны, то задача
решается так.
Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M = 2^31.
Делаем полный просмотр ленты отдельно подчитывая общее количество чисел
из диапазона D, которые <M и которые >=M. Финальные значения счетчиков
сразу скажут нам в какой половине диапазона D не хватает числа. Принимаем
эту половину за новый D и рассматриваем его по тому же принципу, пока не
добреремся до конкретного значения (каждый раз, разумеется, придется
просмативать ленту целиком).
(J. Bentley, Programming Pearls)
Я немного неудачно сформулировал.
На ленте нету многих чисел (2^32 - 10^9). Нужно найти какое-то одно из
них.
Если под "различных" подразумевается, что все числа уникальны, то
задача решается так.
Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M =
2^31. Делаем полный просмотр ленты отдельно подчитывая общее
количество чисел из диапазона D, которые <M и которые >=M. Финальные
значения счетчиков сразу скажут нам в какой половине диапазона D не
хватает числа. Принимаем эту половину за новый D и рассматриваем его
по тому же принципу, пока не добреремся до конкретного значения
(каждый раз, разумеется, придется просмативать ленту целиком).
(J. Bentley, Programming Pearls)
Я немного неудачно сформулировал.
На ленте нету многих чисел (2^32 - 10^9). Нужно найти какое-то одно
из них.
Кажется сообразил.
Приведенное решение вроде находит одно из многих пропущенных.
...
Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M =
2^31. Делаем полный просмотр ленты отдельно подчитывая общее количество
чисел из диапазона D, которые <M и которые >=M. Финальные значения
счетчиков сразу скажут нам в какой половине диапазона D не хватает
числа. Принимаем эту половину за новый D и рассматриваем его по тому же
принципу, пока не добреремся до конкретного значения (каждый раз,
разумеется, придется просмативать ленту целиком).
(J. Bentley, Programming Pearls)
Я немного неудачно сформулировал.
На ленте нету многих чисел (2^32 - 10^9). Нужно найти какое-то одно из
них.
Кажется сообразил.
Приведенное решение вроде находит одно из многих пропущенных.
...
Да. Более того, это решение, при желании, позволяет найти все
пропущенные.
Да. Более того, это решение, при
желании, позволяет найти все
пропущенные.
Ну да. Рассматривая, видимо, все
интервалы, где не хватает числа.
Вроде, не сложно.
А я протупил очередной раз :)