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 otro método de biblioteca.
Solución:
sabemos que foo() devuelve 0 con un 60 % de probabilidad. ¿Cómo podemos asegurarnos de que 0 y 1 se devuelvan con un 50% de probabilidad?
La solución es similar a esta publicación. Si de alguna manera podemos obtener dos casos con la misma probabilidad, entonces hemos terminado. Llamamos a foo() dos veces. Ambas llamadas devolverán 0 con un 60% de probabilidad. Entonces, los dos pares (0, 1) y (1, 0) se generarán con la misma probabilidad a partir de dos llamadas de foo(). Veamos cómo.
(0, 1): La probabilidad de obtener 0 seguido de 1 de dos llamadas de foo() = 0,6 * 0,4 = 0,24
(1, 0): La probabilidad de obtener 1 seguido de 0 de dos llamadas de foo() = 0,4 * 0,6 = 0,24
Entonces los dos casos aparecen con igual probabilidad. La idea es devolver considerar solo los dos casos anteriores, devolver 0 en un caso, devolver 1 en otro caso. Para otros casos [(0, 0) y (1, 1)], repite hasta que termines en cualquiera de los dos casos anteriores.
El siguiente programa muestra cómo podemos usar foo() para devolver 0 y 1 con la misma probabilidad.
C++
#include <bits/stdc++.h> using namespace std; int foo() // given method that returns 0 // with 60% probability and 1 with 40% { // some code here } // returns both 0 and 1 with 50% probability int my_fun() { int val1 = foo(); int val2 = foo(); if (val1 == 0 && val2 == 1) return 0; // Will reach here with // 0.24 probability if (val1 == 1 && val2 == 0) return 1; // Will reach here with // 0.24 probability return my_fun(); // will reach here with // (1 - 0.24 - 0.24) probability } // Driver Code int main() { cout << my_fun(); return 0; } // This is code is contributed // by rathbhupendra
C
#include <stdio.h> int foo() // given method that returns 0 with 60% // probability and 1 with 40% { // some code here } // returns both 0 and 1 with 50% probability int my_fun() { int val1 = foo(); int val2 = foo(); if (val1 == 0 && val2 == 1) return 0; // Will reach here with 0.24 probability if (val1 == 1 && val2 == 0) return 1; // // Will reach here with 0.24 // probability return my_fun(); // will reach here with (1 - 0.24 - // 0.24) probability } int main() { printf("%d ", my_fun()); return 0; }
Java
import java.io.*; class GFG { // Given method that returns 0 // with 60% probability and 1 with 40% static int foo() { // some code here } // Returns both 0 and 1 with 50% probability static int my_fun() { int val1 = foo(); int val2 = foo(); if (val1 == 0 && val2 == 1) return 0; // Will reach here with // 0.24 probability if (val1 == 1 && val2 == 0) return 1; // Will reach here with // 0.24 probability return my_fun(); // will reach here with // (1 - 0.24 - 0.24) probability } // Driver Code public static void main(String[] args) { System.out.println(my_fun()); } } // This code is contributed by ShubhamCoder
Python3
# Python3 program for the # above approach def foo(): # Some code here pass # Returns both 0 and 1 # with 50% probability def my_fun(): val1, val2 = foo(), foo() if val1 ^ val2: # Will reach here with # (0.24 + 0.24) probability return val1 # Will reach here with # (1 - 0.24 - 0.24) probability return my_fun() # Driver Code if __name__ == '__main__': print(my_fun()) # This code is contributed by sgshah2
C#
using System; class GFG { // given method that returns 0 // with 60% probability and 1 with 40% static int foo() { // some code here } // returns both 0 and 1 with 50% probability static int my_fun() { int val1 = foo(); int val2 = foo(); if (val1 == 0 && val2 == 1) return 0; // Will reach here with // 0.24 probability if (val1 == 1 && val2 == 0) return 1; // Will reach here with // 0.24 probability return my_fun(); // will reach here with // (1 - 0.24 - 0.24) probability } // Driver Code static public void Main() { Console.Write(my_fun()); } } // This is code is contributed // by ShubhamCoder
PHP
<?php function foo() // given method that returns 0 // with 60% probability and 1 with 40% { // some code here } // returns both 0 and 1 with 50% probability function my_fun() { $val1 = foo(); $val2 = foo(); if ($val1 == 0 && $val2 == 1) return 0; // Will reach here with // 0.24 probability if ($val1 == 1 && $val2 == 0) return 1; // Will reach here with // 0.24 probability return my_fun(); // will reach here with // (1 - 0.24 - 0.24) probability } // Driver Code echo my_fun(); // This is code is contributed // by Akanksha Rai ?>
Javascript
<script> // Given method that returns 0 with // 60% probability and 1 with 40% function foo() { // Some code here } // Returns both 0 and 1 with // 50% probability function my_fun() { var val1 = foo(); var val2 = foo(); if (val1 == 0 && val2 == 1) return 0; // Will reach here with // 0.24 probability if (val1 == 1 && val2 == 0) return 1; // Will reach here with // 0.24 probability return my_fun(); // Will reach here with // (1 - 0.24 - 0.24) probability } // Driver Code document.write(my_fun()); // This code is contributed by noob2000 </script>
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Referencias:
http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin
Este artículo fue compilado por Shashank Sinha y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA