Genera enteros del 1 al 7 con igual probabilidad

Dada una función foo() que devuelve números enteros del 1 al 5 con la misma probabilidad, escriba una función que devuelva números enteros del 1 al 7 con la misma probabilidad usando solo foo(). Minimice el número de llamadas al método foo(). Además, no se permite el uso de ninguna otra función de biblioteca y no se permite la aritmética de coma flotante.
Solución: 
sabemos que foo() devuelve números enteros del 1 al 5. ¿Cómo podemos asegurarnos de que los números enteros del 1 al 7 ocurran con la misma probabilidad? 
Si de alguna manera generamos números enteros desde 1 hasta un múltiplo de 7 (como 7, 14, 21, …) con la misma probabilidad, podemos usar la división módulo por 7 seguida de la suma de 1 para obtener los números del 1 al 7 con igual probabilidad.
Podemos generar del 1 al 21 con igual probabilidad usando la siguiente expresión.

 5*foo() + foo() -5 

Veamos cómo se puede usar la expresión anterior. 
1. Para cada valor de first foo(), puede haber 5 combinaciones posibles para los valores de second foo(). Entonces, hay un total de 25 combinaciones posibles. 
2. El rango de valores devuelto por la ecuación anterior es de 1 a 25, cada número entero ocurre exactamente una vez. 
3. Si el valor de la ecuación resulta ser menor que 22, devuelva la división de módulo por 7 seguida de la suma de 1. De lo contrario, vuelva a llamar al método recursivamente. La probabilidad de devolver cada número entero se convierte así en 1/7.
El siguiente programa muestra que la expresión devuelve cada número entero del 1 al 25 exactamente una vez. 
 

#include <stdio.h>
 
int main()
{
    int first, second;
    for ( first=1; first<=5; ++first )
        for ( second=1; second<=5; ++second )
            printf ("%d \n", 5*first + second - 5);
    return 0;
}

// Java code to demonstrate
// expression returns each integer
// from 1 to 25 exactly once
 
class GFG {
    public static void main(String[] args)
    {
        int first, second;
        for ( first=1; first<=5; ++first )
            for ( second=1; second<=5; ++second )
            System.out.printf ("%d \n", 5*first + second - 5);
    }
}
 
// This code is contributed by
// Smitha Dinesh Semwal

# Python3 code to demonstrate
# expression returns each integer
# from 1 to 25 exactly once
 
if name == '__main__':
     
    for first in range(1, 6):
        for second in range(1, 6):
                print(5 * first + second - 5)
 
# This code is contributed by Smitha Dinesh Semwal.

// C# code to demonstrate expression returns
// each integer from 1 to 25 exactly once
using System;
 
class GFG {
     
    public static void Main()
    {
        int first, second;
 
        for ( first = 1; first <= 5; ++first )
            for ( second = 1; second <= 5; ++second )
                Console.WriteLine ( 5*first + second - 5);
    }
}
 
// This code is contributed by Sam007.

<?php
// PHP program to Generate integer
// from 1 to 7 with equal probability
 
    $first;
    $second;
    for ( $first = 1; $first <= 5; ++$first )
        for ( $second = 1; $second <= 5; ++$second )
            echo 5 * $first + $second - 5, "\n";
 
// This code is contributed by ajit.
?>

<script>
 
// Javascript Program to demonstrate
// expression returns each integer
// from 1 to 25 exactly once
 
 
// Driver Code
 
    let first, second;
    for ( first=1; first<=5; ++first )
        for ( second=1; second<=5; ++second ) {
             document.write( 5*first + second - 5);
             document.write("<br />");
        }
 
</script>

Producción : 
 

1
2
.
.
24
25

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.

El siguiente programa muestra cómo podemos usar foo() para devolver 1 a 7 con la misma probabilidad. 
 

// C++ program to Generate integer from
// 1 to 5 with equal probability
#include <stdio.h>
 
// given method that returns 1 to 5 with equal probability
int foo()
{
    // some code here
}
 
int my_rand() // returns 1 to 7 with equal probability
{
    int i;
    i = 5*foo() + foo() - 5;
    if (i < 22)
        return i%7 + 1;
    return my_rand();
}
// Driver code
int main()
{
    printf ("%d ", my_rand());
    return 0;
}

// Java program to Generate integer from
// 1 to 5 with equal probability
class GfG
{
 
// given method that returns 1 to 5 with equal probability
static int foo()
{
    // some code here
    return 0;
}
 
// returns 1 to 7 with equal probability
public static int my_rand() 
{
    int i;
    i = 5*foo() + foo() - 5;
    if (i < 22)
        return i%7 + 1;
    return my_rand();
}
 
// Driver code
public static void main (String[] args) {
 
    System.out.println(my_rand());
}
}

# Python3 program to Generate integer
# from 1 to 5 with equal probability
# given method that returns 1 to 5
# with equal probability
def foo():
 
    # some code here
    return 0;
 
# returns 1 to 7 with equal probability
def my_rand():
    i = 0;
    i = (5 * foo()) + (foo() - 5);
    if (i < 22):
        if(i < 0):
            return (i % 7 - 7) + 1;
        else:
            return (i % 7) + 1;
             
    return my_rand();
 
# Driver code
if __name__ == '__main__':
    print(my_rand());
 
# This code contributed by PrinciRaj1992

// C# program to Generate integer from
// 1 to 5 with equal probability
using System;
class GfG
{
  
// given method that returns 1 to 5 with equal probability
static int foo()
{
    // some code here
    return 0;
}
  
// returns 1 to 7 with equal probability
public static int my_rand() 
{
    int i;
    i = 5*foo() + foo() - 5;
    if (i < 22)
        return i%7 + 1;
    return my_rand();
}
  
// Driver code
public static void Main () {
  
    Console.Write(my_rand()+"\n");
}
}

<?php
// PHP program to Generate integer from
// 1 to 5 with equal probability
// given method that returns 1 to 5
// with equal probability
function foo()
{
    // some code here
}
 
// returns 1 to 7 with equal probability
function my_rand()
{
    $i;
    $i = 5 * foo() + foo() - 5;
    if ($i < 22)
        return $i % 7 + 1;
    return my_rand();
}
 
// Driver code
echo my_rand();
 
// This code is contributed by Tushil.
?>

<script>
 
// Javascript program to Generate integer from
// 1 to 5 with equal probability
 
    // given method that returns 1 to 5 with equal probability
    function foo()
    {
        // some code here
        return 0;
    }
     
    // returns 1 to 7 with equal probability
    function my_rand()
    {
        let i;
        i = 5*foo() + foo() - 5;
        if (i < 22)
            return i%7 + 1;
        return my_rand();
    }
     
    // Driver code
    document.write(my_rand());
     
    // This code is contributed by rag2127
     
</script>

Producción: 

-4

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)

Este artículo fue compilado por Aashish Barnwal y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.