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é:
lineær søgning i javaC++
// Program to print 1 with 75% probability and 0 // with 25% probability #include
// 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
# 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# 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
// 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 ?> <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é:
reference datatyper i javaC++
#include
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()); } } }
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# 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 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 -
omvendt streng i javaC++
// Program to print 1 with 75% probability and 0 // with 25% probability #include
// 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
# 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# 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
// 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 ?> <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.