Вчера научился искать минимальный элемент массива
Попутно придумал забавную задачку, которую решил не сразу.
Хотя формулировочка проста до неприличия.
//Ищем минимальный элемент в случайном массиве
for(int i=0,m=MAX_INT;i<N;i++)
if(a[i]<m)
m=a[i];//Cколько раз (в среднем) выполнится это строчка?
PS
Всегда найдутся товарищи, достаточно дотошные,
чтобы желать точной постановки,
и в то же время достаточно ленивые,
чтобы напрячься и сделать её самому.
Для таких объясняю, что значит "в среднем".
- Заполните массив случайным образом.
(Генератор даже не обязательно равномерный.
Достаточно, чтобы он был "хорошим",
т.е. давал слабую корелляцию между соседями.
И ещё он должен быть сильно "шире" чем N,
чтобы в массиве было поменьше одинаковых чисел)
- Подсчитайте число присваиваний при нахождении минимального элемента.
Это число будет зависеть как от числа элементов,
так и от самой случайной реализации массива.
- Проделайте всё это много-много раз и возьмите среднее от всех ответов.
Результат будет функцией только от длины массива F(N).
Вид этой функции я и прошу найти "ручками".