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

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

#Логирование в GUI. (32325 hits)
#Разбор строки. (273342 hits)
#Рисование тора. (34736 hits)
#Рисование полусферы. (29029 hits)
#Простой генератор случайных чисел. (133989 hits)
#Косинус. (39847 hits)
#Динамическая очистка выпадающего списка (select) на javascript. (90870 hits)
#Как работать с zip архивами стандартными средствами windows. (42157 hits)
#Наибольший общий делитель. (192521 hits)
#Вычисление значения полинома. (62106 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (147303 hits)
#"The Java Programming Language" Ken Arnold, James Gosling, David Holmes листинги, код, примеры из книги, исходники. (61067 hits)
#Вычисление эксцесса и коэффициентов асимметрии заданной выборки. (45812 hits)
#Двусторонняя карта. (34052 hits)
#Последовательный поиск и его оптимизации. (44737 hits)
#ООП на javascript: классы, наследование, инкапсуляция. (257613 hits)
#Рисование 3D объекта. (35139 hits)
#Случайный выбор элемента при неизвестном их количестве. (36696 hits)
#Найти максимальную сумму в последовательности. (137255 hits)
#Числа Армстронга. (46118 hits)


Главная >> Каталог задач >> Числа >> Случайные числа >> Случайный выбор элемента при неизвестном их количестве

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

Aвтор:
Дата:
Просмотров: 36695
реализации(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]