El muestreo de reservorio es una familia de algoritmos aleatorios para elegir aleatoriamente k muestras de una lista de n elementos, donde n es un número muy grande o desconocido. Por lo general, n es lo suficientemente grande como para que la lista no quepa en la memoria principal. Por ejemplo, una lista de consultas … Continue reading «Muestreo de yacimientos»
Dada una array, escriba un programa para generar una permutación aleatoria de los elementos de la array. Esta pregunta también se hace como «mezclar una baraja de cartas» o «aleatorizar una array dada». Aquí shuffle significa que cada permutación del elemento de array debería ser igualmente probable. Deje que la array dada sea arr[] . … Continue reading «Mezclar una array dada usando el algoritmo de mezcla de Fisher-Yates – Part 1»
Recomendamos encarecidamente consultar los siguientes artículos como requisito previo para ello. Algoritmos aleatorios | Conjunto 1 (Introducción y Análisis) Algoritmos Aleatorizados | Conjunto 2 (Clasificación y Aplicaciones) En esta publicación, se analiza un algoritmo de Monte Carlo. Declaración del problema: Dada una array no ordenada A[] de n números y ε > 0, calcule un … Continue reading «Algoritmos aleatorios | Conjunto 3 (1/2 mediana aproximada)»
Dados cuatro enteros N, R, X e Y tales que representa un círculo de radio R con [X, Y] como coordenadas del centro. La tarea es encontrar N puntos aleatorios dentro o sobre el círculo. Ejemplos: Entrada: R = 12, X = 3, Y = 3, N = 5 Salida: (7,05, -3,36) (5,21, -7,49) (7,53, 0,19) … Continue reading «Encuentra N puntos aleatorios dentro de un círculo»
Dada una baraja de cartas, la tarea es barajarlas. Preguntado en la entrevista de Amazon Requisito previo: barajar una array dada Algoritmo: 1. First, fill the array with the values in order. 2. Go through the array and exchange each element with the randomly chosen element in the range from itself to the end. // … Continue reading «barajar una baraja de cartas»
Dado un entero positivo N , la tarea es generar una string binaria aleatoria de longitud N . Ejemplos: Entrada: N = 7 Salida: 1000001 Entrada: N = 5 Salida: 01001 Enfoque: el problema dado se puede resolver usando la función rand() que genera un número aleatorio en el rango [0, RAND_MAX ] y con … Continue reading «Genere una string binaria aleatoria de longitud N»
Un CAPTCHA (Prueba de Turing Pública Completamente Automatizada para diferenciar a las Computadoras de los Humanos) es una prueba para determinar si el usuario es humano o no. Por lo tanto, la tarea es generar un CAPTCHA único cada vez y saber si el usuario es humano o no pidiéndole al usuario que ingrese el … Continue reading «Programa para generar CAPTCHA y verificar usuario»
Dados dos números enteros N y M , la tarea es generar cualquier laberinto de tamaño N * M que contenga solo 0 (que representa una pared) y 1 (que representa un espacio vacío donde uno puede moverse) con el punto de entrada como P0 y el punto de salida P1 y allí es sólo … Continue reading «Generador de laberinto acíclico aleatorio con punto de entrada y salida dado»
Estimación de Monte Carlo Los métodos de Monte Carlo son una amplia clase de algoritmos computacionales que se basan en muestreos aleatorios repetidos para obtener resultados numéricos. Uno de los ejemplos básicos para comenzar con el algoritmo de Monte Carlo es la estimación de Pi . Estimación de Pi La idea es simular puntos aleatorios (x, … Continue reading «Estimación del valor de Pi usando Monte Carlo»
Dada una función rand50() que devuelve 0 o 1 con la misma probabilidad, escriba una función que devuelva 1 con un 75 % de probabilidad y 0 con un 25 % de probabilidad usando solo rand50(). Minimice el número de llamadas al método rand50(). Además, no se permite el uso de ninguna otra función de … Continue reading «Genera 0 y 1 con 25% y 75% de probabilidad»