CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Найти максимальную сумму в последовательности. (137940 hits)
#Часики на js. (93802 hits)
#Древовидные структуры. (57651 hits)
#Масштабирование, пропорциональное изменение размеров картинки. (101400 hits)
#Валидация, динамическая проверка заполнения html форм. (209558 hits)
#Рисование линии. (39012 hits)
#ООП на javascript: классы, наследование, инкапсуляция. (257905 hits)
#Рисование прямоугольника. (31517 hits)
#Подсветка синтаксиса. (31663 hits)
#Добавление истории операций(undo&redo) в компонент. (40201 hits)
#Создание простейшей таблицы. (37353 hits)
#Сортировка вставкой. (112562 hits)
#Отслеживание изменений файла. (38122 hits)
#Сравнение алгоритмов сортировки массива. (182721 hits)
#Рисование тора. (34983 hits)
#Арктангенс. (45756 hits)
#Вычисление эксцесса и коэффициентов асимметрии заданной выборки. (46088 hits)
#Перестановка фрагментов строки(или одномерного массива). (61007 hits)
#Вычисление двойного интеграла с использованием MPI. (60528 hits)
#Работа с камерой. (36047 hits)
показать все >>


Главная >> Каталог задач >> Числа >> Случайные числа >>

Случайный выбор элемента при неизвестном их количестве

Aвтор:
Дата:
Просмотров: 36892
реализации(php: 1шт...) +добавить

Как можно выбрать один из n объектов случайным образом, если объекты предъявляются последовательно, но их количество n заранее неизвестно?

Задача достаточно актуальна в программировании при работе с файловой системой: как наиболее быстро выбрать случайный файл в директории?

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

Для таких случаев существует быстрый и красивый алгоритм:

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

Таким образом, получим:
 псевдокод: случайный выбор при неизвестном количестве  ссылка
  1. i = 0
  2. while (<пока есть непройденные элементы>)
  3.   /* randint - случайное число "от" и "до" */
  4.   if randint(1, ++i) == 1
  5.     choice = i
  6.  
  7. /* после выполнения имеем в choice - 
  8.    искомый случайный выбор */

Реализации:

php(1)   +добавить

1) Чтение случайного файла в директории на php, code #83[автор:this]