É fácil gerar uma moeda justa usando uma moeda injusta, mas o inverso é mais difícil de realizar.

Seu programa receberá um número X (entre 0 e 1, inclusive) como entrada. A entrada não deve simplesmente ser codificada como um número no meio do código-fonte. Ele deve retornar um único dígito: a 1com uma probabilidade de X e um 0caso contrário.

Seu programa só pode usar uma forma de gerador de números aleatórios no código-fonte: int(rand(2))(ou equivalente), que retorna zero ou um com probabilidade igual. Você pode incluir ou acessar esta função quantas vezes desejar no seu código. Você também deve fornecer a função como parte do código.

Seu programa não tem permissão para usar outras funções geradoras de número aleatório ou fontes externas (como funções de data e hora) que possam funcionar como uma função geradora de número aleatório. Ele também não pode acessar nenhum arquivo externo ou passar o trabalho para programas externos.

Este é o código de golfe, a resposta mais curta ganha.

Perl, 37 42 char

($d/=2)+=rand>.5for%!;print$d/2<pop|0

Assume probabilidade arbitrária como argumento de linha de comando. Cria um número aleatório uniforme $de o compara com a entrada.

Solução anterior de 52 caracteres

$p=<>;do{$p*=2;$p-=($-=$p)}while$--(.5<rand);print$-

Python, 81 caracteres

import random
print(sum(random.randint(0,1)*2**-i for i in range(9))<input()*2)+0

Pode demorar um pouco, mas nunca mais que 1%.

Mathematica 165

Não é simplificado, mas alguns podem encontrar o algoritmo de interesse:

d = RealDigits; r = RandomInteger;
f@n_ := If[(c = Cases[Transpose@{a = Join[ConstantArray[0, Abs[d[n, 2][[2]]]], d[n, 2][[1]]], 
         RandomInteger[1, {Length@a}]}, {x_, x_}]) == {}, r, c[[1, 1]]]

Uso

f[.53]

1

Verifica

Vamos ver se f[.53]realmente produz o valor em 1torno de 53% do tempo. Cada teste calcula a% para amostras de 10 ^ 4.

50 desses testes são executados e calculados a média.

Table[Count[Table[f[.53], {10^4}], 1]/10^4 // N, {50}]
Mean[%]

{0,5292, 0,5256, 0,5307, 0,5266, 0,5245, 0,5212, 0,5316, 0,5345, 0,5297, 0,5334, 0,5306, 0,5288, 0,528, 0,5379, 0,5293, 0,5263, 0,539, 0,5322, 0,5195, 0,5208, 0,5382, 0,543, 0,5336, 0,5305, 0,5303 , 0,5297, 0,5318, 0,5243, 0,5281, 0,5361, 0,5349, 0,5308, 0,5265, 0,5309, 0,5233, 0,5345, 0,5316, 0,5376, 0,5264, 0,5269, 0,5295, 0,523, 0,5294, 0,5326, 0,5316, 0,5334, 0,5165, 0,5296, 0,5266, 0,5296 }

0.529798

Histograma de resultados

Explicação (alerta de spoiler!)

A representação da base 2 de 0,53 é

.10000111101011100001010001111010111000010100011110110

Prosseguindo da esquerda para a direita, um dígito de cada vez:

Se RandomInteger [] retornar 1, então answer = 1,

Senão Se o segundo RandomInteger [] retornar 0, então responda = 0,

Senão Se o terceiro RandomInteger [] retornar 0, a resposta = 0,

Outro....

Se, quando todos os dígitos tiverem sido testados, ainda não houver resposta, answer = RandomInteger [].

Haskell, 107 caracteres:

import System.Random
g p|p>1=print 1|p<0=print 0|1>0=randomIO>>=g.(p*2-).f
f x|x=1|1>0=0.0
main=readLn>>=g

Wolfram Language (Mathematica) , 42 bytes

RandomInteger[]/.⌈1-2#⌉:>#0@Mod[2#,1]&

Experimente online!

Essa é uma abordagem recursiva. Sem algoritmo, o algoritmo é:

• Se a probabilidade de entrada pfor menor que 1/2, quando o lançamento da moeda subir 0, retorne 0. Caso contrário, prossiga 2p; assumindo a correção, a probabilidade geral de obter 1 é metade de 2pou p.
• Se a probabilidade de entrada pfor maior que 1/2, quando o lançamento da moeda aparecer 1, retorne 1. Caso contrário, continue 2p-1; assumindo a correção, a probabilidade geral de obter 0 é metade de 1-(2p-1)ou 1-p.

Para encurtar, começamos com o sorteio aleatório de moedas, que, em qualquer ramo, é retornado metade do tempo. Se o coinflip não corresponder ao caso em que devemos devolvê-lo, substitua-o pelo resultado da recorrência no 2pmódulo 1. (Ou seja, quando pfor menor que 1/2, substitua 1; quando pfor maior que 1/2 , substitua 0. Isso equivale a substituir ⌈1-2p⌉.)