Łatwo jest wygenerować uczciwą monetę za pomocą nieuczciwej monety, ale trudniej jest uzyskać odwrotność.

Twój program otrzyma jedną liczbę X (od 0 do 1 włącznie) jako dane wejściowe. Dane wejściowe nie mogą być po prostu zakodowane na stałe jako liczba w środku kodu źródłowego. Następnie musi zwrócić jedną cyfrę: a 1z prawdopodobieństwem X, a 0inaczej.

Twój program może używać tylko jednej formy generatora liczb losowych w kodzie źródłowym: int(rand(2))(lub odpowiednika), która zwraca zero lub jeden z jednakowym prawdopodobieństwem. Możesz włączyć lub uzyskać dostęp do tej funkcji tyle razy, ile chcesz w swoim kodzie. Musisz również podać tę funkcję samodzielnie jako część kodu.

Twój program nie może używać żadnych innych funkcji generujących liczby losowe ani źródeł zewnętrznych (takich jak funkcje godziny i daty), które mogłyby działać jako funkcja generowania liczb losowych. Nie może również uzyskać dostępu do żadnych plików zewnętrznych ani przekazać zadania programom zewnętrznym.

To jest golf golfowy, wygrywa najkrótsza odpowiedź.

Perl, 37 42 char

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

Przyjmuje dowolne prawdopodobieństwo jako argument wiersza poleceń. Buduje jednolitą liczbę losową $di porównuje ją z danymi wejściowymi.

Wcześniej 52-znakowe rozwiązanie

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

Python, 81 znaków

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

Może być trochę wyłączone, ale nigdy więcej niż 1%.

Mathematica 165

Nie usprawniono, ale niektórzy mogą znaleźć interesujący algorytm:

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]]]

Stosowanie

f[.53]

1

Czek

Zobaczmy, czy f[.53]naprawdę generuje wartość w 1około 53% przypadków. Każdy test oblicza% dla próbek 10 ^ 4.

50 takich testów jest uruchamianych i uśrednianych.

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,529 }

0,529798

Histogram wyników

Wyjaśnienie (alert spoilera!)

Podstawowa reprezentacja .53 to

.10000111101011100001010001111010111000010100011110110

Przechodząc od lewej do prawej, jedna cyfra na raz:

Jeśli RandomInteger [] zwraca 1, to odpowiedź = 1,

W przeciwnym razie Jeśli druga funkcja RandomInteger [] zwraca 0, to odpowiedź = 0,

W przeciwnym razie Jeśli trzeci RandomInteger [] zwraca 0, odpowiedź = 0,

Jeszcze....

Jeśli po przetestowaniu wszystkich cyfr nadal nie ma odpowiedzi, answer = RandomInteger [].

Haskell, 107 znaków:

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 bajty

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

Wypróbuj online!

To jest podejście rekurencyjne. Niegolfowany algorytm to:

• Jeśli prawdopodobieństwo wejściowe pjest mniejsze niż 1/2, to gdy coinflip wyniesie 0, zwróć 0. W przeciwnym razie powtórz dalej 2p; przy założeniu poprawności ogólne prawdopodobieństwo uzyskania 1 wynosi połowę 2plub p.
• Jeśli prawdopodobieństwo wejściowe pjest większe niż 1/2, to gdy pojawi się spinacz monety 1, zwróć 1. W przeciwnym razie powtórz dalej 2p-1; przy założeniu poprawności ogólne prawdopodobieństwo uzyskania 0 wynosi połowę 1-(2p-1)lub 1-p.

Krótko mówiąc, zaczynamy od losowego spinacza do monety, który w każdej gałęzi jest zwracany o połowę krócej. Jeśli spinacz nie pasuje do przypadku, w którym mamy go zwrócić, zastąp go wynikiem rekurencji w module 2p1. (To znaczy, gdy pjest mniejszy niż 1/2, zamień 1; kiedy pjest większy niż 1/2 , zamień 0. Jest to równoważne zastąpieniu ⌈1-2p⌉.)