Вчера научился искать минимальный элемент массива
Попутно придумал забавную задачку, которую решил не сразу.
Хотя формулировочка проста до неприличия.

//Ищем минимальный элемент в случайном массиве
for(int i=0,m=MAX_INT;i<N;i++)
  if(a[i]<m)
    m=a[i];//Cколько раз (в среднем) выполнится это строчка?

PS
Всегда найдутся товарищи, достаточно дотошные,
чтобы желать точной постановки,
и в то же время достаточно ленивые,
чтобы напрячься и сделать её самому.
Для таких объясняю, что значит "в среднем".

- Заполните массив случайным образом. 
(Генератор даже не обязательно равномерный. 
Достаточно, чтобы он был "хорошим", 
т.е. давал слабую корелляцию между соседями.
И ещё он должен быть сильно "шире" чем N, 
чтобы в массиве было поменьше одинаковых чисел)

- Подсчитайте число присваиваний при нахождении минимального элемента. 
Это число будет зависеть как от числа элементов, 
так и от самой случайной реализации массива.

- Проделайте всё это много-много раз и возьмите среднее от всех ответов. 
Результат будет функцией только от длины массива F(N). 
Вид этой функции я и прошу найти "ручками".

Здравствуйте, Pushkin, Вы писали:

...

P>

P>//Ищем минимальный элемент в случайном массиве
P>for(int i=0,m=MAX_INT;i<N;i++)
P>  if(a[i]<m)
P>    m=a[i];//Cколько раз (в среднем) выполнится это строчка?
P>

P>PS
P>Всегда найдутся товарищи, достаточно дотошные,
P>чтобы желать точной постановки,
P>и в то же время достаточно ленивые,
P>чтобы напрячься и сделать её самому.

и даже достаточно ленивые, чтобы её решать.

Поэтому, в отместку, другая задачка: как при поиске
минимального элемента не делать присваиваний

  m=a[i];

вообще ?

Здравствуйте, mrhru, Вы писали:

M> и даже достаточно ленивые, чтобы её решать.

ай-ай-ай

M>Поэтому, в отместку, другая задачка: как при поиске
M>минимального элемента не делать присваиваний
M>

M>  m=a[i];
M>

M>вообще ?

for(int i=0;i<N-1;i++)
  if(a[i]<a[i+1])
    a[i+1]^=a[i]^=a[i+1]^=a[i];
return a[N-1];

Здравствуйте, Pushkin, Вы писали:

P>

P>//Ищем минимальный элемент в случайном массиве
P>for(int i=0,m=MAX_INT;i<N;i++)
P>  if(a[i]<m)
P>    m=a[i];//Cколько раз (в среднем) выполнится это строчка?
P>

P>Вид этой функции я и прошу найти "ручками".
P>[/ccode]

Найдем вероятность того, что последний элемент массива будет минимальным.
Предыдущие числа разбивают диапозон целых чисел на N отрезков. Вероятность того, что последний будет минимальным равна вероятности попадания последнего числа в первый отрезок. При достаточно равномерном распределении она равна 1/N.
Далее, по индукции, получаем гармонический ряд:
F(N) = 1 + 1/2 + 1/3 + ... + 1/N ~ C + ln(N) + 1/2N, где C = 0.5772... — постоянная Эйлера-Маскерони

Здравствуйте, Pushkin, Вы писали:
...
M>> и даже достаточно ленивые, чтобы её решать.

P>ай-ай-ай



...
P>

P>for(int i=0;i<N-1;i++)
P>  if(a[i]<a[i+1])
P>    a[i+1]^=a[i]^=a[i+1]^=a[i];
P>return a[N-1];
P>

:super:/2.

А вот без жульничества.

int a[N];

int C(int p)
{
  if( p == (N - 1) ){
    return a[p];
  }else{
    return min( a[p], C(p+1) );
  }
}
...
  m = C(0);

Здравствуйте, Pushkin, Вы писали:

P>

P>for(int i=0;i<N-1;i++)
P>  if(a[i]<a[i+1])
P>    a[i+1]^=a[i]^=a[i+1]^=a[i];
P>return a[N-1];
P>

Будьте проще, и к вам undefined behaviour не потянется.

int iGreatest = 0, iCurrent;
for(iCurrent = 1; iCurrent < N; ++i)
  if(a[iGreatest] < a[iCurrent])
    iGreatest = iCurrent;

ибо присваивание целых чисел легче (не тяжелее), чем измывательства над данными любого другого типа.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Pushkin, Вы писали:

P>>

P>>for(int i=0;i<N-1;i++)
P>>  if(a[i]<a[i+1])
P>>    a[i+1]^=a[i]^=a[i+1]^=a[i];
P>>return a[N-1];
P>>

К>Будьте проще, и к вам undefined behaviour не потянется.
К>

К>int iGreatest = 0, iCurrent;
К>for(iCurrent = 1; iCurrent < N; ++i)
К>  if(a[iGreatest] < a[iCurrent])
К>    iGreatest = iCurrent;
К>

К>ибо присваивание целых чисел легче (не тяжелее), чем измывательства над данными любого другого типа.



Спасибо! Вот я ещё на один бит поумнел.

Здравствуйте, Кодт, Вы писали:

К>Будьте проще, и к вам undefined behaviour не потянется.

Вот уж точно по Паркинсону.
Самое большое сопротивление обычно вызывает самое безобидное место.
Вы задачу, блин решайте, умные!

PS
Хотя ты, конечно, как всегда прав

Здравствуйте, MichaelP, Вы писали:

MP>Найдем вероятность того, что последний элемент массива будет минимальным.
MP>Предыдущие числа разбивают диапозон целых чисел на N отрезков. Вероятность того, что последний будет минимальным равна вероятности попадания последнего числа в первый отрезок. При достаточно равномерном распределении она равна 1/N.
MP>Далее, по индукции, получаем гармонический ряд:
MP>F(N) = 1 + 1/2 + 1/3 + ... + 1/N ~ C + ln(N) + 1/2N, где C = 0.5772... — постоянная Эйлера-Маскерони

У меня такой же ответ.
Но получил я его чуть иначе, и мне не потребовалась равномерность генератора.

Здравствуйте, Pushkin, Вы писали:

P>Попутно придумал забавную задачку, которую решил не сразу.
P>Хотя формулировочка проста до неприличия.

P>

P>//Ищем минимальный элемент в случайном массиве
P>for(int i=0,m=MAX_INT;i<N;i++)
P>  if(a[i]<m)
P>    m=a[i];//Cколько раз (в среднем) выполнится это строчка?
P>

Задачка вообще-то для математиков, немного знакомых с тервером.
f(N)=2-1/(2^(N-1))
раписывать ломает, но если кому интересно могу

Здравствуйте, Demon, Вы писали:

D>Задачка вообще-то для математиков, немного знакомых с тервером.
D>f(N)=2-1/(2^(N-1))
D>раписывать ломает, но если кому интересно могу

Ты хочешь сказать, что в длиннющем массиве
присваивание выполнится не более 2-х раз?
Имхо оптимист

Здравствуйте, MichaelP, Вы писали:

[skip]

MP>Найдем вероятность того, что последний элемент массива будет минимальным.
MP>Предыдущие числа разбивают диапозон целых чисел на N отрезков. Вероятность того, что последний будет минимальным равна вероятности попадания последнего числа в первый отрезок. При достаточно равномерном распределении она равна 1/N.

Это и так понятно. Поскольку числа случайные и не коррелируют между собой, то вероятность
того что некоторый, даже не обязательно последний, элемент массива минимальный, равна
1/N.

MP>Далее, по индукции, получаем гармонический ряд:

А вот это мне не понятно. Какие величины складываются?
Нельзя ли по-подробнее?

MP>F(N) = 1 + 1/2 + 1/3 + ... + 1/N ~ C + ln(N) + 1/2N, где C = 0.5772... — постоянная Эйлера-Маскерони

Здравствуйте, Demon, Вы писали:

D>Здравствуйте, Pushkin, Вы писали:

P>>Попутно придумал забавную задачку, которую решил не сразу.
P>>Хотя формулировочка проста до неприличия.

P>>

P>>//Ищем минимальный элемент в случайном массиве
P>>for(int i=0,m=MAX_INT;i<N;i++)
P>>  if(a[i]<m)
P>>    m=a[i];//Cколько раз (в среднем) выполнится это строчка?
P>>

D>Задачка вообще-то для математиков, немного знакомых с тервером.
D>f(N)=2-1/(2^(N-1))
D>раписывать ломает, но если кому интересно могу
Распишу т.к. найден другой ответ
Пусть 0<=a[i]<=1
m[i] — min на i-ом шаге
вероятность того что b[i+1]<m[i] равна m[i], а M(m[i+1])=m[i]/2 т.е. можно считать что m[i+1]=m[i]/2
суммируем и получаем выше указанный результат

Здравствуйте, Pushkin, Вы писали:

D>>f(N)=2-1/(2^(N-1))

P>Ты хочешь сказать, что в длиннющем массиве
P>присваивание выполнится не более 2-х раз?
Меня это тоже удивляет, но дырку в своей логике я не могу найти

Здравствуйте, Demon, Вы писали:

D>Распишу т.к. найден другой ответ
D>Пусть 0<=a[i]<=1
D>m[i] — min на i-ом шаге
D>вероятность того что b[i+1]<m[i] равна m[i],

до этого места верно

D>а M(m[i+1])=m[i]/2 т.е. можно считать что m[i+1]=m[i]/2

Если M(m[i+1]) это мат. ожидание минимума на следующем шаге, то оно равно

M(m[i+1]) = m[i] * m[i]/2 + (1-m[i]) * m[i] = m[i] — m[i]^2/2

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

Здравствуйте, Pushkin, Вы писали:

MP>>Найдем вероятность того, что последний элемент массива будет минимальным.
MP>>Предыдущие числа разбивают диапозон целых чисел на N отрезков. Вероятность того, что последний будет минимальным равна вероятности попадания последнего числа в первый отрезок. При достаточно равномерном распределении она равна 1/N.
MP>>Далее, по индукции, получаем гармонический ряд:
MP>>F(N) = 1 + 1/2 + 1/3 + ... + 1/N ~ C + ln(N) + 1/2N, где C = 0.5772... — постоянная Эйлера-Маскерони

P> У меня такой же ответ.
P>Но получил я его чуть иначе, и мне не потребовалась равномерность генератора.

Согласен. Усилим утверждение:
Если числа распределены одинаково и независимо, то вероятности того, что i-ое из N чисел минимально, равны. Следовательно, вероятность того, что последнее минимально равно 1/N. Далее по тексту.

Здравствуйте, Sergeem, Вы писали:

S>А вот это мне не понятно. Какие величины складываются?
S>Нельзя ли по-подробнее?

Теперь уже я переведу MichelP для широкой публики.

Найдём рекуррентную формулу для F(N).
Т.е. пусть мы знаем F(N-1) и хотим получить F(N).

Если в случайной реализации массива a[N]
минимальный элемент не на последнем месте,
то можно считать, что это массив из N-1 элемента,
так как последний элемент точно не добавит приравнивания.

Если числа распределены одинаково и независимо,
то вероятности того, что i-ое из N чисел минимально
не зависит от i и равна 1/N. В том числе и для i=N-1.

Т.е. только в 1/N реализациях от общего числа больший массив
что-то добавляет к искомому числу по сравнению с меньшим.

Поэтому F(N) = F(N-1) + 1/N = 1 + 1/2 + .... + 1/N

Моё решение было несколько другим.

Пусть у нас всего 2 элемента.
Тогда минимальный из них точно влезет в ячейку.
А вот другой влезет только если будет стоять раньше минимального.
Вероятность стоять раньше из двух 1/2.
Поэтому среднее число присваиваний 1+1/2 = 3/2

Теперь 3 элемента.
Минимальный так и так влезет — уже имеем F=1+
Второй по величине влезет если окажется раньше минимального F=1+1/2+
Третий влезет, если окажется первым из трёх (себя и двух минимальных) F=1+1/2+1/3

Ясно, что и дальше ничего не мешает продолжать в том же духе.

Здравствуйте, Pushkin, Вы писали:


P>Если числа распределены одинаково и независимо,
P>то вероятности того, что i-ое из N чисел минимально
P>не зависит от i и равна 1/N. В том числе и для i=N-1.

Ради справедливости замечу, что это рассуждение, как я только что заметил, раньше меня привел Sergeem

Автор: Sergeem
Дата: 05.03.03

.

Здравствуйте, Pushkin, Вы писали:

P>Моё решение было несколько другим.

Господи, да совсем же всё просто, только сейчас в голову пришло

Первый элемент кладётся в ячейку с вероятностью 1.
Второй элемент с вероятнстью 1/2 — если он окажется меньше первого.
Третий элемент с вероятностью 1/3 — если он меньше первого и второго.
n-ый элемент кладётся с вероятностью 1/n — если он наименьший из первых n
(а любой из них имет равные права быть наименьшим)

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Pushkin, Вы писали:

P>>Моё решение было несколько другим.

P>Господи, да совсем же всё просто, только сейчас в голову пришло

P>Первый элемент кладётся в ячейку с вероятностью 1.
P>Второй элемент с вероятнстью 1/2 — если он окажется меньше первого.
P>Третий элемент с вероятностью 1/3 — если он меньше первого и второго.
P>n-ый элемент кладётся с вероятностью 1/n — если он наименьший из первых n
P>(а любой из них имет равные права быть наименьшим)

Собственно это я имел ввиду в своем доказательстве.