И еще задачка

И еще задачка

На ленте записано 10^9 различных 32-битных чисел.

Найти одно 32-битное число, которое отсутствует на ленте,
используя как можно меньше памяти. Ленту, как обычно,
можно только читать.

Миша

Re: И еще задачка

Mikhail Kimmelman wrote:

На ленте записано 10^9 различных 32-битных чисел.

Найти одно 32-битное число, которое отсутствует на ленте,
используя как можно меньше памяти. Ленту, как обычно,
можно только читать.
...


Если под "различных" подразумевается, что все числа уникальны, то задача
решается так.

Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M = 2^31. Делаем
полный просмотр ленты отдельно подчитывая общее количество чисел из диапазона D,
которые <M и которые >=M. Финальные значения счетчиков сразу скажут нам в какой
половине диапазона D не хватает числа. Принимаем эту половину за новый D и
рассматриваем его по тому же принципу, пока не добреремся до конкретного
значения (каждый раз, разумеется, придется просмативать ленту целиком).

(J. Bentley, Programming Pearls)

--
Best regards,
Andrey Tarasevich

Re: И еще задачка


"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:--2dnf0KRPU3L3nanZ2dnUVZ_veinZ2d@comcast.com...



Найти одно 32-битное число, которое отсутствует на ленте,
используя как можно меньше памяти. Ленту, как обычно,
можно только читать.
...


Если под "различных" подразумевается, что все числа уникальны, то задача
решается так.

Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M = 2^31.
Делаем полный просмотр ленты отдельно подчитывая общее количество чисел из
диапазона D, которые <M и которые >=M. Финальные значения счетчиков сразу
скажут нам в какой половине диапазона D не хватает числа. Принимаем эту
половину за новый D и рассматриваем его по тому же принципу, пока не
добреремся до конкретного значения (каждый раз, разумеется, придется
просмативать ленту целиком).

(J. Bentley, Programming Pearls)


Я немного неудачно сформулировал.
На ленте нету многих чисел (2^32 - 10^9). Нужно найти какое-то одно из
них.

Миша

Re: И еще задачка


"Mikhail Kimmelman" <mikhail.kimmelman@gmail.com> wrote in message
news:fs2c7i$2k69$1@mamba.crocodile.org...




Найти одно 32-битное число, которое отсутствует на ленте,
используя как можно меньше памяти. Ленту, как обычно,
можно только читать.
...


Если под "различных" подразумевается, что все числа уникальны, то задача
решается так.

Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M = 2^31.
Делаем полный просмотр ленты отдельно подчитывая общее количество чисел
из диапазона D, которые <M и которые >=M. Финальные значения счетчиков
сразу скажут нам в какой половине диапазона D не хватает числа. Принимаем
эту половину за новый D и рассматриваем его по тому же принципу, пока не
добреремся до конкретного значения (каждый раз, разумеется, придется
просмативать ленту целиком).

(J. Bentley, Programming Pearls)


Я немного неудачно сформулировал.
На ленте нету многих чисел (2^32 - 10^9). Нужно найти какое-то одно из
них.


Кажется сообразил.
Приведенное решение вроде находит одно из многих пропущенных.

Миша

Re: И еще задачка

Mikhail Kimmelman wrote:



Если под "различных" подразумевается, что все числа уникальны, то
задача решается так.

Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M =
2^31. Делаем полный просмотр ленты отдельно подчитывая общее
количество чисел из диапазона D, которые <M и которые >=M. Финальные
значения счетчиков сразу скажут нам в какой половине диапазона D не
хватает числа. Принимаем эту половину за новый D и рассматриваем его
по тому же принципу, пока не добреремся до конкретного значения
(каждый раз, разумеется, придется просмативать ленту целиком).

(J. Bentley, Programming Pearls)


Я немного неудачно сформулировал.
На ленте нету многих чисел (2^32 - 10^9). Нужно найти какое-то одно
из них.


Кажется сообразил.
Приведенное решение вроде находит одно из многих пропущенных.
...


Да. Более того, это решение, при желании, позволяет найти все пропущенные.

--
Best regards,
Andrey Tarasevich

Re: И еще задачка

"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:jaWdneA6asM3WnnanZ2dnUVZ_ozinZ2d@comcast.com...





Сначала рассматриваем весь диапазон D = [0, 2^32). Его середина M =
2^31. Делаем полный просмотр ленты отдельно подчитывая общее количество
чисел из диапазона D, которые <M и которые >=M. Финальные значения
счетчиков сразу скажут нам в какой половине диапазона D не хватает
числа. Принимаем эту половину за новый D и рассматриваем его по тому же
принципу, пока не добреремся до конкретного значения (каждый раз,
разумеется, придется просмативать ленту целиком).

(J. Bentley, Programming Pearls)


Я немного неудачно сформулировал.
На ленте нету многих чисел (2^32 - 10^9). Нужно найти какое-то одно из
них.


Кажется сообразил.
Приведенное решение вроде находит одно из многих пропущенных.
...


Да. Более того, это решение, при желании, позволяет найти все
пропущенные.


Ну да. Рассматривая, видимо, все интервалы, где не хватает числа.

Вроде, не сложно.
А я протупил очередной раз :)

Миша

Re: Re: И еще задачка

On Sat, 22 Mar 2008 12:09:01 +0200, Mikhail Kimmelman wrote:




Да. Более того, это решение, при
желании, позволяет найти все
пропущенные.


Ну да. Рассматривая, видимо, все
интервалы, где не хватает числа.

Вроде, не сложно.
А я протупил очередной раз :)


Еще проще, Ж) берем числа подряд и
просматриваем ленту на предмет их
наличия. На просмотр ограничений нет.
Самое эфективное по условию задачи
решение, памяти надо на всего одно число
и позицию. (предпологая наличие
оператора сравнения со значением на
ленте по позиции)


ЗЫ: Это в battlezone2 была такая возможность
определить какими юнитами игроки могут
пользоваться при старте. Обычно
разрешались только самые слабые, но
некоторые стартовали сервер разрешив
все. Тогда берем супер-танк или ходячего
монстра и тупо выносим базу противника
сразу Ж)