Alk * rantai lurus didefinisikan sebagai urutan atom karbon yang dihubungkan oleh ikatan tunggal (alkana), rangkap dua (alkena), atau rangkap tiga (alkuna), (digunakan hidrogen implisit.) Atom karbon hanya dapat membentuk 4 ikatan, jadi tidak ada atom karbon yang dipaksa memiliki lebih dari empat ikatan. Alk * rantai lurus dapat direpresentasikan sebagai daftar ikatan karbon-karbonnya.
Ini adalah beberapa contoh alkali rantai lurus yang valid:
[] CH4 Methane
[1] CH3-CH3 Ethane
[2] CH2=CH2 Ethene
[3] CH≡CH Ethyne
[1,1] CH3-CH2-CH3 Propane
[1,2] CH3-CH=CH2 Propene
[1,3] CH3-C≡CH Propyne
[2,1] CH2=CH-CH3 Propene
[2,2] CH2=C=CH2 Allene (Propadiene)
[3,1] CH≡C-CH3 Propyne
[1,1,1] CH3-CH2-CH2-CH3 Butane
...
Meskipun tidak, karena setidaknya satu atom karbon akan memiliki lebih dari 4 ikatan:
[2,3]
[3,2]
[3,3]
...
Tugas Anda adalah membuat program / fungsi yang, jika diberi bilangan bulat positif n
, mengeluarkan / mengembalikan jumlah rantai lurus yang valid n
dengan panjang persis atom karbon. Ini adalah OEIS A077998 .
Spesifikasi / Klarifikasi
- Anda harus menangani
1
dengan benar dengan kembali1
. - Orang-orang suka
[1,2]
dan[2,1]
dianggap berbeda. - Output adalah panjang daftar semua kemungkinan alk panjang.
- Anda tidak harus menangani 0 dengan benar.
Kasus uji:
1 => 1
2 => 3
3 => 6
4 => 14
Ini adalah kode golf, jadi jumlah byte terendah menang!
sumber
<=4
, kan?Jawaban:
Oasis ,
97 byteCobalah online!
Penjelasan
Ini menggunakan hubungan pengulangan di OEIS :
sumber
xkcd
di dalamnya.xkcd-+311
berfungsi , karenak
saat ini bukan pilihan ...MATL , 10 byte
Cobalah online!
Penjelasan
Ini menggunakan karakterisasi yang ditemukan di OEIS
sumber
Oasis ,
98 byteMenyimpan satu byte, terima kasih kepada Adnan
Cobalah online!
Penjelasan
sumber
x
kependekan dari2*
:).0
sini)Jelly, 10 byte
Cobalah online!
Menggunakan algoritma Luis Mendo .
Penjelasan
Jelly, 15 byte
Cobalah online!
Menggunakan kekuatan kasar.
Penjelasan
sumber
MATL , 14 byte
Cobalah online!
Penjelasan
Ini menghasilkan kekuatan Cartesian dari
[1 2 3]
"dinaikkan" ke jumlah atom minus 1, dan kemudian menggunakan konvolusi untuk memeriksa bahwa tidak ada dua angka yang berdekatan dalam setiap jumlah tupel Cartesian lebih dari4
.sumber
Mathematica, 48 byte
Seperti yang ditunjukkan Luis Mendo , ini adalah A006356 di OEIS. Ini adalah upaya asli saya:
Untuk input
n
,Tuples[{1,2,3},n-1]
adalah daftar semua(n-1)
elemen elemen dalam{1,2,3}
mewakili semua kemungkinan urutan ikatan tunggal, rangkap, atau rangkap tiga untukn
atom karbon.+##<5&
adalah fungsi murni yang mengembalikan apakah jumlah argumennya kurang dari5
, sehinggaSplit[#,+##<5&]&
membagi daftar menjadi sublists yang terdiri dari elemen berurutan yang jumlah berpasangannya kurang dari5
. Menggambarkan alk * ne yang valid setara dengan daftar ini yang memiliki panjang0
(dalam kasus di manan=1
) atau1
, jadi saya hanyaCount
jumlah(n-1)
-tupel di mana panjang daftar itu cocok0|1
.If[+##>4,4,#2]&
kembali4
jika jumlah argumennya lebih besar dari4
dan mengembalikan argumen kedua sebaliknya.Fold[If[+##>4,4,#2]&]
melakukanFold
input kiri dengan fungsi ini. Jadi di sini sayaCount
jumlah(n-1)
-tuple yang tidak diberikan operator yang menerapkan ini4
. Kasus di manan=1
dicakup sejakFold
tetap tidak dievaluasi ketika argumen kedua adalah daftar kosong{}
.sumber
LinearRecurrence[{2,1,-1},{1,3,6},#][[#]]&
?this site
, maksud Anda Oei atau PPCG?Python, 51 byte
Ini adalah implementasi langsung dari hubungan perulangan. Terima kasih kepada Tim Pederick untuk 3 byte. Outputnya adalah float di Python 3 dan integer di Python 2.
Cobalah online!
sumber
(n*n+n)/2
lebih pendek dari[1,3,6][n-1]
. Dan jika Anda menggunakan Python 3 dan tidak suka berakhir dengan output floating-point,(n*n+n)//2
masih lebih pendek.Pyth - 16 byte
Menggunakan kekuatan kasar.
Test Suite .
sumber
Ruby, 62 byte
Pendekatan brute force 10 base yang sangat tidak efisien. Dapat ditingkatkan ke basis 5 untuk byte tambahan.
Angka-angka dihasilkan ketika setiap digit mewakili ikatan (n-1 digit.)
0
Mewakili urutan ikatan 1,2
mewakili urutan ikatan 3. Digit lebih dari 2 tidak valid.Kami mengalikannya dengan 11 untuk menjumlahkan pasangan angka yang berdekatan. Sekali lagi angka di atas 3 tidak valid.
Kami menggabungkan dua angka dalam sebuah string dan melakukan regex untuk mencari digit yang tidak valid. Jika tidak ada yang ditemukan, kami menambah penghitung.
dalam program uji
sumber
Ruby, 51 byte
Berdasarkan hubungan perulangan per OEIS A006356.
Mulai dengan larik untuk elemen 0,1 dan 2 dari urutan yang 1 (sebagaimana dihitung oleh saya, untuk membuatnya bekerja), masing-masing 1 dan 3.
Iteratif menambahkan
n
lebih banyak elemen ke urutan, lalu mengembalikan elemenn
. Itu selalu menghitung 2 elemen lebih dari yang sebenarnya perlu, tapi masih waktu linier, yang jauh lebih efisien daripada jawaban saya sebelumnya.dalam program uji
sumber
Mathematica,
4240 byteHitungan byte mengasumsikan pengodean byte tunggal yang kompatibel seperti CP-1252 (default pada instalasi Windows).
Ini hanya mengimplementasikan pengulangan yang diberikan pada OEIS sebagai operator unary.
sumber
CJam (19 byte)
Test suite online . Ini adalah blok anonim (fungsi) yang mengambil satu item di tumpukan dan meninggalkan satu di tumpukan. Perhatikan bahwa paket uji termasuk
a(0) = 1
.Pengulangan yang digunakan didasarkan pada pengamatan untuk urutan OEIS terkait A006356 :
tetapi dengan offset yang sesuai, yang menghilangkan kebutuhan untuk final
+ 1
seperti sekarang tercakup oleha(0)
.Pembedahan
sumber
Brain-Flak, 56 byte
Gunakan algoritme yang dirinci dalam komentar pertama pada halaman OEIS.
Cobalah online!
Penjelasan
Urutan dapat didefinisikan sebagai berikut:
Program dimulai pada
1
dan berulang kali menerapkan pengulangan ini untuk menghitungu(k)
Kode Beranotasi (anotasi aktual yang akan datang)
Visualisasi tumpukan
Dalam satu iterasi dari loop utama inilah yang terjadi (perhatikan bahwa nol mungkin ada atau tidak ada tetapi tidak masalah dengan cara apa pun):
Keadaan tumpukan sekarang sama seperti itu pada awal loop kecuali bahwa tumpukan saat ini sekarang memiliki nilai-nilai berikutnya untuk
u
,v
danw
di atasnya.sumber
Perl 6, 48
Semula
tapi saya lupa saya membutuhkan
sub f
sehingga solusi berulang menang.sumber
Dyalog APL, 30 byte
Menggunakan kekuatan kasar. Penjelasan (upaya terbaik saya setidaknya satu):
sumber
Dyalog APL, 29 byte
Bekerja dengan menggunakan definisi rekursif dari urutan bilangan bulat OEIS A006356.
sumber
Python dengan Numpy, 62 byte
Saya harus mencobanya, tetapi tampaknya Python murni dan rekursi lebih pendek dari numpy dan eksplisit, perhitungan berbasis matriks pada halaman OEIS.
sumber
R,
6158555150 byteMengambil input dari stdin, menggunakan matriks eksponensial untuk menentukan hasil yang tepat.
Jika Anda lebih suka solusi rekursif, berikut ini adalah implementasi langsung dari relasi perulangan yang tercantum dalam OEIS, untuk 55 byte .
sumber
Excel, 123 byte
Menerapkan formula dari OEIS:
Seperti biasa, masukan
A1
, rumus di sel lain.Gali identitas Trig lama untuk melihat apakah bisa membantu. Sekarang kepalaku sakit.
sumber
Lithp , 79 byte
Menerapkan urutan bilangan bulat rekursif yang tercantum dalam OEIS.
Implementasi yang mudah dibaca dan test suite.
sumber