Fungsi mayoritas adalah fungsi boolean yang mengambil tiga input boolean dan mengembalikan yang paling umum. Misalnya jika maj(x,y,z)
fungsi mayoritas dan T
menunjukkan benar dan F
menunjukkan salah maka:
maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F
Pertanyaan ini menyangkut penulisan fungsi boolean sebagai komposisi fungsi mayoritas. Contoh komposisi mayoritas fungsi 5-ary adalah (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5))
. Fungsi ini mengembalikan output berikut pada vektor input sampel ini:
(T,T,F,F,F) => maj(T,T,maj(F,F,F)) = maj(T,T,F) = T
(T,F,T,T,F) => maj(T,F,maj(T,T,F)) = maj(T,F,T) = T
(T,F,T,F,F) => maj(T,F,maj(T,F,F)) = maj(T,F,F) = F
(F,F,F,T,T) => maj(F,F,maj(F,T,T)) = maj(F,F,T) = F
Tugas
Tulis program yang memasukkan bilangan bulat positif dan daftar panjang n vektor boolean dan output pohon gerbang mayoritas yang mengembalikan true pada semua vektor yang diberikan jika memungkinkan. Fungsi dapat mengembalikan benar atau salah pada vektor yang tidak ada dalam daftar kendala.
Daftar vektor dapat dimasukkan dalam format apa pun yang Anda suka. Jika Anda suka, alih-alih memasukkan vektor, Anda dapat memasukkan daftar posisi sebenarnya dalam vektor. Jadi misalnya,
[TTF,TFT,FTT]
atau[[T,T,F],[T,F,T],[F,T,T]]
atau[[1,2],[1,3],[2,3]]
(daftar posisi sebenarnya) semuanya baik-baik saja.Output dapat berupa format pohon apa pun yang valid. Misalnya,
maj(maj(x1,x2,x3),x4,x5)
berfungsi. Anda mungkin ingin menggunakan angka tunggal sebagai pengganti variabel, seperti pada[[1,2,3],4,5]
. Reverse polish123m45m
juga oke, misalnya.Jika tidak ada fungsi yang berfungsi, program Anda harus menghasilkan kesalahan atau menampilkan nilai falsey.
Jika ada beberapa fungsi yang berfungsi, program Anda dapat mengembalikannya. Fungsi tidak perlu disederhanakan. Misalnya,
maj(x1,x1,x2)
ataux1
setara.
Mencetak gol
Ini adalah kode golf: Solusi terpendek dalam byte yang menang.
Kasus uji:
Perhatikan bahwa ada banyak kemungkinan keluaran untuk masing-masing kasus ini, jadi Anda harus menulis skrip checker yang mengubah output Anda menjadi fungsi dan memeriksa apakah fungsi Anda mengembalikan true pada masing-masing vektor input yang ditentukan.
Input: 3, [TFF]
Output: 1 or [1,1,2] or [1,[1,2,2],[1,1,3]] or other equivalent
Input: 3, [TFF,FTF]
Output: Falsey or error (it's not possible)
Input: 3, [TTF,TFT]
Output: [1,2,3] or 1 or other equivalent
Input: 3, [TTF,TFT,FTT]
Output: [1,2,3] or [1,3,2] or other equivalent
Input: 4, [TTFF,TFTF,FFTT]
Output: Falsey or error
Input: 4, [TTTF,TTFT,TFTT,FTTT]
Output: [1, 2, 3] or [2,3,4], or many other options
Input: 5, [TTTFF,FTTFT,TFFFT]
Output: [1,[1,[1,2,5],[2,4,5]],3] or many other options
Input: 6, [TTTFFF,FTFTTF,TFFTFT]
Output: [1, 2, 4] or [1, [1, 2, 4], [2, 3, 4]] or others
Input: 5, [TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT]
Output: [[1, [1, 3, 5], 4], [1, 2, [2, 4, 5]], [2, 3, [3, 4, 5]]] or others
Input: 7, [TTTTFFF,TTTFTFF,TTTFFTF,TTTFFFT,TTFTTFF,TTFTFTF,TTFTFFT,TTFFTTF,TTFFTFT,TTFFFTT,TFTTTFF,TFTTFTF,TFTTFFT,TFTFTTF,TFTFTFT,TFTFFTT,TFFTTTF,TFFTTFT,TFFTFTT,TFFFTTT,FTTTTFF,FTTTFTF,FTTTFFT,FTTFTTF,FTTFTFT,FTTFFTT,FTFTTTF,FTFTTFT,FTFTFTT,FTFFTTT,FFTTTTF,FFTTTFT,FFTTFTT,FFTFTTT,FFFTTTT]
Output: [[[1, [1, [1, 4, 7], 6], 5], [1, [1, 3, [3, 6, 7]], [3, 5, [5, 6, 7]]], [3, 4, [4, [4, 5, 7], 6]]], [[1, [1, [1, 4, 7], 6], 5], [1, 2, [2, [2, 5, 7], 6]], [2, [2, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]], [[2, [2, [2, 4, 7], 6], 5], [2, 3, [3, [3, 5, 7], 6]], [3, [3, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]]]
Jawaban:
JavaScript (ES6), 260 byte
Mengambil input sebagai array array boolean. Mengembalikan pohon gerbang mayoritas 1-diindeks atau melempar kesalahan rekursi (1) jika tidak ada solusi.
Fungsi utama f () secara rekursif berusaha menemukan solusi dengan memanggil pemecah F () dan menambah level bersarang maksimum m pada setiap iterasi.
(1) setelah waktu yang lama , dan mengasumsikan memori tak terbatas
Demo
Tampilkan cuplikan kode
Contoh
Di bawah ini adalah tabel validasi dari solusi yang ditemukan untuk kasus uji terakhir dari demo.
sumber
Mathematica, 121 byte
Fungsi anonim yang mengambil argumen kedua sebagai daftar daftar posisi sebenarnya dalam vektor boolean.
Diformat sedikit lebih bagus:
Kalau tidak, gantikanf1=f(x1,x1,x2,x3,…,xn−1) , f2=f(x1,x2,x2,x3,…,xn−1) , dan f3=f(x1,x2,x1,x3,…,xn−1)) , secara rekursif menyelesaikan masing-masing, lalu setf=maj(f1(x1,x3,x4,…,xn),f2(x1,x2,x4,…,xn),f2(x2,x3,x4,…,xn)) .
Penjelasan:
Ini adalah algoritma rekursif yang mengurangi masalah menemukan solusi dari masalahn variabel menjadi menemukan tiga solusi untuk masalah n−1 variabel. Pengamatan kunci yang membuat pekerjaan ini adalah bahwa untuk f salah satu fungsi yang kita cari kita miliki:
f(x1,…,xn)=maj(f(x1,x1,x3,x4,…,xn),f(x1,x2,x2,…),f(x3,x2,x3,…))
Di posisi pertama, kami menggantix2 dengan x1 , di posisi kedua x3 dengan x2 dan di posisi ketiga x1 dengan x3 .
Mengapa ini benar? Nah fungsi mayoritas memenuhi dua properti:
Ternyata fungsi monotonik pelengkap persis kelas fungsi yang dapat dibangun dari gerbang mayoritas.
sumber