Angka subfaktorial atau rencontres ( A000166 ) adalah urutan angka yang mirip dengan angka faktorial yang muncul dalam kombinatorik permutasi. Khususnya n th subfactorial ! N memberikan jumlah derangements dari satu set n elemen. Gangguan adalah permutasi di mana tidak ada elemen yang tersisa di posisi yang sama. Subfaktorial dapat didefinisikan melalui relasi rekurensi berikut:
!n = (n-1) (!(n-1) + !(n-2))
Faktanya, relasi perulangan yang sama berlaku untuk faktorial, tetapi untuk subfaktorial kita mulai dari:
!0 = 1
!1 = 0
(Untuk faktorial yang kita miliki, tentu saja, 1! = 1. )
Tugas Anda adalah menghitung ! N , diberikan n .
Aturan
Seperti faktorial, subfaktorial tumbuh dengan sangat cepat. Tidak apa-apa jika program Anda hanya dapat menangani input dan sedemikian rupa sehingga ! N dapat diwakili oleh tipe nomor asli bahasa Anda. Namun, algoritma Anda harus secara teori berfungsi untuk arbitrary n . Itu berarti, Anda dapat mengasumsikan bahwa hasil integral dan nilai menengah dapat diwakili dengan tepat oleh bahasa Anda. Perhatikan bahwa ini tidak termasuk konstanta e jika disimpan atau dihitung dengan presisi terbatas.
Hasilnya perlu bilangan bulat yang tepat (khususnya, Anda tidak dapat memperkirakan hasilnya dengan notasi ilmiah).
Anda dapat menulis sebuah program atau fungsi dan menggunakan salah satu metode standar untuk menerima input dan memberikan output.
Anda dapat menggunakan bahasa pemrograman apa pun , tetapi perhatikan bahwa celah ini dilarang secara default.
Ini adalah kode-golf , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.
Uji Kasus
n !n
0 1
1 0
2 1
3 2
4 9
5 44
6 265
10 1334961
12 176214841
13 2290792932
14 32071101049
20 895014631192902121
21 18795307255050944540
100 34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601
sumber
Jawaban:
Funciton , 336 byte
Hitungan byte mengasumsikan pengodean UTF-16 dengan BOM.
Ini mendefinisikan fungsi
f
yang mengambil satu bilangan bulat dan mengeluarkan bilangan bulat lainnya pada belokan 90 derajat ke kiri. Ini bekerja untuk input besar yang sewenang-wenang.Cobalah online!
Mengingat ini adalah Funciton, itu bahkan cukup cepat (n = 20 membutuhkan sekitar 14 detik pada TIO). Perlambatan utama datang dari rekursi ganda, karena saya tidak berpikir penerjemah Funciton secara otomatis memo fungsi.
Sayangnya, beberapa font monospasi tidak dengan benar monospace
♭
dan / atau menyisipkan celah kecil di antara garis. Berikut screenshot dari kode dari TIO dengan segala keindahannya:Saya pikir mungkin untuk golf ini lagi, misalnya dengan mengubah kondisi dari
>0
ke<1
dan menukar cabang-cabang kondisional, sehingga saya dapat menggunakan kembali angka literal, atau mungkin dengan menggunakan formula yang sama sekali berbeda, tapi saya cukup senang dengan betapa kompaknya sudah.Penjelasan
Ini pada dasarnya mengimplementasikan rekursi yang diberikan dalam tantangan, meskipun menggunakan kasus dasar ! (- 1) =! 0 = 1 . n-1 dan n-2 dihitung dengan fungsi pendahulunya
♭
, dan hasil antara n-1 digunakan kembali di tiga tempat. Tidak ada yang lebih dari itu, jadi saya hanya akan dengan cepat melewati aliran kontrol:Ini adalah header fungsi yang memancarkan input fungsi dan merindukan baris terlampir. Ini segera mencapai pertigaan, yang hanya menduplikasi nilai.
The
0
box hanya literal numerik. Persimpangan 4 arah menghitung dua fungsi: jalur yang mengarah dari bawah menghitung 0 <n , yang akan kita gunakan untuk menentukan kasus dasar. Jalur yang dibiarkan secara terpisah menghitung 0 << n (bergeser ke kiri), tetapi kami membuang nilai ini dengan konstruk Starkov .Kami mengarahkan ini ke dalam kondisional tiga arah
?
. Jika nilainya salah, kami mengembalikan hasil yang konstan1
. Ujung kanan longgar?
adalah output fungsi. Saya memutar sekitar 180 derajat di sini, sehingga orientasi relatif dari input dan outputf
lebih nyaman di sisa program.Jika kondisinya benar, maka nilai lainnya akan digunakan. Mari kita lihat jalan yang menuju ke cabang ini. (Perhatikan bahwa evaluasi Funciton sebenarnya malas sehingga cabang ini tidak akan pernah dievaluasi jika tidak diperlukan, yang memungkinkan terjadinya rekursi.)
Di cabang lain kita pertama menghitung n-1 dan kemudian membagi jalan dua kali sehingga kita mendapatkan tiga salinan dari nilai (satu untuk koefisien perulangan, satu untuk subfaktorial pertama, yang terakhir untuk n-2 ).
Seperti yang saya katakan, kami mengurangi satu salinan lagi dengan yang lain
♭
, lalu kami memberi makan n-1 dan n-2 secara rekursiff
dan akhirnya menambahkan dua hasil bersama di+
.Yang tersisa adalah mengalikan n-1 dengan ! (N-1) +! (N-2) .
sumber
Oasis , 5 byte
Menggunakan formula yang diberikan oleh Martin. Kode:
Versi yang dibedah:
dengan
a(0) = 1
dana(1) = 0
.Penjelasan,
a(n) =
:Cobalah online!
sumber
X
:-) BTW, apakah Anda sudah menerapkan ini ? Suatu hari kita tidak akan bisa lolos dengan hanya mengubah nilai awalHaskell , 25 byte
Cobalah online! Menggunakan pengulangan lain dari halaman OEIS .
sumber
Jelly , 7 byte
Pendekatan ini membangun kekacauan, jadi agak lambat.
Cobalah online!
Bagaimana itu bekerja
sumber
Brachylog (2), 11 byte
Cobalah online!
Penjelasan
Ini pada dasarnya hanya terjemahan langsung dari spec dari Bahasa Inggris ke Brachylog (dan dengan demikian memiliki keuntungan bahwa ia dapat dengan mudah dimodifikasi untuk menangani perubahan kecil pada spesifikasi, seperti menemukan jumlah kekacauan daftar tertentu).
sumber
Bahasa dengan solusi bawaan
Mengikuti saran xnor, ini adalah jawaban CW di mana solusi sepele berdasarkan pada satu built-in untuk menghitung subfaktorial atau menghasilkan semua gangguan harus diedit.
Mathematica, 12 byte
sumber
Python 3 ,
3532 byteIni menggunakan relasi perulangan ! N = n! (N-1) + (-1) n dari jawaban Haskell @ Laikoni , dengan case dasar ! 0 = 1 .
Cobalah online!
sumber
f=lambda n:n<1or n*f(n-1)+(-1)**n
.n=-1
, tidak masalah sama sekali nilai yang Anda gunakan. Itu bisa berguna untuk beberapa bahasa (misalnya dalam Mathematica Anda benar-benar bisa membiarkannya tidak terdefinisi jika itu menyimpan byte).M , 9 byte
Seperti yang Anda lihat dengan menghapus
Ḟ
, M menggunakan matematika simbolik, sehingga tidak akan ada masalah presisi.Cobalah online! Bukan solusi terpendek yang telah diposting, tetapi cepat .
Bagaimana itu bekerja
sumber
MATL ,
98 byteDemikian pula dengan jawaban Jelly @ Dennis , ini benar-benar membangun permutasi dan menghitung berapa banyak dari mereka adalah kekacauan; jadi lambat.
Cobalah online!
sumber
Matematika , 21 byte
Saya sangat baru dalam hal ini dan tidak tahu apa yang saya lakukan ...
Cobalah online!
sumber
Round[(#/. 0->2)!/E]&
dan±0=1;±n_:=Round[n!/E]
(walaupun saya tidak tahu apakah Matematika mendukung pengkodean byte tunggal untuk file sumber seperti Mathematica).±
yang kedua. Ini akan bekerja denganf
, tetapi dengan biaya dua byte.Round[#!/E]+1-Sign@#&
. Nilai awal yang mengganggu ...!Ruby, 27 byte
~0**n
lebih pendek dari(-1)**n
!sumber
CJam (10 byte)
Demo online .
Ini menggunakan pengulangan
!n = n !(n-1) + (-1)^n
, yang saya berasal darin! / e
dan kemudian menemukan sudah di OEIS.Pembedahan
Pengulangan menghitung
(-1)^n !n
, jadi kita perlu mengambil nilai absolut di akhir:sumber
05AB1E , 8 byte
Cobalah online!
Penjelasan
sumber
MATLAB, 33 byte
Fungsi Anonympus yang menggunakan rumus di Bagian 3 dari Pengaturan dan aplikasi oleh Mehdi Hassani.
Contoh penggunaan:
sumber
JavaScript (ES6), 26 byte
Menggunakan relasi perulangan dari jawaban @ Laikoni. Di ES7 Anda dapat menyimpan byte dengan menggunakan
+(-1)**n
alih-alih-(~n%2|1)
.sumber
PostScript,
817669 byteBerikut ini adalah implementasi dari kedua formula.
n * f (n-1) + (- 1) ^ n
/ f {dup 0 eq {pop 1} {dup dup 1 sub f mul exch 2 mod 2 mul 1 sub sub} ifelse} defVersi itu menghasilkan float. Jika perlu untuk mengeluarkan bilangan bulat:
yang beratnya mencapai 73 byte.
Formula lainnya sedikit lebih panjang: 81 byte.
(n-1) * (f (n-1) + f (n-2))
Fungsi-fungsi ini mendapatkan argumennya dari stack, dan membiarkan hasilnya di stack.
Anda dapat menguji fungsi-fungsi, baik dalam file atau pada prompt PostScript interaktif (misalnya GhostScript) dengan
keluaran
Berikut adalah file PostScript lengkap yang membuat output ke layar atau halaman printer. (Komentar dalam PostScript dimulai dengan
%
).sumber
-1 3 2 roll exp
sedikit lebih pendek dari adilexch 2 mod 2 mul 1 sub
.exp
: oops: Namun, ia mengembalikan float, dan saya pikir saya perlu menampilkan bilangan bulat agar sesuai dengan pertanyaan.cvi
dan melakukan penghematan. (Catatan: belum diuji, tetapi dari membaca dokumen saya pikir itu harus berhasil).cvi
berfungsi, dan masih lebih pendek dari versi saya sebelumnya.PHP, 69 Bytes
gunakan cara ini
a(n) = n*a(n-1) + (-1)^n
sumber
PHP,
5044Jalankan dengan
echo <n> | php -nR '<code>
Keindahan
a(n) = n*a(n-1) + (-1)^n
adalah bahwa itu hanya tergantung pada nilai sebelumnya. Ini memungkinkan untuk diimplementasikan secara iteratif daripada secara rekursif. Ini menyimpan fungsi yang panjang deklarasi .-6 bytes oleh @Titus. Terima kasih!
sumber
$i++<$argv[1]
. -2 byte:for(;$i++<$argv[1];)$n=++$n*$i-$i%2*2;echo$n+1;
. (-3 byte dengan-R
dan$argn
.)-R
dan$argn
?Mathematica, 40 byte
Yang datang pada 31 byte di bawah pengkodean ISO 8859-1 default.
sumber
C, 34 byte
Penjelasan:
sumber
R, 47 byte
Menggunakan rumus yang sama dengan jawaban Mego .
Metode alternatif, 52 byte menggunakan
PerMallows
perpustakaansumber
Sebenarnya , 18 byte
Cobalah online!
Penjelasan:
Versi 12-byte yang akan berfungsi jika Sebenarnya memiliki lebih presisi:
Cobalah online!
Tidak seperti semua jawaban lain (pada saat dikirim), solusi ini tidak menggunakan rumus rekursif atau rumus penjumlahan. Sebagai gantinya, ia menggunakan rumus berikut:
Formula ini relatif mudah diterapkan di Sebenarnya:
Sekarang, satu-satunya masalah adalah formula hanya berlaku untuk positif
n
. Jika Anda mencoba menggunakann = 0
, rumusnya salah menghasilkan0
. Ini mudah diperbaiki, namun: dengan menerapkan negasi boolean pada input dan menambahkannya ke output formula, output yang benar diberikan untuk semua non-negatifn
. Dengan demikian, program dengan koreksi itu adalah:sumber
n = 100
),(-1)**n/n!
tidak dapat diwakili dengan float IEEE 754 presisi ganda. Itu bisa diterima sesuai tantangan.n=4
...Ditumpuk , 30 byte
Cobalah online!
Fungsi rekursif sederhana. Menggunakan fakta
!n = not n
untuk itun < 2
. Sebut sebagain f
.sumber
Alice ,
2018 byteCobalah online!
Penjelasan
Kegunaan ini rekursi dari Laikoni ini jawabannya , ! N = n! (N-1) + (-1) n . Mirip dengan jawaban Funciton, saya menggunakan kasus dasar ! (- 1) = 1 . Kami menempatkan 1 itu di tumpukan
1.
. Lalu ini...... hanya kerangka I / O desimal yang biasa. Kode utamanya sebenarnya
Rusak:
sumber