Sangat mudah untuk menghasilkan koin yang adil menggunakan koin yang tidak adil, tetapi sebaliknya lebih sulit untuk dicapai.

Program Anda akan menerima satu angka X (antara 0 dan 1, inklusif) sebagai input. Input tidak boleh hanya berupa hard-kode sebagai angka di tengah kode sumber. Kemudian harus mengembalikan satu digit: a 1dengan probabilitas X dan 0sebaliknya.

Program Anda hanya diperbolehkan menggunakan satu bentuk generator angka acak dalam kode sumber: int(rand(2))(atau yang setara), yang mengembalikan nol atau yang memiliki probabilitas yang sama. Anda dapat memasukkan atau mengakses fungsi ini sebanyak yang Anda inginkan dalam kode Anda. Anda juga harus menyediakan fungsi sendiri sebagai bagian dari kode.

Program Anda tidak diperbolehkan menggunakan fungsi penghasil nomor acak atau sumber eksternal lainnya (seperti fungsi waktu dan tanggal) yang dapat berfungsi sebagai fungsi penghasil nomor acak. Itu juga tidak dapat mengakses file eksternal atau meneruskan pekerjaan ke program eksternal.

Ini kode golf, jawaban terpendek menang.

Perl, 37 42 char

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

Membawa probabilitas arbitrer sebagai argumen baris perintah. Membuat nomor acak yang seragam $ddan membandingkannya dengan input.

Sebelumnya, 52 solusi char

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

Python, 81 karakter

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

Dapat dimatikan sedikit, tetapi tidak pernah lebih dari 1%.

Mathematica 165

Tidak disederhanakan, tetapi beberapa mungkin menemukan algoritma yang menarik:

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

Pemakaian

f[.53]

1

Memeriksa

Mari kita lihat apakah f[.53]benar-benar menghasilkan nilai 1sekitar 53% dari waktu. Setiap tes menghitung% untuk sampel 10 ^ 4.

50 tes semacam itu dijalankan dan dirata-rata.

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,5304, 0,5306, 0,5288, 0,528, 0,5379, 0,5293, 0,5263, 0,539, 0,5322, 0,5195, 0,5208, 0,5382, 0,5330, 0,5330 , 0.5297, 0.5318, 0.5243, 0.5281, 0.5361, 0.5349, 0.5308, 0.5265, 0.5303, 0.5345, 0.5316, 0.5376, 0.5264, 0.5295, 0.5295, 0.523, 0.5294, 0.5316, 0.5334, 0.5336, 0.5296, 0.5296, 0.5306, 0.5306, 0.5303, 0.5303, 0.5303, 0.5316 }

0,529798

Histogram hasil

Penjelasan (peringatan spoiler!)

Representasi basis 2 dari .53 adalah

.10000111101011100001010001111010111000010100011110110

Melanjutkan dari kiri ke kanan, satu digit pada satu waktu:

Jika RandomInteger [] mengembalikan 1, maka jawab = 1,

Lain Jika RandomInteger kedua [] mengembalikan 0, maka jawab = 0,

Lain Jika RandomInteger ketiga [] mengembalikan 0, jawabannya = 0,

Lain....

Jika, ketika semua digit telah diuji, masih belum ada jawaban, maka jawab = RandomInteger [].

Haskell, 107 karakter:

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

Bahasa Wolfram (Mathematica) , 42 byte

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

Cobalah online!

Ini adalah pendekatan rekursif. Tidak digabungkan, algoritmenya adalah:

• Jika probabilitas input pkurang dari 1/2, maka ketika coinflip muncul 0, kembalikan 0. Jika tidak, kambuh kembali 2p; dengan asumsi benar, probabilitas keseluruhan untuk mendapatkan 1 adalah setengah 2patau p.
• Jika probabilitas input plebih besar dari 1/2, maka ketika coinflip muncul 1, kembalikan 1. Jika tidak, muncul kembali 2p-1; dengan asumsi benar, probabilitas keseluruhan untuk mendapatkan 0 adalah setengah 1-(2p-1)atau 1-p.

Untuk membuatnya lebih pendek, kita mulai dengan coinflip acak, yang, di cabang mana pun, dikembalikan separuh waktu. Jika coinflip tidak cocok dengan case ketika kita seharusnya mengembalikannya, ganti dengan hasil pengulangan pada 2pmodulo 1. (Yaitu, ketika pkurang dari 1/2, ganti 1; ketika plebih besar dari 1/2 , ganti 0. Ini sama dengan mengganti ⌈1-2p⌉.)