Детский вопрос для крутых программеров
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 06:50
Оценка:
Вчера научился искать минимальный элемент массива
Попутно придумал забавную задачку, которую решил не сразу.
Хотя формулировочка проста до неприличия.

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


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

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

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

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