Поиск минимума

и задачки для интервью.
Forum rules
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Поиск минимума

Post by venco »

Есть последовательность из N разных чисел в случайном порядке.
Мы ищем самое маленькое число - сравниваем очередное число из последовательности с текущим минимумом, если меньше - присваиваем его текущему минимуму.
Сколько в среднем будет присваиваний?
Top
blak_box
Уже с Приветом
Posts: 497
Joined: 07 Jun 2002 18:41

Re: Поиск минимума

Post by blak_box »

N/2. При условии, что исходный минимум устанавливаетса в INT_MAX, а в наборе чисел INT_MAXа нет.
Top
User avatar
Ion Tichy
Уже с Приветом
Posts: 13339
Joined: 07 Dec 2004 04:00
Location: Москва->CO

Re: Поиск минимума

Post by Ion Tichy »

blak_box wrote:N/2. При условии, что исходный минимум устанавливаетса в INT_MAX, а в наборе чисел INT_MAXа нет.
Зависит также от вероятностных характеристик последовательности. N/2 - равномерное распределение, или нормальное, или (?)...
Как же это вы без гравицаппы пепелац выкатываете из гаража? Это непорядок...
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: Поиск минимума

Post by venco »

blak_box wrote:N/2. При условии, что исходный минимум устанавливаетса в INT_MAX, а в наборе чисел INT_MAXа нет.

Неправильно.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: Поиск минимума

Post by venco »

Ion Tichy wrote:
blak_box wrote:N/2. При условии, что исходный минимум устанавливаетса в INT_MAX, а в наборе чисел INT_MAXа нет.
Зависит также от вероятностных характеристик последовательности. N/2 - равномерное распределение, или нормальное, или (?)...

Порядок совершенно случаен, а поскольку повторов нет, то от вероятностных характеристик самих чисел ответ не зависит.
Top
blak_box
Уже с Приветом
Posts: 497
Joined: 07 Jun 2002 18:41

Re: Поиск минимума

Post by blak_box »

(N+1)/2
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: Поиск минимума

Post by venco »

blak_box wrote:(N+1)/2

Хватит гадать, это далеко от правильного ответа. :)
Top
Noskov Sergey
Уже с Приветом
Posts: 5430
Joined: 05 Sep 2002 18:45
Location: CAB

Post by Noskov Sergey »

N*N/2?
Top
User avatar
dima_ca
Уже с Приветом
Posts: 2226
Joined: 16 Jan 2004 22:05
Location: East Bay, CA

Post by dima_ca »

Noskov Sergey wrote:N*N/2?

8O

Тогда уже почему бы не (N!)^2 :mrgreen:
Безапелляционность - признак глупости.
Top
Tigrius
Уже с Приветом
Posts: 266
Joined: 23 Oct 2004 22:07

Post by Tigrius »


1 + 1/2 + ... + 1/n ~ ln n + \gamma.

Hint: consider the i-th smallest number, find the probability that we assign it to the "current minimum", finally use the linearity of expectation.

I'll post the complete solution later, if nobody else finds it.
Top
Noskov Sergey
Уже с Приветом
Posts: 5430
Joined: 05 Sep 2002 18:45
Location: CAB

Post by Noskov Sergey »

Tigrius,

Мне цитата чего-то не видна.

dima_ca

я просто перебрал в лоб двумя циклами. С присвоением минималного значения.
Top
Tigrius
Уже с Приветом
Posts: 266
Joined: 23 Oct 2004 22:07

Post by Tigrius »

Noskov Sergey wrote:Tigrius,
Мне цитата чего-то не видна.


Выделите ее мышкой.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

[quote="Tigrius"][/quote]
Правильно. :great:
Причём уже после того как я запостил задачу я обнаружил, что есть очень простое решение.
Top
Noskov Sergey
Уже с Приветом
Posts: 5430
Joined: 05 Sep 2002 18:45
Location: CAB

Post by Noskov Sergey »

Классно. Спасибо.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Итак, простое решение. Если бы я его сразу нашёл - то не запостил бы задачу. :)

i-ое число будет присвоено, если оно меньше всех предыдущих, т.е. с вероятносью 1/i.
Top
Sam Adams
Уже с Приветом
Posts: 1316
Joined: 03 Jul 2003 06:02
Location: USA

Post by Sam Adams »

venco wrote:Итак, простое решение. Если бы я его сразу нашёл - то не запостил бы задачу. :)

i-ое число будет присвоено, если оно меньше всех предыдущих, т.е. с вероятносью 1/i.


Еще одна очень похожая красивая задача - выбрать случайное число из _потока_ данных.
Top

Return to “Головоломки”