Задачка

Задачка

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?

Миша

Re: Задачка


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

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?

прекратить маяться дурью. и заказать памяти столько, сколько требуется плюс
25%й резерв.

Re: Задачка

Hello, Mikhail Kimmelman!
You wrote on Fri, 21 Mar 2008 09:41:33 +0200:


На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?


А резать ленту можно?


Миша


Георгий Малышев

Re: Задачка

"Georgy Malyshev" <g@o.n> wrote in message
news:47e3c551$0$15168$607ed4bc@cv.net...



На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?


А резать ленту можно?


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

Миша

Re: Задачка

On Mar 21, 6:40 pm, "Mikhail Kimmelman" <mikhail.kimmel...@gmail.com>
wrote:




На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?

А резать ленту можно?

Ленту можно только последовательно читать,


Надеюсь, неоднократно?


а больше ничего с ней нельзя делать.


Kit.

Re: Задачка

"Nikita V. Belenki" <fido7@kits.net> wrote in message
news:e872cf68-e793-403d-ab06-502356de0096@c19g2000prf.googlegroups.com...





На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?

А резать ленту можно?

Ленту можно только последовательно читать,


Надеюсь, неоднократно?


Думаю, да.
Говорят, это сложная задача.

Миша

Re: Задачка


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

"Nikita V. Belenki" <fido7@kits.net> wrote in message
news:e872cf68-e793-403d-ab06-502356de0096@c19g2000prf.googlegroups.com...





На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?

А резать ленту можно?

Ленту можно только последовательно читать,


Надеюсь, неоднократно?


Думаю, да.
Говорят, это сложная задача.


Присоединяюсь к мнению не морочить голову и купить памяти.
Умение решать такие задачи сейчас сравнимо с умением
управлять матричным принтером с помощью эскэйп последовательностей.



Миша


Re: Задачка

За один проход найдем, в какой тысяче эта медиана сидит, а во втором проходе
уточним

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

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?

Миша


Re: Задачка

Mikhail Kimmelman wrote:

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?


А какой размер у каждого числа? Если каждое число имеет не более 10^9 возможных
значений, можно просто за один проход построить гистограмму, потом середина в
гистограмме тоже находится за один проход.

Re: Задачка

Cyril Novikov wrote:

Mikhail Kimmelman wrote:

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?


А какой размер у каждого числа? Если каждое число имеет не более 10^9
возможных значений, можно просто за один проход построить
гистограмму, потом середина в гистограмме тоже находится за один
проход.


У Миши просто страсть к бесполезным задачам :-)

Re: Задачка

Hello, Cyril Novikov!
You wrote on Fri, 21 Mar 2008 14:43:19 -0700:


Mikhail Kimmelman wrote:

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?




А какой размер у каждого числа? Если каждое число имеет не более 10^9 возможных
значений, можно просто за один проход построить гистограмму, потом середина в
гистограмме тоже находится за один проход.


Там наверняка огроменные комплексные числа. Интереснее
другое - кто и зачем записал их на ленту? И хорошо ли это
для евреев?

Георгий Малышев

Re: Задачка


"Georgy Malyshev" <g@o.n> wrote in message
news:47e45502$0$15176$607ed4bc@cv.net...

Hello, Cyril Novikov!
You wrote on Fri, 21 Mar 2008 14:43:19 -0700:


Mikhail Kimmelman wrote:

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?




А какой размер у каждого числа? Если каждое число имеет не более 10^9

возможных

значений, можно просто за один проход построить гистограмму, потом

середина в

гистограмме тоже находится за один проход.


Там наверняка огроменные комплексные числа. Интереснее
другое - кто и зачем записал их на ленту? И хорошо ли это
для евреев?


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


Re: Задачка

Hello, Рынский, Дениска (старшой)!
You wrote on Fri, 21 Mar 2008 17:39:11 -0700:


РДс> "Georgy Malyshev" <g@o.n> wrote in message
РДс> news:47e45502$0$15176$607ed4bc@cv.net...


Hello, Cyril Novikov!
You wrote on Fri, 21 Mar 2008 14:43:19 -0700:






Mikhail Kimmelman wrote:

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?








А какой размер у каждого числа? Если каждое число имеет не более 10^9

возможных

значений, можно просто за один проход построить гистограмму, потом

середина в

гистограмме тоже находится за один проход.






Там наверняка огроменные комплексные числа. Интереснее
другое - кто и зачем записал их на ленту? И хорошо ли это
для евреев?



РДс> Комплексные числа не сравниваются, у них нет понятия больше или меньше, это
РДс> надо знать.


Так ведь это делает задачку только интресенее, не так ли?
Я уж не говорю о том, что вопрос кто и зачем их записал на
ленту все равно остается.

Георгий Малышев

Re: Задачка


"Georgy Malyshev" <g@o.n> wrote in message
news:47e4586e$0$15189$607ed4bc@cv.net...

Hello, Рынский, Дениска (старшой)!
You wrote on Fri, 21 Mar 2008 17:39:11 -0700:


РДс> "Georgy Malyshev" <g@o.n> wrote in message
РДс> news:47e45502$0$15176$607ed4bc@cv.net...


Hello, Cyril Novikov!
You wrote on Fri, 21 Mar 2008 14:43:19 -0700:






Mikhail Kimmelman wrote:

На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?








А какой размер у каждого числа? Если каждое число имеет не более

10^9
возможных

значений, можно просто за один проход построить гистограмму, потом

середина в

гистограмме тоже находится за один проход.






Там наверняка огроменные комплексные числа. Интереснее
другое - кто и зачем записал их на ленту? И хорошо ли это
для евреев?



РДс> Комплексные числа не сравниваются, у них нет понятия больше или
меньше, это
РДс> надо знать.


Так ведь это делает задачку только интресенее, не так ли?
Я уж не говорю о том, что вопрос кто и зачем их записал на
ленту все равно остается.


Ну скажем так, археологи обнаружили некую ленту под развалинами одно из
храмов в Иршалаиме. Лента очень хрупкая и светочувствительная, после чтения
первого значка он рассыпается в секунды. Закончив с этой загадкой можно
только ответить кто создал эту ленту, пришельцы или древние египтяне, и
зачем и что нам с этого, ну просто интересно.


Re: Задачка

"Рынский, Дениска (старшой)" <javaarchitect@msn.com> wrote:




Ну скажем так, археологи обнаружили некую ленту под развалинами одно из
храмов в Иршалаиме. Лента очень хрупкая и светочувствительная, после
чтения первого значка он рассыпается в секунды.


И у них не хватило денег на пару терабайт дисковой памяти?

Иван

Re: Задачка

"Isaac Blank" <izblank_removethis_@yahoo.com> wrote in message
news:%RUEj.20608$Ch6.8167@newssvr11.news.prodigy.net...


За один проход найдем, в какой тысяче эта медиана сидит, а во втором
проходе уточним


А как ?

Миша

Re: Задачка

"Cyril Novikov" <cnovikov@mail.remove.this.ru> wrote in message
news:q3WEj.3982$qT6.2294@nlpi070.nbdc.sbc.com...



На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?


А какой размер у каждого числа? Если каждое число
имеет не более 10^9 возможных значений,


Не думаю. Какое-то это число 10^9 не круглое.
Скорее всего обычные 32-bit числа


можно просто за один проход построить гистограмму,
потом середина в гистограмме тоже находится за один проход.


Миша

Re: Задачка

Mikhail Kimmelman wrote:

"Cyril Novikov" <cnovikov@mail.remove.this.ru> wrote in message
news:q3WEj.3982$qT6.2294@nlpi070.nbdc.sbc.com...



На ленте записано 10^12 чисел. Писать на ленту нельзя.
Как найти их медиану, имея память только на 10^9 чисел ?


А какой размер у каждого числа? Если каждое число
имеет не более 10^9 возможных значений,


Не думаю. Какое-то это число 10^9 не круглое.
Скорее всего обычные 32-bit числа


Если известны верхняя и нижняя границы чисел (как для 32-битных), тогда
все равно решается гистограммами. В общем случае, сначала делим диапазон
на 10^9 интервалов (можно неравных), строим по ним гистограмму, находим
интервал с медианой внутри (надеюсь, это понятно как), делим его на 10^9
отрезков, и так далее, пока не доберемся до конкретных чисел. На каждой
итерации надо аккуратно запоминать сколько чисел уже ушло слева от
нового интервала. Для 32-битных целых чисел будет всего две итерации,
потому что после первой итерации в интервале будет всего четыре или пять
чисел (2^32 / 10^9).

Небольшая проблема в том, что в гистограмме числа тоже 32-битные, и их
может зашкалить, например если на ленте больше 2^32 какого-нибудь одного
числа. Не беда - организуем 10^9 32-битных чисел как 5*10^8 64-битных.

Если на то пошло, то для этого алгоритма вообще хватает двух(!) чисел
(счетчиков) в памяти (не считая внутренние переменные алгоритма) -
главное, чтобы на каждой итерации интервалы уменьшались.



можно просто за один проход построить гистограмму,
потом середина в гистограмме тоже находится за один проход.


Re: Задачка

"Cyril Novikov" <cnovikov@mail.remove.this.ru> wrote in message
news:d%2Fj.4018$qT6.1377@nlpi070.nbdc.sbc.com...


Если известны верхняя и нижняя границы чисел (как для 32-битных), тогда
все равно решается гистограммами. В общем случае, сначала делим диапазон
на 10^9 интервалов (можно неравных), строим по ним гистограмму, находим
интервал с медианой внутри (надеюсь, это понятно как), делим его на 10^9
отрезков, и так далее, пока не доберемся до конкретных чисел.


Спасибо. Надо подумать.


На каждой итерации надо аккуратно запоминать сколько чисел уже ушло слева
от нового интервала. Для 32-битных целых чисел будет всего две итерации,
потому что после первой итерации в интервале будет всего четыре или пять
чисел (2^32 / 10^9).

Небольшая проблема в том, что в гистограмме числа тоже 32-битные, и их
может зашкалить, например если на ленте больше 2^32 какого-нибудь одного
числа. Не беда - организуем 10^9 32-битных чисел как 5*10^8 64-битных.

Если на то пошло, то для этого алгоритма вообще хватает двух(!) чисел
(счетчиков) в памяти (не считая внутренние переменные алгоритма) -
главное, чтобы на каждой итерации интервалы уменьшались.


Миша

Re: Задачка

On Sat, 22 Mar 2008 12:10:53 +0200, Mikhail Kimmelman wrote:


"Cyril Novikov" <cnovikov@mail.remove.this.ru> wrote in message
news:d%2Fj.4018$qT6.1377@nlpi070.nbdc.sbc.com...


Если известны верхняя и нижняя границы чисел (как для 32-битных), тогда
все равно решается гистограммами.



А если не известны - они находятся за лишний прогон.

Юра

Re: Задачка

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



Если известны верхняя и нижняя границы чисел (как для 32-битных), тогда
все равно решается гистограммами. В общем случае, сначала делим диапазон
на 10^9 интервалов (можно неравных), строим по ним гистограмму, находим
интервал с медианой внутри (надеюсь, это понятно как), делим его на 10^9
отрезков, и так далее, пока не доберемся до конкретных чисел.


Спасибо. Надо подумать.


Ну да. Вроде все действительно просто.
Если не вдаваться в детали и подробности (типа того же переполнения и др.)

Миша