Diberikan bilangan bulat 1 ≤ N ≤ 1.000.000 sebagai input, menghasilkan digit N -nol terakhir ! , Di mana ! adalah faktorial (produk dari semua angka dari 1 hingga N , inklusif). Ini adalah urutan OEIS A008904 .
Program Anda perlu selesai dalam waktu 10 detik pada mesin yang masuk akal untuk input yang valid.
Uji Kasus
1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4
Ini adalah kode-golf sehingga kode terpendek dalam byte menang!
Jawaban:
Ruby - 63 karakter
Sumber - http://oeis.org/A008904
Menangani hingga seribu digit di bawah satu detik.
Uji
sumber
Mathematica,
4536 byteSangat mudah dibaca untuk jawaban yang menang. :) (Kemudian lagi, belum ada pengiriman GolfScript & Co.)
Ini menangani input 1.000.000 dalam waktu sekitar 5 detik pada mesin saya.
sumber
Python - 75
sumber
PARI / GP - 27 byte
Ini memperdagangkan kecepatan untuk ukuran - testcase membutuhkan waktu lama (~ 6 detik).
Versi ini jauh lebih cepat (~ 15 mikrodetik) tetapi membutuhkan 81 byte:
Anda dapat menggunakan kode (non-golf) ini untuk menguji:
sumber
Windows PowerShell, 53
565960637390Catatan:
Sejarah:
$input
ke string sudah cukup; para pemeranint
diterapkan secara implisit.sumber
Perl, 53
5861karakterSemua spasi putih dapat dihapus, tetapi saya meninggalkannya untuk "keterbacaan". Catatan: tidak menggunakan rumus eksplisit konyol dari Sloane.
Menghitung f (10 ^ 6) dalam 8,7 detik pada mesin saya.
Pembaruan : OP menginginkannya menjadi keseluruhan program:
Itu membuatnya menjadi 55 karakter.
sumber
CJam - 28
Anda dapat mencobanya di http://cjam.aditsu.net/ untuk nilai hingga 10.000 atau lebih; untuk angka yang lebih besar Anda harus menggunakan penerjemah java . 1000000 berjalan dalam waktu sekitar 3 detik di laptop saya.
Penjelasan:
Sayangnya solusi langsung terlalu lambat, jadi saya hanya menyimpan 7 digit terakhir (sebelum nol akhir) setelah setiap perkalian.
Catatan: bahasa ini jauh lebih baru daripada pertanyaan.
sumber
Mathematica, 34 byte
sumber
05AB1E , 4 byte
Cobalah online!
Penjelasan
sumber
Jelly , 4 byte
Cobalah online!
Penjelasan
Menggunakan fakta bahwa ketika
Ṛ
(membalikkan daftar; tidak membuat vektor)) diterapkan ke integer secara otomatis mengambilD
(digit) terlebih dahulu.Dengan input 8:
Saya tidak berpikir ada satu byte "elemen kebenaran pertama" (yang
ȯ/
bertindak sebagai) tetapi jika ada maka ini dapat dipersingkat menjadi tiga byte total.sumber
Java (OpenJDK 8) , 62 byte
Cobalah online!
Mirip dengan @Kevin Cruijssen tetapi menghemat 5 byte dengan menggabungkan loop.
sumber
||
dengan|
, dan byte tambahan dengan mengganti==0
dengan<1
. Selamat menikmati!C,
150140135 byteIni adalah versi untuk sistem ASCII; ganti string
33436
dengan11214
untuk sistem EBCDIC, atau dengan\1\1\2\1\4
untuk program portabel.Solusi C agak terhambat oleh persyaratan untuk menyediakan program lengkap; Namun, ini menjawab pertanyaan sepenuhnya.
Cobalah online (memerlukan Javascript):
Penjelasan
Ini didasarkan pada algoritma yang digariskan dalam Least Significant Non-Zero Digit of n! , berbalik sehingga kita kembali untuk menemukan kekuatan tertinggi lima, dan melakukan perhitungan di jalan keluar. Tabel konstanta terlalu besar, jadi saya menguranginya dengan menemukan hubungan antara residu sebelumnya
r
, digit saat inid
dan kedalaman rekursik
:Sebab
r>0
, ini menyelesaikan ke kalir
kali konstan2^dk
(mod 5); konstanta ada dia[]
bawah (sebaris dalam kode golf). Kami juga mengamati bahwa itu(2^4)%5
adalah 1, sehingga kami dapat mengurangi eksponen untuk menghindari meluapnya kisaranint
.Tes:
Performanya juga terhormat. Berikut input maksimum untuk sistem dengan 32-bit
int
:Saya mendapat timing yang sama dengan 64-bit maksimal
int
juga.sumber
2147483647!
memiliki lebih dari 19 miliar digit, dan(2^63-1)!
lebih dari 170.000.000.000.000.000.000 digit, jadi ini adalah kemenangan besar atas perhitungan faktorial.1000000!
sebagaimana ditentukan dalam pertanyaan layak untuk dihitung pada perangkat keras saat ini; itu hanya 5½ juta digit. :-)PHP - 105
Berjalan di bawah 10 detik dengan testcase yang diberikan.
sumber
Python3
239 CharsDapat melakukan 10000 dalam ~ 3,2 detik (Ideone memotong saya pada 8 detik, saya yakin itu akan memakan waktu lebih dari 10 detik :()
Python2.6
299 Chars (sedikit lebih cepat)sumber
Haskell, 78 karakter
(Mungkin perlu dikompilasi untuk menghitung 1.000.000! Dalam 10 detik).
sumber
foldl1
denganproduct
(cf codegolf.stackexchange.com/questions/607/find-the-factorial/… ). Tetapi apakah Anda benar-benar mencoba dengan 1000000! ?J -
4240 karakterSeluruh program. Simpan program ini dalam file dan jalankan
jconsole script.ijs 1234
. Perhatikan bahwa program ini tidak keluar dari juru bahasa setelah mencetak hasilnya. Ketik^D
atauexit]0
untuk keluar dari juru bahasa.Berikut ini penjelasannya:
x #. y
menafsirkan vektor bilangan bulaty
sebagai angka dasarx
; misalnya,10 #. 1 2 3 4
hasil1234
.u inv
menghasilkan kebalikan dari kata kerjau
. Secara khusus,x #. inv y
mewakiliy
sebagaix
nomor dasar ; misalnya,10 #. 1234
hasil1 2 3 4
. Perhatikan bahwainv
didefinisikan sebagai^:_1
, yaitu,u
diterapkan -1 kali.x * y
adalah produk darix
dany
, dengan demikianx 10&#.inv@* y
menghasilkan representasi basis-10 dari produkx
dany
.x # y
menyalin item ke- ny
sesering item ke- n darix
; kapanx
vektor boolean,x
pilih item mana yangy
akan diambil. Misalnya,1 0 1 0 # 1 2 3 4
hasil1 3
.* y
menghasilkan signum dariy
.x u~ y
adalah refleksif dariu
, yaitu, sama dengany u x
.y #~ * y
hasilkan vektor semua itemy
yang positif. Dalam notasi diam-diam, ini dapat ditulis dengan kait sebagai(#~ *)
.{: y
menghasilkan item terakhir dalamy
.([:{:@(#~*)10&#.inv@*)
.u/ y
adalah reduksi dariy
, yaitu, kata kerja diadu
dimasukkan di antara elemeny
. Misalnya,+/1 2 3 4
seperti1 + 2 + 3 + 4
dan hasil10
.([:{:@(#~*)10&#.inv@*)/ y
menghasilkan digit terakhir dari produk itemy
.ARGV
adalah kotak vektor dari argumen baris perintah.".>{:ARGV
adalah argumen terakhir tanpa kotak dan ditafsirkan sebagai angka.i. y
menghitung bilangan asli dari0
hinggay - 1
.1+i. y
menghasilkan bilangan asli dari1
hinggay
. Saya bisa juga menggunakan>:
increment di sini, tetapi1+
lebih jelas dengan biaya karakter yang sama.1+i.".>{:ARGV
(vektor1
ke nomor dalam argumen baris perintah terakhir) ke kata kerja([:{:@(#~*)10&#.inv@*)/
dan mencetak hasilnya denganecho
.sumber
Pyt , 5 byte
Penjelasan:
Cobalah online!
sumber
R ,
63555146 byteHitung faktorial, ekstrak angka non-nol terakhir. Terima kasih kepada Giuseppe karena menyediakan struktur dasar.
Cobalah online!
Atau, jawaban lama 51 byte saya:
Menghitung faktorial, mengkonversi ke karakter, menghapus semua
0
s, dan kemudian mengambil karakter terakhir. Disimpan 2 byte berkat Giuseppe.Cobalah online!
sumber
gamma(x+1)
lebih pendek darifactorial(x)
(y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]
54 byte.nchar(x)
dengan1e5
untuk solusi 46-byte! Bagus sekali.> <> , 25 byte
Cobalah online!
Pegangan 0! dengan benar juga. Nilai melewati
-v
bendera.sumber
1000
tidak menghasilkan keluaran apa pun pada TIO - apa yang salah?Perl 6 ,
2635 byteCobalah
Sebagai program lengkap:
Cobalah
Diperluas:
sumber
C (gcc) , 72 byte (fungsi)
Cobalah online!
C (gcc) ,
10199 byte (seluruh program)Cobalah online!
Pertanyaan ini hanya berumur 8 tahun sehingga "mesin yang masuk akal" tidak sama dengan waktu itu, tapi saya mendapatkan waktu ~ 0,01 detik di komputer saya ketika melakukan semua kasus uji bersama, jadi kecuali komputer telah meningkatkan kecepatannya dengan faktor 1000 dekade terakhir ini, itu harus baik-baik saja.
sumber
Tambahkan ++ , 11 byte
Cobalah online!
sumber
Attache , 26 byte
Cobalah online!
Penjelasan
Ini adalah komposisi dari 4 fungsi:
`!
- ini adalah versi fungsional dari operator faktorialDigits
- ini mendapatkan angka dari faktorial\&:(All@V)
- Ini adalah fungsi pemilihan. Ini bekerja dengan ikatan kiri (&:
) fungsiAll@V
untuk\
, yang dipilih. Pada gilirannya,All@V
ini adalah cara singkat untuk menguji apakah suatu bilangan bukan 0. Ia bekerja dengan memasukkan inputnya ke sebuah vektor0 -> [0]
kemudian menanyakan apakah semua anggota itu benar (yaitu bukan 0). Ini memberikan digit angka tanpa 0s.Last
- ini hanya mendapatkan anggota terakhir dari array ini.sumber
APL (Dyalog Unicode) ,
1815 byteCobalah online!
Fungsi awalan Tacit. Mengembalikan digit yang benar untuk satu test case, atau serangkaian digit untuk beberapa test case.
Terima kasih kepada @ Adám dan @ErikTheOutgolfer untuk masing-masing 3 byte.
Bagaimana?
sumber
APL NARS, 28 byte, 14 karakter
Saya tidak tahu mengapa tetapi ini lulus ujian:
sumber
AWK ,
4757 byteCobalah online!
Solusi asli tidak menangani nilai input "besar" dengan sangat baik. Dapat menambah
-M
untuk memaksanya bekerja, tetapi itu juga membutuhkan lebih banyak waktu pemrosesan.sumber
inf
tidak%
begitu baik. :(Japt , 6 byte
Datang dengan 6-byters berbeda tapi saya suka yang terbaik ini. Tapi saya yakin pasti ada cara untuk melakukannya dalam 5 menit.
Cobalah
Penjelasan
Ê
menghitung faktorial dari input,s
mengubahnya menjadi string dan kembali ke integer setelahw
membalikkannya,ì
mengubah hasilnya menjadi array angka danv
mengembalikan elemen pertama.Alternatif
sumber
Perl 5 , 36 + 10 (
-p -Mbigint
) = 46 byteCobalah online!
sumber
f
(harus 4 ) dan 100 ⇒7
(harus 4 )