Paradoja de Monty Hall – Simulación en C++

Descripción del problema de Monty Hall: El concursante debe elegir una puerta entre tres (todas cerradas); el premio consiste en llevarse lo que se encuentra detrás de la elegida. Se sabe con certeza que tras una de ellas se oculta un automóvil, y tras las otras dos hay cabras. Una vez que el concursante haya elegido una […]

Algoritmo Extendido de Euclides

El algoritmo de Euclides para el cálculo del MCD se vio en este post, este post trata del proceso extendido de dicho algoritmo, como veremos se le dice extendido ya que el proceso del algoritmo es prácticamente mismo con la diferencia que ahora en cada iteración tomamos cierta información que nos es útil para calcular […]

Algoritmo de Euclides

Tiempo: O(log n)Espacio: O(1) Es un algoritmo para el cálculo en tiempo logarítmico del MCD de dos números. Se basa en lo siguiente: Dado A y B enteros, y A > B:MCD (A, B) = MCD (A, r) Donde r es el residuo de A entre B (A mod B) Demostración Queremos demostrar: ¿ MCD […]

Cálculo del Inverso Modular

Ya en esta publicación se habló de lo que básicamente es el inverso modular, este post es para explicar las formas más conocidas para hallarlo. El inverso modular de A en modulo N lo representamos como: (i) X ≡ A^(-1) mod Nó(ii) X * A ≡ 1 mod N Nos interesa el cálculo de X, del cual […]

Congruencia Módulo N

El operador módulo (mod) Podemos decir que básicamente la operación modulo (mod) nos hace obtener el residuo de dos números, sea por ejemplo: Observe que los valores 1, 2 y 0 se repiten continuamente, esto es porque en módulo 3 solo obtendremos valores enteros positivos menores a 3 (esto se puede notar dado que dichos […]