Diberikan fungsi yang menghasilkan bilangan bulat acak dalam kisaran 1 hingga 5, tulis fungsi yang menghasilkan bilangan bulat acak dalam kisaran 1 hingga 7.

1. Apa itu solusi sederhana?
2. Apa solusi yang efektif untuk mengurangi penggunaan memori atau berjalan pada CPU yang lebih lambat?

Ini setara dengan solusi Adam Rosenfield, tetapi mungkin sedikit lebih jelas bagi sebagian pembaca. Ini mengasumsikan rand5 () adalah fungsi yang mengembalikan bilangan bulat acak secara statistik dalam kisaran 1 hingga 5 inklusif.

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

Bagaimana cara kerjanya? Pikirkan seperti ini: bayangkan mencetak array dua dimensi ini di atas kertas, menempelkannya ke papan panah dan melemparkan panah secara acak ke sana. Jika Anda menekan nilai bukan nol, itu adalah nilai acak statistik antara 1 dan 7, karena ada jumlah yang sama dari nilai bukan nol untuk dipilih. Jika Anda menekan nol, terus lempar panah sampai Anda memukul nol. Itulah yang dilakukan kode ini: indeks i dan j secara acak memilih lokasi pada papan panah, dan jika kami tidak mendapatkan hasil yang baik, kami terus melempar panah.

Seperti kata Adam, ini bisa berjalan selamanya dalam kasus terburuk, tetapi secara statistik, kasus terburuk tidak pernah terjadi. :)

Tidak ada solusi (tepat benar) yang akan berjalan dalam jumlah waktu yang konstan, karena 1/7 adalah desimal tak terbatas dalam basis 5. Salah satu solusi sederhana adalah dengan menggunakan sampel penolakan, misalnya:

int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

Ini memiliki runtime yang diharapkan dari 25/21 = 1,19 iterasi loop, tetapi ada kemungkinan sangat kecil untuk mengulang selamanya.

Saya ingin menambahkan jawaban lain, selain jawaban pertama saya . Jawaban ini mencoba untuk meminimalkan jumlah panggilan rand5()per panggilan rand7(), untuk memaksimalkan penggunaan keacakan. Artinya, jika Anda menganggap keacakan sebagai sumber daya yang berharga, kami ingin menggunakan sebanyak mungkin itu, tanpa membuang bit acak. Jawaban ini juga memiliki beberapa kesamaan dengan logika yang disajikan dalam jawaban Ivan .

The entropi dari suatu variabel acak adalah kuantitas didefinisikan dengan baik. Untuk variabel acak yang mengambil status N dengan probabilitas yang sama (distribusi seragam), entropinya adalah log ₂ N. Dengan demikian, rand5()memiliki sekitar 2,32193 bit entropi, dan rand7()memiliki sekitar 2,80735 bit entropi. Jika kita berharap untuk memaksimalkan penggunaan keacakan kita, kita perlu menggunakan semua 2,32193 bit entropi dari setiap panggilan rand5(), dan menerapkannya untuk menghasilkan 2,80735 bit entropi yang diperlukan untuk setiap panggilan rand7(). Batas mendasar, maka, adalah bahwa kita tidak dapat melakukan lebih baik daripada log (7) / log (5) = 1,20906 panggilan kerand5() per panggilan ke rand7().

Catatan samping: semua logaritma dalam jawaban ini akan menjadi basis 2 kecuali ditentukan sebaliknya. rand5()akan diasumsikan untuk mengembalikan angka dalam kisaran [0, 4], dan rand7()akan diasumsikan untuk mengembalikan angka dalam kisaran [0, 6]. Menyesuaikan rentang ke [1, 5] dan [1, 7] masing-masing adalah sepele.

jadi bagaimana kita melakukannya? Kami menghasilkan bilangan real acak tak terhingga yang akurat antara 0 dan 1 (berpura-pura saat itu kami benar-benar dapat menghitung dan menyimpan bilangan yang tepat tak terhingga - kami akan memperbaikinya nanti). Kita dapat menghasilkan angka seperti itu dengan menghasilkan digitnya di basis 5: kita memilih angka acak 0. a₁ a₂ a₃ ..., di mana setiap digit a _idipilih oleh panggilan ke rand5(). Misalnya, jika RNG kami memilih a _i= 1 untuk semua i, maka abaikan fakta bahwa itu tidak terlalu acak, itu akan sesuai dengan bilangan real 1/5 + 1/5 ² + 1/5 ³ + ... = 1/4 (jumlah deret geometri).

Ok, jadi kami telah memilih bilangan real acak antara 0 dan 1. Saya sekarang mengklaim bahwa bilangan acak tersebut didistribusikan secara seragam. Secara intuitif, ini mudah dimengerti, karena setiap digit dipilih secara seragam, dan jumlahnya sangat tepat. Namun, bukti formal ini agak lebih terlibat, karena sekarang kita berurusan dengan distribusi kontinu, bukan distribusi diskrit, jadi kita perlu membuktikan bahwa probabilitas bahwa nomor kita terletak pada interval [ a, b] sama dengan panjang interval itu,b - a ,. Buktinya dibiarkan sebagai latihan untuk pembaca =).

Sekarang kita memiliki bilangan real acak yang dipilih secara seragam dari rentang [0, 1], kita perlu mengonversinya menjadi serangkaian angka acak seragam dalam rentang [0, 6] untuk menghasilkan output rand7(). Bagaimana kita melakukan ini? Kebalikan dari apa yang baru saja kita lakukan - kita mengonversinya menjadi desimal yang sangat tepat pada basis 7, dan kemudian setiap basis 7 digit akan sesuai dengan satu output rand7().

Mengambil contoh dari sebelumnya, jika kami rand5()menghasilkan aliran tak terbatas 1, maka bilangan real acak kami akan menjadi 1/4. Mengubah 1/4 ke basis 7, kita mendapatkan desimal tak terhingga 0.15151515 ..., jadi kita akan menghasilkan sebagai output 1, 5, 1, 5, 1, 5, dll.

Oke, jadi kita punya ide utama, tetapi kita punya dua masalah tersisa: kita tidak bisa benar-benar menghitung atau menyimpan bilangan real yang sangat tepat, jadi bagaimana kita berurusan dengan hanya sebagian yang terbatas? Kedua, bagaimana kita benar-benar mengubahnya menjadi basis 7?

Salah satu cara kita dapat mengonversi angka antara 0 dan 1 ke basis 7 adalah sebagai berikut:

1. Kalikan dengan 7
2. Bagian integral dari hasilnya adalah basis 7 digit berikutnya
3. Kurangi bagian integral, hanya menyisakan bagian fraksional
4. Pergi langkah 1

Untuk menangani masalah ketelitian tak terbatas, kami menghitung hasil parsial, dan kami juga menyimpan batas atas pada hasil apa yang mungkin terjadi. Artinya, misalkan kita sudah menelepon rand5()dua kali dan kembali 1 kali. Jumlah yang kami hasilkan sejauh ini adalah 0,11 (basis 5). Apa pun sisa dari serangkaian panggilan tak terbatas untuk rand5()diproduksi, bilangan real acak yang kami hasilkan tidak akan pernah lebih besar dari 0,12: selalu benar bahwa 0,11 ≤ 0,11xyz ... <0,12.

Jadi, melacak nomor saat ini sejauh ini, dan nilai maksimum yang bisa diambil, kami mengonversi kedua angka menjadi basis 7. Jika mereka menyetujui kangka pertama , maka kami dapat dengan aman menampilkan kangka berikutnya - terlepas dari apa yang Aliran tak terbatas dari basis 5 digit adalah, mereka tidak akan pernah mempengaruhi kdigit berikutnya dari representasi basis 7!

Dan itulah algoritme - untuk menghasilkan output selanjutnya rand7(), kami hanya menghasilkan sebanyak digit yang rand5()kami perlukan untuk memastikan bahwa kami tahu dengan pasti nilai digit berikutnya dalam konversi bilangan real acak ke basis 7. Berikut ini adalah implementasi Python, dengan test harness:

import random

rand5_calls = 0
def rand5():
    global rand5_calls
    rand5_calls += 1
    return random.randint(0, 4)

def rand7_gen():
    state = 0
    pow5 = 1
    pow7 = 7
    while True:
        if state / pow5 == (state + pow7) / pow5:
            result = state / pow5
            state = (state - result * pow5) * 7
            pow7 *= 7
            yield result
        else:
            state = 5 * state + pow7 * rand5()
            pow5 *= 5

if __name__ == '__main__':
    r7 = rand7_gen()
    N = 10000
    x = list(next(r7) for i in range(N))
    distr = [x.count(i) for i in range(7)]
    expmean = N / 7.0
    expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))

    print '%d TRIALS' % N
    print 'Expected mean: %.1f' % expmean
    print 'Expected standard deviation: %.1f' % expstddev
    print
    print 'DISTRIBUTION:'
    for i in range(7):
        print '%d: %d   (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
    print
    print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)

Catatan yang rand7_gen()mengembalikan generator, karena memiliki keadaan internal yang melibatkan konversi angka ke basis 7. Uji harness memanggil next(r7)10.000 kali untuk menghasilkan 10.000 angka acak, dan kemudian mengukur distribusi mereka. Hanya matematika bilangan bulat yang digunakan, sehingga hasilnya persis benar.

Perhatikan juga bahwa angka-angka di sini menjadi sangat besar, sangat cepat. Kekuatan 5 dan 7 tumbuh dengan cepat. Oleh karena itu, kinerja akan mulai menurun secara nyata setelah menghasilkan banyak angka acak, karena aritmatika bignum. Tapi ingat di sini, tujuan saya adalah untuk memaksimalkan penggunaan bit acak, bukan untuk memaksimalkan kinerja (meskipun itu adalah tujuan sekunder).

Dalam satu menjalankan ini, saya membuat 12091 panggilan ke rand5()untuk 10.000 panggilan ke rand7(), mencapai minimum panggilan log (7) / log (5) rata-rata untuk 4 angka signifikan, dan hasil yang dihasilkan seragam.

Untuk mem-porting kode ini ke bahasa yang tidak memiliki bilangan bulat besar yang built-in, Anda harus membatasi nilai pow5dan pow7nilai maksimum tipe integral asli Anda - jika terlalu besar, maka setel ulang segalanya dan mulai lagi dari awal. Ini akan meningkatkan jumlah rata-rata panggilan rand5()per panggilan menjadi rand7()sangat sedikit, tetapi mudah-mudahan itu tidak akan meningkat terlalu banyak bahkan untuk bilangan bulat 32 atau 64-bit.

(Saya telah mencuri jawaban Adam Rosenfeld dan membuatnya berjalan sekitar 7% lebih cepat.)

Asumsikan bahwa rand5 () mengembalikan salah satu dari {0,1,2,3,4} dengan distribusi yang sama dan tujuannya adalah mengembalikan {0,1,2,3,4,5,6} dengan distribusi yang sama.

int rand7() {
  i = 5 * rand5() + rand5();
  max = 25;
  //i is uniform among {0 ... max-1}
  while(i < max%7) {
    //i is uniform among {0 ... (max%7 - 1)}
    i *= 5;
    i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
    max %= 7;
    max *= 5; //once again, i is uniform among {0 ... max-1}
  }
  return(i%7);
}

Kami melacak nilai terbesar yang dapat dihasilkan loop dalam variabel max. Jika reult sejauh ini adalah antara max% 7 dan max-1 maka hasilnya akan terdistribusi secara seragam dalam kisaran itu. Jika tidak, kami menggunakan sisanya, yang acak antara 0 dan maks% 7-1, dan panggilan lain ke rand () untuk membuat nomor baru dan maks baru. Lalu kita mulai lagi.

Sunting: Mengharapkan beberapa kali untuk memanggil rand5 () adalah x dalam persamaan ini:

x =  2     * 21/25
   + 3     *  4/25 * 14/20
   + 4     *  4/25 *  6/20 * 28/30
   + 5     *  4/25 *  6/20 *  2/30 * 7/10
   + 6     *  4/25 *  6/20 *  2/30 * 3/10 * 14/15
   + (6+x) *  4/25 *  6/20 *  2/30 * 3/10 *  1/15
x = about 2.21 calls to rand5()

Algoritma:

7 dapat direpresentasikan dalam urutan 3 bit

Gunakan rand (5) untuk secara acak mengisi setiap bit dengan 0 atau 1.
Untuk mis: panggil rand (5) dan

jika hasilnya 1 atau 2, isi bit dengan 0
jika hasilnya 4 atau 5, isi bit dengan 1
jika hasilnya 3, abaikan dan lakukan lagi (penolakan)

Dengan cara ini kita dapat mengisi 3 bit secara acak dengan 0/1 dan karenanya mendapatkan angka dari 1-7.

EDIT: Ini sepertinya jawaban yang paling sederhana dan paling efisien, jadi inilah beberapa kode untuk itu:

public static int random_7() {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + random_5_output_2();
        }
    }
    return returnValue;
}

private static int random_5_output_2() {
    while (true) {
        int flip = random_5();

        if (flip < 3) {
            return 0;
        }
        else if (flip > 3) {
            return 1;
        }
    }
}

int randbit( void )
{
    while( 1 )
    {
        int r = rand5();
        if( r <= 4 ) return(r & 1);
    }
}

int randint( int nbits )
{
    int result = 0;
    while( nbits-- )
    {
        result = (result<<1) | randbit();
    }
    return( result );
}

int rand7( void )
{
    while( 1 )
    {
        int r = randint( 3 ) + 1;
        if( r <= 7 ) return( r );
    }
}

rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

Sunting: Itu tidak berhasil. Ini mati sekitar 2 bagian dalam 1000 (dengan asumsi rand5 sempurna). Ember mendapatkan:

value   Count  Error%
1       11158  -0.0035
2       11144  -0.0214
3       11144  -0.0214
4       11158  -0.0035
5       11172  +0.0144
6       11177  +0.0208
7       11172  +0.0144

Dengan beralih ke jumlah

n   Error%
10  +/- 1e-3,
12  +/- 1e-4,
14  +/- 1e-5,
16  +/- 1e-6,
...
28  +/- 3e-11

tampaknya mendapatkan urutan besarnya untuk setiap 2 ditambahkan

BTW: tabel kesalahan di atas tidak dihasilkan melalui pengambilan sampel tetapi oleh relasi perulangan berikut:

p[x,n]adalah nomor cara output=xdapat terjadi diberikan npanggilan ke rand5.

  p[1,1] ... p[5,1] = 1
  p[6,1] ... p[7,1] = 0

  p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
  p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
  p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
  p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
  p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
  p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
  p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]

int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}

Berikut ini menghasilkan distribusi seragam pada {1, 2, 3, 4, 5, 6, 7} menggunakan generator nomor acak yang menghasilkan distribusi seragam pada {1, 2, 3, 4, 5}. Kode ini berantakan, tetapi logikanya jelas.

public static int random_7(Random rg) {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + SimulateFairCoin(rg);
        }
    }
    return returnValue;
}

private static int SimulateFairCoin(Random rg) {
    while (true) {
        int flipOne = random_5_mod_2(rg);
        int flipTwo = random_5_mod_2(rg);

        if (flipOne == 0 && flipTwo == 1) {
            return 0;
        }
        else if (flipOne == 1 && flipTwo == 0) {
            return 1;
        }
    }
}

private static int random_5_mod_2(Random rg) {
    return random_5(rg) % 2;
}

private static int random_5(Random rg) {
    return rg.Next(5) + 1;
}    

int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

Berbeda dengan solusi yang dipilih, algoritma akan berjalan dalam waktu yang konstan. Namun itu membuat 2 lebih banyak panggilan ke rand5 daripada rata-rata waktu berjalan dari solusi yang dipilih.

Perhatikan bahwa generator ini tidak sempurna (angka 0 memiliki peluang 0,0064% lebih banyak daripada angka lainnya), tetapi untuk sebagian besar tujuan praktis jaminan waktu konstan mungkin lebih besar daripada ketidakakuratan ini.

Penjelasan

Solusi ini berasal dari kenyataan bahwa angka 15.624 dapat dibagi oleh 7 dan dengan demikian jika kita dapat secara acak dan seragam menghasilkan angka dari 0 hingga 15.624 dan kemudian mengambil mod 7 kita bisa mendapatkan generator rand7 yang hampir seragam. Angka dari 0 hingga 15.624 dapat dihasilkan secara seragam dengan menggulirkan rand5 6 kali dan menggunakannya untuk membentuk digit nomor basis 5 sebagai berikut:

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

Namun, properti mod 7 memungkinkan kita untuk menyederhanakan persamaan:

5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7

Begitu

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

menjadi

rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5

Teori

Angka 15.624 tidak dipilih secara acak, tetapi dapat ditemukan menggunakan teorema kecil fermat, yang menyatakan bahwa jika p adalah bilangan prima maka

a^(p-1) = 1 mod p

Jadi ini memberi kita,

(5^6)-1 = 0 mod 7

(5 ^ 6) -1 sama dengan

4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4

Ini adalah angka dalam bentuk basis 5 dan dengan demikian kita dapat melihat bahwa metode ini dapat digunakan untuk beralih dari generator nomor acak apa pun ke generator nomor acak lainnya. Meskipun bias kecil terhadap 0 selalu diperkenalkan saat menggunakan eksponen p-1.

Untuk menggeneralisasikan pendekatan ini dan agar lebih akurat kita dapat memiliki fungsi seperti ini:

def getRandomconverted(frm, to):
    s = 0
    for i in range(to):
        s += getRandomUniform(frm)*frm**i
    mx = 0
    for i in range(to):
        mx = (to-1)*frm**i 
    mx = int(mx/to)*to # maximum value till which we can take mod
    if s < mx:
        return s%to
    else:
        return getRandomconverted(frm, to)

Apakah masalah pekerjaan rumah diperbolehkan di sini?

Fungsi ini tidak kasar "basis 5" matematika untuk menghasilkan angka antara 0 dan 6.

function rnd7() {
    do {
        r1 = rnd5() - 1;
        do {
            r2=rnd5() - 1;
        } while (r2 > 1);
        result = r2 * 5 + r1;
    } while (result > 6);
    return result + 1;
}

Jika kita mempertimbangkan kendala tambahan untuk mencoba memberikan jawaban yang paling efisien yaitu yang memberikan aliran input,, Ibilangan bulat yang terdistribusi seragam mdari 1-5 output aliran O, bilangan bulat terdistribusi seragam dari 1-7 dari relatif panjang terpanjang untuk m, katakan L(m).

Cara paling sederhana untuk menganalisis ini adalah dengan memperlakukan aliran I dan Osebagai bilangan 5-ary dan 7-ary masing-masing. Ini dicapai dengan ide jawaban utama untuk mengambil aliran a1, a2, a3,... -> a1+5*a2+5^2*a3+..dan juga untuk aliran O.

Kemudian jika kita mengambil bagian dari aliran input panjang di m choose n s.t. 5^m-7^n=cmana c>0dan sekecil mungkin. Lalu ada peta yang seragam dari aliran input panjang m ke bilangan bulat dari 1ke 5^mdan peta seragam lainnya dari bilangan bulat dari 1 ke 7^naliran keluaran panjang n di mana kita mungkin harus kehilangan beberapa kasus dari aliran input ketika bilangan bulat dipetakan melebihi 7^n.

Jadi ini memberikan nilai L(m)sekitar m (log5/log7)yang kira-kira .82m.

Kesulitan dengan analisis di atas adalah persamaan 5^m-7^n=cyang tidak mudah untuk memecahkan persis dan kasus di mana nilai seragam dari 1ke 5^mmelebihi 7^ndan kami kehilangan efisiensi.

Pertanyaannya adalah seberapa dekat dengan nilai terbaik m (log5 / log7) dapat dicapai. Sebagai contoh ketika angka ini mendekati mendekati integer, dapatkah kita menemukan cara untuk mencapai jumlah integral dari nilai output?

Jika 5^m-7^n=ckemudian dari aliran input, kami secara efektif menghasilkan angka acak seragam dari 0ke (5^m)-1dan tidak menggunakan nilai lebih tinggi dari 7^n. Namun nilai-nilai ini dapat diselamatkan dan digunakan lagi. Mereka secara efektif menghasilkan urutan angka yang seragam dari 1 hingga 5^m-7^n. Jadi kita dapat mencoba menggunakan ini dan mengubahnya menjadi angka 7-ary sehingga kita dapat membuat lebih banyak nilai output.

Jika kita biarkan T7(X)menjadi panjang rata-rata dari urutan output random(1-7)bilangan bulat yang berasal dari ukuran input yang seragam X, dan dengan asumsi itu 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7.

Maka T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)karena kita memiliki panjang tanpa urutan dengan probabilitas 7 ^ n0 / 5 ^ m dengan sisa panjang 5^m-7^n0dengan probabilitas (5^m-7^n0)/5^m).

Jika kami terus mengganti, kami memperoleh:

T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m  = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m

Karenanya

L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)

Cara lain untuk mengatakan ini adalah:

If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)

Kasing terbaik adalah yang asli saya di atas di mana 5^m=7^n+s, di mana s<7.

Lalu T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)seperti sebelumnya.

Kasus terburuk adalah ketika kita hanya dapat menemukan k dan st 5 ^ m = kx7 + s.

Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)

Kasus-kasus lain ada di suatu tempat di antara. Akan menarik untuk melihat seberapa baik kita dapat melakukan untuk m yang sangat besar, yaitu seberapa baik kita bisa mendapatkan istilah kesalahan:

T7(5^m) = m (Log5/Log7)+e(m)

Tampaknya mustahil untuk mencapainya e(m) = o(1)secara umum tetapi semoga kita bisa membuktikannya e(m)=o(m).

Semuanya kemudian bertumpu pada distribusi digit 7-ary 5^muntuk berbagai nilai m.

Saya yakin ada banyak teori di luar sana yang membahas hal ini. Saya mungkin akan melihat dan melaporkan kembali di beberapa titik.

Berikut ini adalah implementasi Python implementasi jawaban Adam .

import random

def rand5():
    return random.randint(1, 5)

def rand7():
    while True:
        r = 5 * (rand5() - 1) + rand5()
        #r is now uniformly random between 1 and 25
        if (r <= 21):
            break
    #result is now uniformly random between 1 and 7
    return r % 7 + 1

Saya suka melempar algoritma yang saya lihat ke Python sehingga saya bisa bermain-main dengan mereka, saya pikir saya akan mempostingnya di sini dengan harapan itu berguna bagi seseorang di luar sana, bukan karena butuh waktu lama untuk dilempar bersama.

Mengapa tidak melakukannya secara sederhana?

int random7() {
  return random5() + (random5() % 3);
}

Peluang mendapatkan 1 dan 7 dalam solusi ini lebih rendah karena modulo, namun, jika Anda hanya menginginkan solusi yang cepat dan mudah dibaca, inilah cara yang harus ditempuh.

Dengan asumsi bahwa rand (n) di sini berarti "bilangan bulat acak dalam distribusi seragam dari 0 hingga n-1 ", inilah contoh kode menggunakan randint Python, yang memiliki efek itu. Hanya menggunakan randint (5) , dan konstanta, untuk menghasilkan efek randint (7) . Sebenarnya agak konyol

from random import randint
sum = 7
while sum >= 7:
    first = randint(0,5)   
    toadd = 9999
    while toadd>1:
        toadd = randint(0,5)
    if toadd:
        sum = first+5
    else:
        sum = first

assert 7>sum>=0 
print sum

Premis di balik jawaban yang benar Adam Rosenfield adalah:

• x = 5 ^ n (dalam kasusnya: n = 2)
• memanipulasi panggilan n rand5 untuk mendapatkan nomor y dalam jangkauan [1, x]
• z = ((int) (x / 7)) * 7
• jika y> z, coba lagi. lain kembalikan y% 7 +1

Ketika n sama dengan 2, Anda memiliki 4 kemungkinan membuang: y = {22, 23, 24, 25}. Jika Anda menggunakan n sama dengan 6, Anda hanya memiliki 1 membuang: y = {15625}.

5 ^ 6 = 15625
7 * 2232 = 15624

Anda menelepon rand5 lebih banyak. Namun, Anda memiliki peluang jauh lebih rendah untuk mendapatkan nilai throw-away (atau infinite loop). Jika ada cara untuk tidak mendapatkan nilai membuang yang mungkin untuk y, saya belum menemukannya.

Inilah jawaban saya:

static struct rand_buffer {
  unsigned v, count;
} buf2, buf3;

void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
  buf->v = buf->v * n + v;
  ++buf->count;
}

#define PUSH(n, v)  push (&buf##n, n, v)

int rand16 (void)
{
  int v = buf2.v & 0xf;
  buf2.v >>= 4;
  buf2.count -= 4;
  return v;
}

int rand9 (void)
{
  int v = buf3.v % 9;
  buf3.v /= 9;
  buf3.count -= 2;
  return v;
}

int rand7 (void)
{
  if (buf3.count >= 2) {
    int v = rand9 ();

    if (v < 7)
      return v % 7 + 1;

    PUSH (2, v - 7);
  }

  for (;;) {
    if (buf2.count >= 4) {
      int v = rand16 ();

      if (v < 14) {
        PUSH (2, v / 7);
        return v % 7 + 1;
      }

      PUSH (2, v - 14);
    }

    // Get a number between 0 & 25
    int v = 5 * (rand5 () - 1) + rand5 () - 1;

    if (v < 21) {
      PUSH (3, v / 7);
      return v % 7 + 1;
    }

    v -= 21;
    PUSH (2, v & 1);
    PUSH (2, v >> 1);
  }
}

Ini sedikit lebih rumit daripada yang lain, tapi saya percaya ini meminimalkan panggilan ke rand5. Seperti dengan solusi lain, ada kemungkinan kecil bahwa itu bisa berulang untuk waktu yang lama.

Sederhana dan efisien:

int rand7 ( void )
{
    return 4; // this number has been calculated using
              // rand5() and is in the range 1..7
}

(Terinspirasi oleh Apa kartun "programmer" favorit Anda? ).

Selama tidak ada tujuh kemungkinan yang tersisa untuk dipilih, gambarkan nomor acak lain, yang mengalikan jumlah kemungkinan dengan lima. Dalam Perl:

$num = 0;
$possibilities = 1;

sub rand7
{
  while( $possibilities < 7 )
  {
    $num = $num * 5 + int(rand(5));
    $possibilities *= 5;
  }
  my $result = $num % 7;
  $num = int( $num / 7 );
  $possibilities /= 7;
  return $result;
}

Saya tidak suka rentang mulai dari 1, jadi saya akan mulai dari 0 :-)

unsigned rand5()
{
    return rand() % 5;
}

unsigned rand7()
{
    int r;

    do
    {
        r =         rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
    } while (r > 15623);

    return r / 2232;
}

Di sana Anda pergi, distribusi seragam dan nol panggilan Rand5.

def rand7:
    seed += 1
    if seed >= 7:
        seed = 0
    yield seed

Perlu mengatur benih sebelumnya.

Saya tahu itu telah dijawab, tetapi apakah ini tampaknya berhasil, tetapi saya tidak dapat memberi tahu Anda jika ada bias. 'Pengujian' saya menunjukkan itu, setidaknya, masuk akal.

Mungkin Adam Rosenfield akan berbaik hati berkomentar?

Ide saya (naif?) Adalah ini:

Akumulasi rand5 sampai ada bit acak yang cukup untuk membuat rand7. Ini memakan waktu paling banyak 2 rand5. Untuk mendapatkan nomor rand7 saya menggunakan nilai akumulasi mod 7.

Untuk menghindari overloading akumulator, dan karena akumulator adalah mod 7 maka saya mengambil mod 7 dari akumulator:

(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7

Fungsi rand7 () mengikuti:

(Saya membiarkan rentang rand5 menjadi 0-4 dan rand7 juga 0-6.)

int rand7(){
  static int    a=0;
  static int    e=0;
  int       r;
  a = a * 5 + rand5();
  e = e + 5;        // added 5/7ths of a rand7 number
  if ( e<7 ){
    a = a * 5 + rand5();
    e = e + 5;  // another 5/7ths
  }
  r = a % 7;
  e = e - 7;        // removed a rand7 number
  a = a % 7;
  return r;
}

Sunting: Hasil tambahan untuk 100 juta percobaan.

Fungsi 'Real' rand mod 5 atau 7

rand5: avg = 1.999802 0: 20003944 1: 19999889 2: 20003690 3: 19996938 4: 19995539 rand7: avg = 3.000111 0: 14282851 1: 14282851 1: 14282879 2: 14284554 3: 14288554 4: 14292388 5: 142292388 5: 14229853836 6: 14280046

Rand7 saya

Rata-rata terlihat ok dan distribusi angka juga terlihat ok.

Randand: rata-rata = 3,000080 0: 14288793 1: 14280135 2: 14287848 3: 14285277 4: 14286341 5: 14278663 6: 14292943

Ada beberapa algoritma elegan yang dikutip di atas, tetapi inilah salah satu cara untuk mendekatinya, meskipun mungkin bundaran. Saya mengasumsikan nilai yang dihasilkan dari 0.

R2 = generator angka acak yang memberikan nilai kurang dari 2 (ruang sampel = {0, 1})
R8 = generator angka acak yang memberikan nilai kurang dari 8 (ruang sampel = {0, 1, 2, 3, 4, 5, 5, 6, 7 })

Untuk menghasilkan R8 dari R2, Anda akan menjalankan R2 tiga kali, dan menggunakan hasil gabungan dari semua 3 berjalan sebagai angka biner dengan 3 digit. Berikut adalah rentang nilai ketika R2 dijalankan tiga kali:

0 0 0 -> 0
.
.
1 1 1 -> 7

Sekarang untuk menghasilkan R7 dari R8, kita cukup menjalankan R7 lagi jika mengembalikan 7:

int R7() {
  do {
    x = R8();
  } while (x > 6)
  return x;
}

Solusi bundaran adalah untuk menghasilkan R2 dari R5 (sama seperti kita menghasilkan R7 dari R8), kemudian R8 dari R2 dan kemudian R7 dari R8.

Berikut adalah solusi yang sepenuhnya sesuai dengan bilangan bulat dan berada dalam kisaran 4% dari yang optimal (yaitu menggunakan 1.26 angka acak dalam {0..4} untuk setiap orang di {0..6}). Kode dalam Scala, tetapi matematika harus cukup jelas dalam bahasa apa pun: Anda memanfaatkan fakta bahwa 7 ^ 9 + 7 ^ 8 sangat dekat dengan 5 ^ 11. Jadi Anda memilih angka 11 digit pada basis 5, dan kemudian menafsirkannya sebagai angka 9 digit pada basis 7 jika berada dalam kisaran (memberikan 9 basis 7 angka), atau sebagai angka 8 digit jika melebihi angka 9 digit, dll. .:

abstract class RNG {
  def apply(): Int
}

class Random5 extends RNG {
  val rng = new scala.util.Random
  var count = 0
  def apply() = { count += 1 ; rng.nextInt(5) }
}

class FiveSevener(five: RNG) {
  val sevens = new Array[Int](9)
  var nsevens = 0
  val to9 = 40353607;
  val to8 = 5764801;
  val to7 = 823543;
  def loadSevens(value: Int, count: Int) {
    nsevens = 0;
    var remaining = value;
    while (nsevens < count) {
      sevens(nsevens) = remaining % 7
      remaining /= 7
      nsevens += 1
    }
  }
  def loadSevens {
    var fivepow11 = 0;
    var i=0
    while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
    if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
    fivepow11 -= to9
    if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
    fivepow11 -= to8
    if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
    else loadSevens
  }
  def apply() = {
    if (nsevens==0) loadSevens
    nsevens -= 1
    sevens(nsevens)
  }
}

Jika Anda menempelkan tes ke interpreter (REPL sebenarnya), Anda mendapatkan:

scala> val five = new Random5
five: Random5 = Random5@e9c592

scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423

scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)

scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000

scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)

scala> five.count
res1: Int = 125902876

Distribusinya bagus dan rata (dalam kisaran 10k 1/7 dari 10 ^ 8 di setiap nampan, seperti yang diharapkan dari distribusi kira-kira Gaussian).

Dengan menggunakan total bergulir , Anda dapat keduanya

• mempertahankan distribusi yang sama; dan
• tidak harus mengorbankan elemen apa pun dalam urutan acak.

Kedua masalah ini adalah masalah dengan rand(5)+rand(5)...solusi tipe sederhana . Kode Python berikut ini menunjukkan cara mengimplementasikannya (sebagian besar membuktikan distribusi).

import random
x = []
for i in range (0,7):
    x.append (0)
t = 0
tt = 0
for i in range (0,700000):
    ########################################
    #####            qq.py             #####
    r = int (random.random () * 5)
    t = (t + r) % 7
    ########################################
    #####       qq_notsogood.py        #####
    #r = 20
    #while r > 6:
        #r =     int (random.random () * 5)
        #r = r + int (random.random () * 5)
    #t = r
    ########################################
    x[t] = x[t] + 1
    tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
    print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
    if x[i] < low:
        low = x[i]
    if x[i] > high:
        high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)

Dan output ini menunjukkan hasilnya:

pax$ python qq.py
0:   99908 14.27257
1:  100029 14.28986
2:  100327 14.33243
3:  100395 14.34214
4:   99104 14.15771
5:   99829 14.26129
6:  100408 14.34400
Variation = 1304 (0.18629%)

pax$ python qq.py
0:   99547 14.22100
1:  100229 14.31843
2:  100078 14.29686
3:   99451 14.20729
4:  100284 14.32629
5:  100038 14.29114
6:  100373 14.33900
Variation = 922 (0.13171%)

pax$ python qq.py
0:  100481 14.35443
1:   99188 14.16971
2:  100284 14.32629
3:  100222 14.31743
4:   99960 14.28000
5:   99426 14.20371
6:  100439 14.34843
Variation = 1293 (0.18471%)

Sederhana rand(5)+rand(5), mengabaikan kasus-kasus di mana ini mengembalikan lebih dari 6 memiliki variasi khas 18%, 100 kali lipat dari metode yang ditunjukkan di atas:

pax$ python qq_notsogood.py
0:   31756 4.53657
1:   63304 9.04343
2:   95507 13.64386
3:  127825 18.26071
4:  158851 22.69300
5:  127567 18.22386
6:   95190 13.59857
Variation = 127095 (18.15643%)

pax$ python qq_notsogood.py
0:   31792 4.54171
1:   63637 9.09100
2:   95641 13.66300
3:  127627 18.23243
4:  158751 22.67871
5:  126782 18.11171
6:   95770 13.68143
Variation = 126959 (18.13700%)

pax$ python qq_notsogood.py
0:   31955 4.56500
1:   63485 9.06929
2:   94849 13.54986
3:  127737 18.24814
4:  159687 22.81243
5:  127391 18.19871
6:   94896 13.55657
Variation = 127732 (18.24743%)

Dan, atas saran Nixuz, saya sudah membersihkan skrip sehingga Anda bisa mengekstrak dan menggunakan rand7...barang - barang:

import random

# rand5() returns 0 through 4 inclusive.

def rand5():
    return int (random.random () * 5)

# rand7() generator returns 0 through 6 inclusive (using rand5()).

def rand7():
    rand7ret = 0
    while True:
        rand7ret = (rand7ret + rand5()) % 7
        yield rand7ret

# Number of test runs.

count = 700000

# Work out distribution.

distrib = [0,0,0,0,0,0,0]
rgen =rand7()
for i in range (0,count):
    r = rgen.next()
    distrib[r] = distrib[r] + 1

# Print distributions and calculate variation.

high = distrib[0]
low = distrib[0]
for i in range (0,7):
    print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count)
    if distrib[i] < low:
        low = distrib[i]
    if distrib[i] > high:
        high = distrib[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count)

Jawaban ini lebih merupakan eksperimen dalam memperoleh entropi sebanyak mungkin dari fungsi Rand5. Oleh karena itu agak tidak jelas dan hampir pasti jauh lebih lambat daripada implementasi lainnya.

Dengan asumsi distribusi seragam dari 0-4 dan menghasilkan distribusi seragam dari 0-6:

public class SevenFromFive
{
  public SevenFromFive()
  {
    // this outputs a uniform ditribution but for some reason including it 
    // screws up the output distribution
    // open question Why?
    this.fifth = new ProbabilityCondensor(5, b => {});
    this.eigth = new ProbabilityCondensor(8, AddEntropy);
  } 

  private static Random r = new Random();
  private static uint Rand5()
  {
    return (uint)r.Next(0,5);
  }

  private class ProbabilityCondensor
  {
    private readonly int samples;
    private int counter;
    private int store;
    private readonly Action<bool> output;

    public ProbabilityCondensor(int chanceOfTrueReciprocal,
      Action<bool> output)
    {
      this.output = output;
      this.samples = chanceOfTrueReciprocal - 1;  
    }

    public void Add(bool bit)
    {
      this.counter++;
      if (bit)
        this.store++;   
      if (counter == samples)
      {
        bool? e;
        if (store == 0)
          e = false;
        else if (store == 1)
          e = true;
        else
          e = null;// discard for now       
        counter = 0;
        store = 0;
        if (e.HasValue)
          output(e.Value);
      }
    }
  }

  ulong buffer = 0;
  const ulong Mask = 7UL;
  int bitsAvail = 0;
  private readonly ProbabilityCondensor fifth;
  private readonly ProbabilityCondensor eigth;

  private void AddEntropy(bool bit)
  {
    buffer <<= 1;
    if (bit)
      buffer |= 1;      
    bitsAvail++;
  }

  private void AddTwoBitsEntropy(uint u)
  {
    buffer <<= 2;
    buffer |= (u & 3UL);    
    bitsAvail += 2;
  }

  public uint Rand7()
  {
    uint selection;   
    do
    {
      while (bitsAvail < 3)
      {
        var x = Rand5();
        if (x < 4)
        {
          // put the two low order bits straight in
          AddTwoBitsEntropy(x);
          fifth.Add(false);
        }
        else
        { 
          fifth.Add(true);
        }
      }
      // read 3 bits
      selection = (uint)((buffer & Mask));
      bitsAvail -= 3;     
      buffer >>= 3;
      if (selection == 7)
        eigth.Add(true);
      else
        eigth.Add(false);
    }
    while (selection == 7);   
    return selection;
  }
}

Jumlah bit yang ditambahkan ke buffer per panggilan ke Rand5 saat ini 4/5 * 2 jadi 1,6. Jika nilai probabilitas 1/5 disertakan yang meningkat sebesar 0,05 maka 1,65 tetapi lihat komentar dalam kode di mana saya harus menonaktifkan ini.

Bit dikonsumsi melalui panggilan ke Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...
Ini 3 + 3/8 + 3/64 + 3/512 ... jadi sekitar 3,42

Dengan mengekstraksi informasi dari tujuh, saya mendapatkan kembali 1/8 * 1/7 bit per panggilan jadi sekitar 0,018

Ini memberikan konsumsi bersih 3,4 bit per panggilan yang berarti rasionya adalah 2,125 panggilan ke Rand5 untuk setiap Rand7. Yang optimal harus 2.1.

Saya akan membayangkan pendekatan ini secara signifikan lebih lambat daripada banyak yang lain di sini kecuali biaya panggilan ke Rand5 sangat mahal (katakanlah memanggil beberapa sumber eksternal entropi).

dalam php

function rand1to7() {
    do {
        $output_value = 0;
        for ($i = 0; $i < 28; $i++) {
            $output_value += rand1to5();
        }
    while ($output_value != 140);
    $output_value -= 12;
    return floor($output_value / 16);
}

loop untuk menghasilkan angka acak antara 16 dan 127, membaginya dengan enam belas untuk membuat float antara 1 dan 7.9375, kemudian membulatkan ke bawah untuk mendapatkan int antara 1 dan 7. jika saya tidak salah, ada peluang 16/112 untuk mendapatkan salah satu dari 7 hasil.

extern int r5();

int r7() {
    return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}

Saya pikir saya punya empat jawaban, dua memberikan solusi tepat seperti yang dari @Adam Rosenfield tetapi tanpa masalah loop tak terbatas, dan dua lainnya dengan solusi yang hampir sempurna tetapi implementasi lebih cepat daripada yang pertama.

Solusi tepat terbaik membutuhkan 7 panggilan rand5, tetapi mari kita lanjutkan untuk memahami.

Metode 1 - Tepat

Kekuatan jawaban Adam adalah bahwa ia memberikan distribusi seragam yang sempurna, dan ada probabilitas yang sangat tinggi (21/25) bahwa hanya dua panggilan ke rand5 () yang akan dibutuhkan. Namun, kasus terburuk adalah infinite loop.

Solusi pertama di bawah ini juga memberikan distribusi seragam yang sempurna, tetapi membutuhkan total 42 panggilan ke rand5. Tidak ada loop tanpa batas.

Berikut ini adalah implementasi R:

rand5 <- function() sample(1:5,1)

rand7 <- function()  (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1

Bagi orang yang tidak terbiasa dengan R, ini adalah versi yang disederhanakan:

rand7 = function(){
  r = 0 
  for(i in 0:6){
    r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
  }
  return r %% 7 + 1
}

Distribusi rand5akan dipertahankan. Jika kita menghitungnya, masing-masing dari 7 iterasi loop memiliki 5 ^ 6 kombinasi yang memungkinkan, sehingga jumlah total kombinasi yang mungkin adalah (7 * 5^6) %% 7 = 0. Dengan demikian kita dapat membagi angka acak yang dihasilkan dalam kelompok yang sama dari 7. Lihat metode dua untuk diskusi lebih lanjut tentang ini.

Berikut ini semua kemungkinan kombinasi:

table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)

    1     2     3     4     5     6     7 
15625 15625 15625 15625 15625 15625 15625 

Saya pikir ini sangat jelas untuk menunjukkan bahwa metode Adam akan berjalan jauh lebih cepat. Probabilitas bahwa ada 42 atau lebih panggilan ke rand5dalam solusi Adam sangat kecil ( (4/25)^21 ~ 10^(-17)).

Metode 2 - Tidak Tepat

Sekarang metode kedua, yang hampir seragam, tetapi membutuhkan 6 panggilan ke rand5:

rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

Ini adalah versi yang disederhanakan:

rand7 = function(){
  r = 0 
  for(i in 1:6){
    r = r + i*rand5()
  }
  return r %% 7 + 1
}

Ini pada dasarnya adalah satu iterasi dari metode 1. Jika kami menghasilkan semua kombinasi yang mungkin, berikut adalah jumlah yang dihasilkan:

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)

   1    2    3    4    5    6    7 
2233 2232 2232 2232 2232 2232 2232

Satu nomor akan muncul sekali lagi dalam 5^6 = 15625uji coba.

Sekarang, dalam Metode 1, dengan menambahkan 1 hingga 6, kami memindahkan angka 2233 ke setiap titik berurutan. Dengan demikian jumlah total kombinasi akan cocok. Ini berhasil karena 5 ^ 6 %% 7 = 1, dan kemudian kita melakukan 7 variasi yang sesuai, jadi (7 * 5 ^ 6 %% 7 = 0).

Metode 3 - Tepat

Jika argumen metode 1 dan 2 dipahami, metode 3 mengikuti, dan hanya membutuhkan 7 panggilan ke rand5. Pada titik ini, saya merasa ini adalah jumlah minimum panggilan yang diperlukan untuk solusi yang tepat.

Berikut ini adalah implementasi R:

rand5 <- function() sample(1:5,1)

rand7 <- function()  (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1

Bagi orang yang tidak terbiasa dengan R, ini adalah versi yang disederhanakan:

rand7 = function(){
  r = 0 
  for(i in 1:7){
    r = r + i * rand5()
  }
  return r %% 7 + 1
}

Distribusi rand5akan dipertahankan. Jika kita menghitungnya, masing-masing dari 7 iterasi loop memiliki 5 hasil yang mungkin, dengan demikian jumlah total kombinasi yang mungkin adalah (7 * 5) %% 7 = 0. Dengan demikian kita dapat membagi angka acak yang dihasilkan dalam kelompok yang sama dari 7. Lihat metode satu dan dua untuk diskusi lebih lanjut tentang ini.

Berikut ini semua kemungkinan kombinasi:

table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)

1 2 3 4 5 6 7  
5 5 5 5 5 5 5 

Saya pikir ini sangat jelas untuk menunjukkan bahwa metode Adam masih akan berjalan lebih cepat. Probabilitas bahwa ada 7 panggilan atau lebih rand5dalam solusi Adam masih kecil ( (4/25)^3 ~ 0.004).

Metode 4 - Tidak Tepat

Ini adalah variasi kecil dari metode kedua. Hampir seragam, tetapi membutuhkan 7 panggilan ke rand5, itu adalah satu tambahan untuk metode 2:

rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

Ini adalah versi yang disederhanakan:

rand7 = function(){
  r = 0 
  for(i in 1:6){
    r = r + i*rand5()
  }
  return (r+rand5()) %% 7 + 1
}

Jika kami menghasilkan semua kombinasi yang mungkin, berikut ini penghitungannya:

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)

    1     2     3     4     5     6     7 
11160 11161 11161 11161 11161 11161 11160

Dua angka akan muncul sekali kurang dalam 5^7 = 78125uji coba. Untuk sebagian besar tujuan, saya bisa hidup dengan itu.

Fungsi yang Anda butuhkan adalah rand1_7 () , saya menulis rand1_5 () sehingga Anda dapat mengujinya dan memplotnya.

import numpy
def rand1_5():
    return numpy.random.randint(5)+1

def rand1_7():
    q = 0
    for i in xrange(7):  q+= rand1_5()
    return q%7 + 1