Nos dan una array ordenada A[] de n elementos. Necesitamos encontrar si x está presente en A o no. En la búsqueda binaria siempre usamos el elemento medio, aquí elegiremos al azar un elemento en el rango dado. En la búsqueda binaria teníamos middle = (start + end)/2 En la búsqueda binaria aleatoria hacemos lo … Continue reading «Algoritmo de búsqueda binaria aleatoria»
Dada una función foo() que devuelve números enteros del 1 al 5 con la misma probabilidad, escriba una función que devuelva números enteros del 1 al 7 con la misma probabilidad usando solo foo(). Minimice el número de llamadas al método foo(). Además, no se permite el uso de ninguna otra función de biblioteca y … Continue reading «Genera enteros del 1 al 7 con igual probabilidad»
Dadas tres arrays A, B y C, encuentre si C es un producto de A y B. Ejemplos: Input : A = 1 1 1 1 B = 1 1 1 1 C = 2 2 2 2 Output : Yes C = A x B Input : A = 1 1 1 1 1 … Continue reading «Algoritmo de Freivald para comprobar si una array es producto de dos»
Dada una lista enlazada individualmente, seleccione un Node aleatorio de la lista enlazada (la probabilidad de elegir un Node debe ser 1/N si hay N Nodes en la lista). Se le da un generador de números aleatorios. A continuación se muestra una solución simple: Cuente el número de Nodes recorriendo la lista. Recorra la lista … Continue reading «Programa C para seleccionar un Node aleatorio de una lista enlazada individualmente»
¿Cuántas personas deben estar en una habitación para que la probabilidad sea del 100% de que al menos dos personas en la habitación tengan el mismo cumpleaños? Respuesta: 367 (ya que hay 366 cumpleaños posibles, incluido el 29 de febrero). La pregunta anterior era simple. Pruebe la siguiente pregunta usted mismo. ¿Cuántas personas deben estar en … Continue reading «Paradoja de cumpleaños»
Se le da una función foo() que representa una moneda sesgada. Cuando se llama a foo(), devuelve 0 con un 60 % de probabilidad y 1 con un 40 % de probabilidad. Escribe una nueva función que devuelva 0 y 1 con un 50% de probabilidad cada uno. Su función debe usar solo foo(), ningún … Continue reading «Hacer una moneda justa a partir de una moneda sesgada»
Prerrequisito: Variable aleatoria Esta publicación trata sobre conceptos matemáticos como expectativa , linealidad de expectativa . Cubre uno de los temas necesarios para comprender los algoritmos aleatorios . Consideremos el siguiente problema simple. Problema: dado un dado justo con 6 caras, el dado se lanza n veces, encuentre el valor esperado de la suma de … Continue reading «Linealidad de la expectativa»
Dada una lista enlazada individualmente, seleccione un Node aleatorio de la lista enlazada (la probabilidad de elegir un Node debe ser 1/N si hay N Nodes en la lista). Se le da un generador de números aleatorios. A continuación se muestra una solución simple: Cuente el número de Nodes recorriendo la lista. Recorra la lista … Continue reading «Programa C++ para seleccionar un Node aleatorio de una lista enlazada individualmente»
Tienes una función rand(a, b) que genera números aleatorios equiprobables entre [a, b] inclusive. Genere 3 números x, y, z con probabilidad P(x), P(y), P(z) tales que P(x) + P(y) + P(z) = 1 usando el rand(a,b) dado ) función. La idea es utilizar la característica equiprobable del rand(a,b) provisto. Sean las probabilidades dadas en … Continue reading «Escribe una función que genere uno de 3 números según las probabilidades dadas»
Dada una array de enteros, encuentre el elemento que aparece más en la array y devuelva cualquiera de sus índices aleatoriamente con la misma probabilidad. Ejemplos: Input: arr[] = [-1, 4, 9, 7, 7, 2, 7, 3, 0, 9, 6, 5, 7, 8, 9] Output: Element with maximum frequency present at index 6 OR Element … Continue reading «Encuentre un índice del elemento máximo que ocurre con la misma probabilidad»