Escribí este código de Python y me pregunté si a veces simplemente no termina (suponiendo que tengamos memoria / tiempo infinito y ningún límite de profundidad de recursión).
Intuitivamente pensarías que termina, ya que en algún momento debes tener suerte , y si no termina tienes una cantidad infinita de tiempo para tener suerte. Por otro lado, a medida que aumenta la profundidad de recursión, debes ser exponencialmente más afortunado.
import random
def random_tree():
if random.random() < 0.5:
return 0
return [random_tree() for _ in range(random.randint(1, 5))]
Si random_tree
no siempre termina, ¿por qué y cuál es la probabilidad de que termine?
He intentado calcularlo usando , que en su inutilidad terrible da la respuesta ~ 0.684124 o ... 1 .
Probablemente más complicado, pero también intrigante para mí, ¿cuál es la posibilidad de terminación para:
def random_tree(a, b):
if random.random() < a:
return 0
return [random_tree(a, b) for _ in range(random.randint(1, b))]
O en seudocódigo:
random_tree(a, b) is a function that either:
- returns 0 with probability a
- returns a list containing the results of 1 to b
(uniformly chosen from this inclusive range) recursive calls
random_tree(a, b):
if rand() < a # rand() is a random real on [0, 1)
return 0
list = []
len = randint(1, b) # uniform random integer from 1 to b inclusive
do len times
append random_tree(a, b) to list
return list
random_tree(0.5, 5)
.Respuestas:
fuente