Generer 0 og 1 med 25% og 75% sandsynlighed
Givet en funktion rand50(), der returnerer 0 eller 1 med lige stor sandsynlighed, skriv en funktion, der returnerer 1 med 75 % sandsynlighed og 0 med 25 % sandsynlighed kun ved at bruge rand50(). Minimer antallet af opkald til rand50()-metoden. Det er heller ikke tilladt at bruge andre biblioteksfunktioner og flydende kommaaritmetik.
Ideen er at bruge Bitvis ELLER . En bitvis OR tager to bit og returnerer 0, hvis begge bit er 0, mens resultatet ellers er 1. Så det har 75 % sandsynlighed for, at det returnerer 1.
Nedenfor er implementeringen af ovenstående idé:
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>
Produktion
11101010110101011010000101011110100010111110101111
Tidskompleksitet: O(1)
Hjælpeplads: O(1)
På lignende linjer kan vi også bruge Bitvis OG . Da det returnerer 0 med 75% sandsynlighed, er vi nødt til at invertere resultatet.
// Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND bool rand75() { return !(rand50() & rand50()); } Nedenfor er implementeringen af ovenstående idé:
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
Produktion
11111111000111101111110011111110011110111111010111
Vi kan erstatte Bitwise OR og Bitwise AND operatorer med OR- og AND-operatorer ligeså -
// 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() } Vi kan også opnå resultatet ved hjælp af venstre skiftoperatør og 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>
Produktion
10110100111011011110111100101111110111100001111111
Tidskompleksitet: O(1)
Hjælpeplads: O(1)
Bemærk venligst, at ovenstående løsninger vil producere forskellige resultater hver gang vi kører dem.
![Top 10 største byer i USA efter befolkning rangeret [Opdateret liste 2024]](https://techcodeview.com/img/us-gk/09/top-10-largest-cities-united-states-population-ranked.webp)
