Рубрики

Сделайте честную монету из предвзятой монеты

Вам предоставляется функция foo (), которая представляет предвзятую монету. Когда вызывается функция foo (), она возвращает 0 с вероятностью 60% и 1 с вероятностью 40%. Напишите новую функцию, которая возвращает 0 и 1 с вероятностью 50% каждая. Ваша функция должна использовать только foo (), никакой другой метод библиотеки.

Решение:
Мы знаем, что foo () возвращает 0 с вероятностью 60%. Как мы можем гарантировать, что 0 и 1 будут возвращены с вероятностью 50%?
Решение похоже на этот пост. Если мы можем как-то получить два случая с равной вероятностью, то мы закончили. Мы вызываем foo () два раза. Оба вызова вернут 0 с вероятностью 60%. Таким образом, две пары (0, 1) и (1, 0) будут сгенерированы с равной вероятностью из двух вызовов функции foo (). Давайте посмотрим, как.

(0, 1): вероятность получить 0 с последующим 1 из двух вызовов foo () = 0,6 * 0,4 = 0,24
(1, 0): вероятность получить 1 с последующим 0 из двух вызовов foo () = 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() // данный метод, который возвращает 0

          // с вероятностью 60% и 1 с 40%

    // некоторый код здесь

  
// возвращает 0 и 1 с вероятностью 50%

int my_fun() 

    int val1 = foo(); 

    int val2 = foo(); 

    if (val1 == 0 && val2 == 1) 

        return 0; // Дойдем сюда с

                  // 0.24 вероятность

    if (val1 == 1 && val2 == 0) 

        return 1;  // Дойдем сюда с

                   // 0.24 вероятность

    return my_fun(); // дойдем до

                     // (1 - 0,24 - 0,24) вероятность

  
// Код драйвера

int main() 

    cout<<my_fun(); 

    return 0; 

  
// Это код добавлен
// ратбхупендра

С

#include <stdio.h>

   

int foo() // данный метод, который возвращает 0 с вероятностью 60% и 1 с 40%

{

    // некоторый код здесь

}

  
// возвращает 0 и 1 с вероятностью 50%

int my_fun() 

{

    int val1 = foo();

    int val2 = foo();

    if (val1 == 0 && val2 == 1)

        return 0;   // достигнем с вероятностью 0,24

    if (val1 == 1 && val2 == 0)

        return 1;   // // достигнем с вероятностью 0.24

    return my_fun();  // достигнем здесь с вероятностью (1 - 0,24 - 0,24)

}

   

int main()

{

    printf ("%d ", my_fun());

    return 0;

}

PHP

<?php

  

function foo()  // данный метод, который возвращает 0

                // с вероятностью 60% и 1 с 40%

    // некоторый код здесь

  
// возвращает 0 и 1 с вероятностью 50%

function my_fun() 

    $val1 = foo(); 

    $val2 = foo(); 

    if ($val1 == 0 && $val2 == 1) 

        return 0; // Дойдем сюда с

                  // 0.24 вероятность

    if ($val1 == 1 && $val2 == 0) 

        return 1; // Дойдем сюда с

                  // 0.24 вероятность

    return my_fun(); // дойдем до

                     // (1 - 0,24 - 0,24) вероятность

  
// Код драйвера

echo my_fun(); 

  
// Это код добавлен
// Аканкша Рай
?>

Ссылки:
http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin

Эта статья составлена Shashank Sinha и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Рекомендуемые посты:

Сделайте честную монету из предвзятой монеты

0.00 (0%) 0 votes