Pohon biner
Pohon biner adalah pohon dengan simpul dari tiga jenis:
- terminal node, yang tidak memiliki anak
- node unary, yang masing-masing memiliki satu anak
- node biner, yang masing-masing memiliki dua anak
Kita dapat mewakili mereka dengan tata bahasa berikut, diberikan dalam BNF (bentuk Backus-Naur):
<e> ::=
<terminal>
| <unary>
| <binary>
<terminal> ::=
"0"
<unary> ::=
"(1" <e> ")"
<binary> ::=
"(2" <e> " " <e> ")"
Dalam tata bahasa ini, node diberikan dalam preorder dan setiap node diwakili oleh digit yang merupakan jumlah anak yang dimilikinya.
Nomor Motzkin
Angka Motzkin ( OEIS ) ( Wikipedia ) memiliki banyak interpretasi, tetapi satu interpretasi adalah bahwa angka n
Motzkin adalah jumlah pohon biner yang berbeda dengan n
node. Tabel nomor Motzkin dimulai
N Motzkin number M(N)
1 1
2 1
3 2
4 4
5 9
6 21
7 51
8 127
...
misalnya M(5)
adalah 9, dan sembilan pohon biner yang berbeda dengan 5 node
1 (1 (1 (1 (1 0))))
2 (1 (1 (2 0 0)))
3 (1 (2 0 (1 0)))
4 (1 (2 (1 0) 0))
5 (2 0 (1 (1 0)))
6 (2 0 (2 0 0))
7 (2 (1 0) (1 0))
8 (2 (1 (1 0)) 0)
9 (2 (2 0 0) 0)
Tugas
Ambil bilangan bulat positif tunggal n
sebagai input dan output semua pohon biner yang berbeda dengan n
node.
Contoh untuk n
dari 1 hingga 5 dengan tanda kurung dimasukkan untuk keterbacaan
0
(1 0)
(1 (1 0))
(2 0 0)
(1 (1 (1 0)))
(1 (2 0 0))
(2 0 (1 0))
(2 (1 0) 0)
(1 (1 (1 (1 0))))
(1 (1 (2 0 0)))
(1 (2 0 (1 0)))
(1 (2 (1 0) 0))
(2 0 (1 (1 0)))
(2 0 (2 0 0))
(2 (1 0) (1 0))
(2 (1 (1 0)) 0)
(2 (2 0 0) 0)
Memasukkan
Input akan menjadi satu bilangan bulat positif.
Keluaran
Outputnya harus berupa representasi yang jelas dari pohon biner yang berbeda dengan banyak node. Tidaklah wajib untuk menggunakan string persis yang diberikan oleh tata bahasa BNF di atas: cukup bahwa sintaks yang digunakan memberikan representasi pohon yang jelas. Misalnya, Anda dapat menggunakan []
alih-alih ()
, tanda kurung tambahan [[]]
alih-alih []
, tanda kurung luar ada atau tidak ada, koma ekstra atau tanpa koma, ruang ekstra, tanda kurung atau tanpa tanda kurung, dll.
Semua ini setara:
(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55
(- (+ (- 1) 1))
-+-11
Juga variasi yang ditujukan oleh @xnor dalam komentar. Karena ada cara untuk menerjemahkan ini ke format yang dapat dipahami, maka itu dapat diterima.
[[[]][]] is (2 (1 0) 0)
Untuk membuat ini lebih mudah untuk memahami mengkonversi beberapa []
untuk ()
suka begitu
[([])()]
Sekarang jika Anda mulai dengan
[]
kemudian masukkan biner yang membutuhkan dua ekspresi yang Anda dapatkan
[()()] which is 2
dan kemudian untuk yang pertama () masukkan unary yang membutuhkan satu ekspresi yang Anda dapatkan
[([])()] which is 21
tetapi karena []
atau ()
tanpa tanda kurung bagian dalam dapat mewakili 0 yang tidak memerlukan ekspresi lagi Anda dapat menafsirkannya sebagai
2100
Perhatikan bahwa jawaban harus bekerja secara teoritis dengan memori tak terbatas, tetapi jelas akan kehabisan memori untuk input terbatas yang bergantung pada implementasi.
Variasi keluaran
BNF xnor Christian Ben
b(t, b(t, t)) [{}{{}{}}] (0(00)) (1, -1, 1, -1)
b(t, u(u(t))) [{}{(())}] (0((0))) (1, -1, 0, 0)
b(u(t), u(t)) [{()}{()}] ((0)(0)) (1, 0, -1, 0)
b(b(t, t), t) [{{}{}}{}] ((00)0) (1, 1, -1, -1)
b(u(u(t)), t) [{(())}{}] (((0))0) (1, 0, 0, -1)
u(b(t, u(t))) [({}{()})] ((0(0))) (0, 1, -1, 0)
u(b(u(t), t)) [({()}{})] (((0)0)) (0, 1, 0, -1)
u(u(b(t, t))) [(({}{}))] (((00))) (0, 0, 1, -1)
u(u(u(u(t)))) [(((())))] ((((0)))) (0, 0, 0, 0)
Tempat yang memungkinkan untuk memeriksa duplikat pohon
Satu tempat untuk memeriksa duplikat adalah dengan M (5).
Pohon yang satu ini dihasilkan dua kali untuk M (5) dari pohon M (4)
(2 (1 0) (1 0))
yang pertama dengan menambahkan cabang unary ke
(2 (1 0) 0)
dan kedua dengan menambahkan cabang unary ke
(2 0 (1 0))
Memahami BNF
BNF terdiri dari aturan sederhana:
<symbol> ::= expression
di mana di sebelah kiri adalah nama simbol yang dikelilingi oleh <>
.
Di sebelah kanan adalah ekspresi untuk membangun simbol. Beberapa aturan menggunakan aturan lain dalam konstruksi, misalnya
<e> ::= <terminal>
e
bisa menjadi terminal
dan beberapa aturan memiliki karakter yang digunakan dalam membangun simbol, misalnya
<terminal> ::= "0"
terminal
hanya karakter nol.
Beberapa aturan memiliki beberapa cara untuk membuatnya, misalnya
<e> ::=
<terminal>
| <unary>
| <binary>
An e
dapat berupa a <terminal>
atau a <unary>
atau a <binary>
.
Dan beberapa aturan adalah urutan bagian, misalnya
<unary> ::= "(1" <e> ")"
A unary
adalah karakter yang (1
diikuti oleh apa yang dapat dibangun untuk e
diikuti oleh )
.
Anda selalu mulai dengan aturan awal, yang untuk ini <e>
.
Beberapa contoh sederhana:
Urutan paling sederhana adalah adil 0
. Jadi kita mulai dengan aturan awal <e>
dan melihat bahwa ada tiga pilihan:
<terminal>
| <unary>
| <binary>
jadi ambil yang pertama <terminal>
. Sekarang terminal tidak memiliki pilihan dan sedang 0
. Jadi ganti <terminal>
dengan 0
di <e>
aturan dan Anda selesai.
Lalu yang berikutnya adalah (1 0)
. Mulai dengan <e>
dan gunakan aturan <unary>
yang ada
"(1" <e> ")"
Sekarang ini perlu <e>
jadi kami kembali ke <e>
dan memilih salah satu dari tiga, kali ini memilih, <terminal>
yang memberi 0
. Mengganti 0
menjadi (1 <e> )
memberi (1 0)
, dan ini diganti menjadi <unary>
apa <e>
adanya (1 0)
.
sumber
Jawaban:
Haskell, 68 byte
Terminal node diwakili oleh
0
, node unary dan binary oleh(e)
resp.(ee)
, jadi dua pohon tiga simpul diberikan sebagai(00)
dan((0))
.Contoh:
sumber
CJam (37 byte)
Demo online . Perhatikan bahwa ini sangat tidak efisien, dan Anda mungkin tidak ingin mencoba menghitung input
5
online.Diseksi untuk diikuti.
sumber
Pyth (
242119 bytes)Ini didasarkan pada solusi Python 3 saya .
Ini pertama kalinya saya menggunakan Pyth jadi ini kemungkinan masih golf.
Contoh , output ketika input adalah
4
:1 mewakili simpul biner, 0 mewakili simpul unary, dan -1 mewakili simpul terminal. Ada simpul terminal tersirat di ujung setiap pohon.
Penjelasan :
sumber
brainfuck, 107 byte
Diformat:
Cobalah online
Input diambil sebagai byte , dan hierarki
12100
direpresentasikan sebagai\x01\x02\x03\x02
: untuk mengkonversi kembali, menerjemahkantr/\x01\x02\x03/012/
, membalikkan string, dan menambahkan final0
. Pohon dipisahkan oleh\xfe
. (Keluaran dapat dibuat lebih mudah dibaca dengan misalnya mengubah yang pertama-
menjadi-36
dan yang.
menjadi+47.-47
, di mana-36
berarti string 36-
karakter, dll.)Pendekatan ini memanfaatkan properti (yang juga digunakan Ben Frankel): mempertimbangkan kemungkinan simpul sebagai
-1, 0, 1
dan mengabaikan-1
simpul terakhir , daftar mewakili pohon yang valid jika dan hanya jika (1) semua awalan daftar memiliki jumlah non-negatif, dan (2) jumlah seluruh daftar sama dengan0
. Kondisi pertama dipertahankan sementara menghasilkan node perantara, jadi hanya kondisi kedua yang perlu diperiksa di akhir.Rekaman ini dibagi menjadi sel 5-node,
di mana
i
indeks (turun dari kiri ke kanan),d
adalah jumlah parsial, danx
merupakan elemen.Sketsa aliran kontrol:
Perhatikan bahwa kadang-kadang nilai disimpan atau diinisialisasi sebagai satu atau dua lebih besar dari nilai aktual (konseptual) dan disesuaikan sesuai kebutuhan.
sumber
Python 3 (
138134128121119 byte)Contoh output, untuk
n=5
:1 mewakili simpul biner, 0 mewakili simpul unary, dan -1 mewakili simpul terminal. Ada simpul terminal tersirat di ujung setiap pohon.
Program mulai memakan waktu terlalu lama
n=17
.sumber
JavaScript (Firefox 30-57), 79 byte
Dimana
-1
mewakili terminal,0
simpul unary dan1
simpul biner. Mulai lambat dim=14
PC saya. Secara rekursif bekerja kembali dari ujung pohon.l
dibatasi oleh fakta bahwa mungkin hanya ada 1 simpul yang tersisa di akhir.n
dibatasi oleh kebutuhan untuk memiliki cukup banyak simpul yang tidak terhitung untuk menjadi anak-anaknya.sumber
Prolog,
149144138137131107 byteDan untuk menghitung solusinya
sumber
Python, 71 byte
Ini mewakili pohon sebagai tupel bersarang seperti
((((),), ()),)
, yang dapat ditransformasikan menjadi((())())
dengan menghilangkan koma, spasi, dan bagian terluar()
.Versi 76 byte sebelumnya:
sumber
CJam, 38 byte
Menggunakan pendekatan berbeda yang dijawab Peter Taylor CJam.
Output akan menjadi sesuatu seperti
1110120020102100
. Setiap pohon adalah sekelompokn
digit (di manan
adalah nomor input).Ide dasarnya adalah bahwa kita menghasilkan setiap string mungkin digit
0
,1
, dan2
, dan kemudian menyaring hanya orang-orang yang pohon well-formed.sumber