Блог пользователя vitux

Очень интересная и увлекательная задача
Автор vitux, 12 лет назад, По-русски

Есть вот такая вот функция. 

def test(k):
	i = 0
	j = randint(0, k - 1) # randint(0, k - 1) - случайное целое число из [0, k - 1]
	while i < j:
		i += 1
		j = randint(0, k - 1)
	return i

Какое математическое ожидание величины test(k)? Требуется посчитать быстрее, чем за O(k).

  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Ответ порядка sqrt(k), так что можно посчитать за O(ответа). Просто считаем по очереди p_i = вероятность того, что будет возвращено число i. Эта величина легко пересчитывается (p_(i+1) = (1 — p_i) * (i + 1) / k, если считать p_0 = 0 и что числа генерируются от 1 до k, а не от 0 до k-1).

→ Ответить