Dengan bilangan bulat n, sebutkan semua kemungkinan pohon biner penuh dengan n simpul internal. (Pohon biner penuh memiliki tepat 2 anak di setiap simpul internal). Struktur pohon harus berupa output sebagai traversal pre-order dari pohon dengan 1 mewakili simpul internal, dan 0 mewakili simpul eksternal (Null).
Berikut adalah contoh untuk beberapa n pertama:
0:
0
1:
100
2:
11000
10100
3:
1110000
1101000
1100100
1011000
1010100
Ini adalah kode golf dengan hadiah mencapai karakter paling sedikit. Pohon-pohon harus menghasilkan satu per baris ke stdout. Program harus membaca n dari commandline atau stdin.
code-golf
combinatorics
binary-tree
Kyle Butt
sumber
sumber
Jawaban:
Perl -
12579 karakterHitung termasuk 4 karakter untuk
-ln
opsi " ". Mengambil n dari stdin.Pendekatan konstruktif baru:
Bentuk solusi untuk n dengan mengganti simpul internal baru ("100") untuk setiap daun ("0"), pada gilirannya, di setiap pohon dari solusi untuk n-1.
(Saya berutang konsep ini kepada solusi orang lain yang menggunakan subtitusi internal node to leaf [100-> 0] untuk memverifikasi string yang dihasilkan secara berurutan, dan saya yakin saya melihat - setelah menulis jawaban saya berdasarkan konsep itu - ini sama dengan 0 - > 100 metode konstruksi dalam pengeditan menengah seseorang.)
Pendekatan rekursif sebelumnya:
Berubah tak rekursif:
sumber
PHP
(142)(138)(134)(113)Berjalan dari baris perintah, yaitu "php golf.php 1" menghasilkan "100".
Suntingan: Potong 4 karakter dengan metode alternatif, susun string dari 0 daripada berulang dari $ n. Menggunakan PHP 5.3 untuk operator ternary yang dipersingkat; jika tidak, diperlukan 2 karakter lagi.
EDIT 2: Menyimpan 4 karakter lagi dengan beberapa perubahan pada loop.
EDIT 3: Saya sedang mencoba pendekatan yang berbeda dan akhirnya saya mendapatkannya di bawah metode lama.
Semua pohon dapat dianggap sebagai representasi biner dari bilangan bulat antara 4 ^ n (atau 0, ketika n = 0) dan 2 * 4 ^ n. Fungsi ini loop melalui rentang itu, dan mendapatkan string biner dari setiap angka, kemudian berulang kali menguranginya dengan mengganti "100" dengan "0". Jika string terakhir adalah "0", maka itu adalah pohon yang valid, jadi hasilkan.
sumber
Ruby,
9994928987 karakterInput dibaca dari stdin.
Sunting 1: IO yang Diubah (lihat komentar Lowjacker)
Sunting 2: Algoritma berubah.
Sunting 3: Versi sekarang menggunakan pendekatan ketiga (menggunakan ide migimaru).
Sunting 4: Lagi dua karakter. Terima kasih untuk migimaru.
sumber
*?\n
, karenaputs
mencetak setiap elemen dari array di barisnya sendiri.Ruby 1.9
(80)(79)Menggunakan pendekatan non-rekursif dan konstruktif yang digunakan oleh DCharness.
EDIT: Disimpan 1 karakter.
sumber
Haskell 122 karakter
Karena IO adalah bagian non-sepele dari kode di haskell, mungkin seseorang dapat menggunakan solusi serupa dalam bahasa lain. Intinya acak berjalan di kotak dari kiri bawah ke kanan berhenti jika diagonal disilangkan. Setara dengan yang berikut:
sumber
Golfscript, 60
83Saya membangun mode skrip golf untuk Emacs untuk mengerjakan ini, jika ada yang tertarik.
sumber