Générez 0 et 1 avec une probabilité de 25 % et 75 %
Étant donné une fonction rand50() qui renvoie 0 ou 1 avec une probabilité égale, écrivez une fonction qui renvoie 1 avec une probabilité de 75 % et 0 avec une probabilité de 25 % en utilisant uniquement rand50(). Minimisez le nombre d’appels à la méthode rand50(). De plus, l'utilisation de toute autre fonction de bibliothèque et de l'arithmétique à virgule flottante n'est pas autorisée.
L'idée est d'utiliser OU au niveau du bit . Un OU au niveau du bit prend deux bits et renvoie 0 si les deux bits sont 0, sinon le résultat est 1. Il a donc 75 % de probabilité qu'il renvoie 1.
Vous trouverez ci-dessous la mise en œuvre de l'idée ci-dessus :
C++ // Program to print 1 with 75% probability and 0 // with 25% probability #include using namespace std ; // Random Function to that returns 0 or 1 with // equal probability int rand50 () { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number the function will // return 1 else it will return 0. return rand () & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR bool rand75 () { return rand50 () | rand50 (); } // Driver code to test above functions int main () { // Initialize random number generator srand ( time ( NULL )); for ( int i = 0 ; i < 50 ; i ++ ) cout < < rand75 (); return 0 ; }
Java // Java program to print 1 with 75% probability and 0 // with 25% probability class GFG { // Random Function to that returns 0 or 1 with // equal probability static int rand50 () { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number the function will // return 1 else it will return 0. return ( int ) ( 10 * Math . random ()) & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR static int rand75 () { return rand50 () | rand50 (); } // Driver code public static void main ( String [] args ) { // Initialize random number generator //srand(time(null)); for ( int i = 0 ; i < 50 ; i ++ ) { System . out . print ( rand75 ()); } } } // This code is contributed by 29AjayKumar
Python3 # Program to print 1 with 75% probability and 0 # with 25% probability from random import randrange # Random Function to that returns 0 or 1 with # equal probability def rand50 (): # The randrange function will generate integer # between the half closed interval at end # Here by passing parameter as 02 # the function will generate integer between 0 and 1 return ( int )( randrange ( 0 2 )) & 1 # Random Function to that returns 1 with 75% # probability and 0 with 25% probability using # Bitwise OR def rand75 (): return rand50 () | rand50 () # Driver code to test above functions for i in range ( 0 50 ): print ( rand75 () end = '' ) # This code is contributed by meetgor.
C# // C# program to print 1 with 75% probability and 0 // with 25% probability using System ; public class GFG { // Instantiate random number generator static Random rand = new Random (); // Random Function to that returns 0 or 1 with // equal probability static int rand50 () { // rand() function will generate 1 or 0 // with equal probability return rand . Next ( 0 2 ); } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR static int rand75 () { return rand50 () | rand50 (); } public static void Main ( string [] args ) { for ( int i = 0 ; i < 50 ; i ++ ) { Console . Write ( rand75 ()); } } } //this code is contributed by phasing17
PHP // Program to print 1 with 75% probability // and 0 with 25% probability // Random Function to that returns 0 or // 1 with equal probability function rand50 () { // rand() function will generate // odd or even number with equal // probability. If rand() generates // odd number the function will // return 1 else it will return 0. return rand () & 1 ; } // Random Function to that returns // 1 with 75% probability and 0 // with 25% probability using // Bitwise OR function rand75 () { return rand50 () | rand50 (); } // Driver Code // Initialize random // number generator srand ( time ( NULL )); for ( $i = 0 ; $i < 50 ; $i ++ ) echo rand75 (); // This code is contributed m_kit ?>
JavaScript < script > // Program to print 1 with 75% probability and 0 // with 25% probability // Random Function to that returns 0 or 1 with // equal probability function rand50 () { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number the function will // return 1 else it will return 0. return Math . floor ( Math . random () * 10 ) & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR function rand75 () { return rand50 () | rand50 (); } // Driver code to test above functions // Initialize random number generator for ( let i = 0 ; i < 50 ; i ++ ) document . write ( rand75 ()); // This code is contributed by gfgking < /script>
Sortir
11101010110101011010000101011110100010111110101111
Complexité temporelle : O(1)
Espace auxiliaire : O(1)
Dans le même esprit, nous pouvons également utiliser ET au niveau du bit . Puisqu'il renvoie 0 avec une probabilité de 75 %, nous devons inverser le résultat.
// Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND bool rand75() { return !(rand50() & rand50()); } Vous trouverez ci-dessous la mise en œuvre de l'idée ci-dessus :
C++ #include using namespace std ; // Random Function to that returns 0 or 1 with // equal probability int rand50 () { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number the function will // return 1 else it will return 0. return rand () & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND bool rand75 () { return ! ( rand50 () & rand50 ()); } // Driver code to test above functions int main () { // Initialize random number generator srand ( time ( NULL )); for ( int i = 0 ; i < 50 ; i ++ ) cout < < rand75 (); return 0 ; }
Java class GFG { // Random Function to that returns 0 or 1 with // equal probability static int rand50 () { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number the function will // return 1 else it will return 0. return ( int ) ( 10 * Math . random ()) & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND static int rand75 () { return ( rand50 () & rand50 ()) ^ 1 ; } // Driver code public static void main ( String [] args ) { // Initialize random number generator //srand(time(null)); for ( int i = 0 ; i < 50 ; i ++ ) { System . out . print ( rand75 ()); } } }
Python3 from random import randrange # Random Function to that returns 0 or 1 with # equal probability def rand50 (): return (( int )( randrange ( 0 2 )) & 1 ) def rand75 (): return ( rand50 () & rand50 ()) ^ 1 for i in range ( 0 50 ): print ( rand75 () end = '' )
C# // C# program to implement the approach using System ; class GFG { // Random Function to that returns 0 or 1 with // equal probability static int rand50 () { // Instantiate random number generator using // system-supplied value as seed. var rand = new Random (); // rand() function will generate 0 or 1 // number with equal probability. return rand . Next ( 0 2 ); } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND static int rand75 () { return ( rand50 () & rand50 ()) ^ 1 ; } // Driver code public static void Main ( string [] args ) { // Initialize random number generator // srand(time(null)); for ( int i = 0 ; i < 50 ; i ++ ) { Console . Write ( rand75 ()); } } } // This code is contributed by phasing17
JavaScript // JavaScript program to implement the approach // Random Function to that returns 0 or 1 with // equal probability function rand50 () { return ( Math . floor ( Math . random () * 2 ) & 1 ); } function rand75 () { return ( rand50 () & rand50 ()) ^ 1 ; } for ( var i = 0 ; i < 50 ; i ++ ) process . stdout . write ( rand75 (). toString ()); //This code is contributed by phasing17
Sortir
11111111000111101111110011111110011110111111010111
Nous pouvons remplacer les opérateurs Bitwise OR et Bitwise AND par Opérateurs OU et ET aussi -
// Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // OR or AND operator int rand75() { return !(rand50() && rand50()); // return rand50() || rand50() } Nous pouvons également obtenir le résultat en utilisant le opérateur de décalage à gauche et Bitwise XOR -
C++ // Program to print 1 with 75% probability and 0 // with 25% probability #include using namespace std ; // Random Function to that returns 0 or 1 with // equal probability int rand50 () { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number the function will // return 1 else it will return 0. return rand () & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // left shift and Bitwise XOR int rand75 () { // x is one of {0 1} int x = rand50 (); x = x < < 1 ; // x is now one of {00 10} x = x ^ rand50 (); // x is now one of {00 01 10 11} return ( x > 0 ) ? 1 : 0 ; } // Driver code to test above functions int main () { // Initialize random number generator srand ( time ( NULL )); for ( int i = 0 ; i < 50 ; i ++ ) cout < < rand75 (); return 0 ; }
Java // Java program to print 1 with 75% probability and 0 // with 25% probability class GFG { // Random Function to that returns 0 or 1 with // equal probability static int rand50 () { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number the function will // return 1 else it will return 0. return ( int ) ( 10 * Math . random ()) & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // left shift and Bitwise XOR static int rand75 () { // x is one of {0 1} int x = rand50 (); x = x < < 1 ; // x is now one of {00 10} x = x ^ rand50 (); // x is now one of {00 01 10 11} return ( x > 0 ) ? 1 : 0 ; } // Driver code public static void main ( String [] args ) { for ( int i = 0 ; i < 50 ; i ++ ) System . out . print ( rand75 ()); } } // This code is contributed by 29AjayKumar
Python3 # Program to print 1 with 75% probability and 0 # with 25% probability from random import randrange # Random Function to that returns 0 or 1 with # equal probability def rand50 (): # rand range function generates a integer between # the provided ranges which is half closed interval # It will generate integer 0 or 1 if passed 02 as parameter return ( int )( randrange ( 0 2 )) & 1 # Random Function to that returns 1 with 75% # probability and 0 with 25% probability using # left shift and Bitwise XOR def rand75 (): # x is one of {0 1} x = rand50 () x = x < < 1 # x is now one of {00 10} x = x ^ rand50 () # x is now one of {00 01 10 11} return 1 if ( x > 0 ) else 0 # Driver code to test above functions for i in range ( 0 50 ): print ( rand75 () end = '' ) # This code is contributed by meetgor.
C# // C# program to print 1 with 75% probability and 0 // with 25% probability using System ; public class GFG { // Random Function to that returns 0 or 1 with // equal probability static Random rnd = new Random (); static int rand50 () { // Next(2) will generate 0 or 1 with equal probability return rnd . Next ( 2 ); } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // left shift and Bitwise XOR static int rand75 () { // x is one of {0 1} int x = rand50 (); x = x < < 1 ; // x is now one of {00 10} x = x ^ rand50 (); // x is now one of {00 01 10 11} return ( x > 0 ) ? 1 : 0 ; } static public void Main (){ for ( int i = 0 ; i < 50 ; i ++ ) Console . Write ( rand75 ()); } } // This code is contributed by shruti456rawal
PHP // Program to print 1 with // 75% probability and 0 // with 25% probability // Random Function to that // returns 0 or 1 with // equal probability function rand50 () { // rand() function will // generate odd or even // number with equal // probability. If rand() // generates odd number // the function will return // 1 else it will return 0. return rand () & 1 ; } // Random Function to that // returns 1 with 75% // probability and 0 with // 25% probability using // left shift and Bitwise XOR function rand75 () { // x is one of {0 1} $x = rand50 (); $x = $x < < 1 ; // x is now one // of {00 10} $x = $x ^ rand50 (); // x is now one of // {00 01 10 11} return ( $x > 0 ) ? 1 : 0 ; } // Driver code // Initialize random // number generator srand ( time ( NULL )); for ( $i = 0 ; $i < 50 ; $i ++ ) echo rand75 (); // This code is contributed // by ajit ?>
JavaScript < script > // Javascript program to print 1 with 75% probability and 0 // with 25% probability // Random Function to that returns 0 or 1 with // equal probability function rand50 () { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number the function will // return 1 else it will return 0. return Math . floor (( 10 * Math . random ())) & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR function rand75 () { // x is one of {0 1} let x = rand50 (); x = x < < 1 ; // x is now one of {00 10} x = x ^ rand50 (); // x is now one of {00 01 10 11} return ( x > 0 ) ? 1 : 0 ; } // Driver code for ( let i = 0 ; i < 50 ; i ++ ) { document . write ( rand75 ()); } // This code is contributed by rag2127 < /script>
Sortir
10110100111011011110111100101111110111100001111111
Complexité temporelle : O(1)
Espace auxiliaire : O(1)
Veuillez noter que les solutions ci-dessus produiront résultats différents chaque fois que nous les exécutons.
