从有偏见的硬币中制造出公平的硬币-yiteyi-C++库

你会得到一个函数foo（），它代表一个有偏见的硬币。调用foo（）时，它以60%的概率返回0，以40%的概率返回1。编写一个新函数，以50%的概率返回0和1。函数应该只使用foo（），而不使用其他库方法。

null

解决方案： 我们知道foo（）以60%的概率返回0。我们如何确保以50%的概率返回0和1？解决方案类似于这邮递如果我们能以同样的概率得到两个案例，那么我们就完蛋了。我们调用foo（）两次。两次呼叫都将以60%的概率返回0。因此，两个对（0，1）和（1，0）将以相同的概率从foo（）的两个调用中生成。让我们看看如何。 (0, 1): 从foo（）的两次调用中得到0后跟1的概率=0.6*0.4=0.24 (1, 0): 从foo（）的两次调用中得到1后跟0的概率=0.4*0.6=0.24 因此，这两种情况出现的概率相等。想法是返回只考虑以上两种情况，一次返回0，在其他情况下返回1。对于其他病例[（0,0）和（1,1）]，在上述两种情况中的任何一种结束之前都会复发。

下面的程序描述了如何使用foo（）以相同的概率返回0和1。

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>                         

时间复杂性： O（1）

辅助空间： O（1）

参考资料： http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin 本文由 沙尚克辛哈 并由Geeksforgeks团队审核。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。如果你喜欢GeekSforgeks，并且想贡献自己的力量，你也可以写一篇文章，然后把你的文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章