Biorąc na wejściu liczbę całkowitą 1 ≤ N ≤ 1 000 000 , wypisz ostatnią niezerową cyfrę N! gdzie ! jest silnią (iloczyn wszystkich liczb od 1 do N włącznie). Jest to sekwencja OEIS A008904 .
Twój program musi zakończyć się w ciągu 10 sekund na rozsądnej maszynie dla każdego ważnego wejścia.
Przypadki testowe
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
To jest golf golfowy, więc wygrywa najkrótszy kod w bajtach!
Odpowiedzi:
Rubin - 63 znaki
Źródło - http://oeis.org/A008904
Obsługuje f do tysiąc cyfr w ciągu sekundy.
Test
źródło
Mathematica,
4536 bajtówBardzo czytelny dla zwycięskiej odpowiedzi. :) (Z drugiej strony, nie ma jeszcze zgłoszenia GolfScript & Co.).
To obsługuje wejście 1 000 000 w około 5 sekund na moim komputerze.
źródło
Python - 75
źródło
PARI / GP - 27 bajtów
Szybkość wymiany zależy od rozmiaru - testowanie zajmuje dużo czasu (~ 6 sekund).
Ta wersja jest znacznie szybsza (~ 15 mikrosekund), ale zajmuje 81 bajtów:
Możesz użyć tego (nie golfowego) kodu do przetestowania:
źródło
Windows PowerShell, 53
565960637390Uwagi:
Historia:
$input
Wystarczy rzut na sznur; rzutowanieint
jest stosowane domyślnie.źródło
Perl, 53
5861postacieWszystkie białe znaki można usunąć, ale pozostawiłem to dla „czytelności”. Uwaga: nie używanie jakiejś głupiej, jawnej formuły Sloane.
Oblicza f (10 ^ 6) w 8,7 sekundy na mojej maszynie.
Aktualizacja : OP chciał, aby był to cały program:
To daje 55 znaków.
źródło
CJam - 28
Możesz spróbować na http://cjam.aditsu.net/ dla wartości do około 10000; w przypadku większych liczb należy użyć interpretera Java . 1000000 działa na moim laptopie w około 3 sekundy.
Wyjaśnienie:
Niestety, proste rozwiązanie jest zbyt wolne, więc po każdym pomnożeniu zachowuję tylko ostatnie 7 cyfr (przed końcowymi zerami).
Uwaga: ten język jest znacznie nowszy niż pytanie.
źródło
Mathematica, 34 bajty
źródło
05AB1E , 4 bajty
Wypróbuj online!
Wyjaśnienie
źródło
Galaretka , 4 bajty
Wypróbuj online!
Wyjaśnienie
Wykorzystuje fakt, że kiedy
Ṛ
(odwraca listę; nie wektoryzuje) jest stosowana do liczby całkowitej,D
najpierw automatycznie pobiera (cyfry).Z wejściem 8:
Nie sądzę, że istnieje jeden bajtowy „pierwszy element zgodny z prawdą” (który
ȯ/
działa jako), ale jeśli tak, to można go skrócić do trzech bajtów ogółem.źródło
Java (OpenJDK 8) , 62 bajty
Wypróbuj online!
Podobne do @Kevin Cruijssen, ale oszczędza 5 bajtów, łącząc pętle.
źródło
||
z|
, oraz dodatkowy bajt zastępując==0
z<1
. Miłego pobytu!C,
150140135 bajtówTo jest wersja dla systemów ASCII; wymienić łańcuch
33436
ze11214
dla systemu EBCDIC, lub\1\1\2\1\4
na przenośnym programem.Rozwiązania w C są nieco utrudnione przez wymóg zapewnienia pełnego programu; to jednak w pełni odpowiada na pytanie.
Wypróbuj online (wymaga Javascript):
Wyjaśnienie
Opiera się na algorytmie przedstawionym w Najmniej znaczącej niezerowej cyfrze n! , odwrócił się, abyśmy znaleźli najwyższą potęgę pięciu i dokonali obliczeń po wyjściu. Tabele stałych były zbyt duże, więc zmniejszyłem je, znajdując związek między poprzednią resztą
r
, bieżącą cyfrąd
i głębokością rekurencjik
:Bo
r>0
to rozwiązuje się do stałych czasówr
razy2^dk
(mod 5); stałe znajdują sięa[]
poniżej (wstawione w kodzie golfowym). Obserwujemy również, że(2^4)%5
wynosi 1, więc możemy zmniejszyć wykładnik, aby uniknąć przepełnienia zakresuint
.Testy:
Wydajność jest również godna szacunku. Oto maksymalne wejście dla systemu z 32-bitami
int
:Mam te same czasy przy maksymalnym 64-bitowym
int
.źródło
2147483647!
ma on ponad 19 miliardów cyfr i(2^63-1)!
ponad 170 000 000 000 000 000 000 000 cyfr, więc jest to duża wygrana w stosunku do obliczania silni.1000000!
jak określono w pytaniu, możliwe jest obliczenie na obecnym sprzęcie; to tylko 5,5 miliona cyfr. :-)PHP - 105
Działa poniżej 10 sekund z podaną walizką testową.
źródło
Python3
239 znakówMoże zrobić 10000 w ~ 3,2 sekundy (Ideone odcina mnie po 8 sekundach, jestem pewien, że zajmie to więcej niż 10 sekund :()
Python2.6
299 znaków (nieco szybciej)źródło
Haskell, 78 znaków
(Prawdopodobnie trzeba go skompilować, aby obliczyć 1 000 000! W 10 sekund).
źródło
foldl1
zproduct
(por codegolf.stackexchange.com/questions/607/find-the-factorial/... ). Ale czy rzeczywiście próbowałeś z 1000000! ?J -
4240 znakówCały program. Zapisz ten program w pliku i uruchom z
jconsole script.ijs 1234
. Zauważ, że ten program nie wychodzi z interpretera po wydrukowaniu wyniku. Wpisz^D
lub,exit]0
aby wyjść z interpretera.Oto wyjaśnienie:
x #. y
interpretuje wektor liczb całkowitychy
jakox
liczbę podstawową ; na przykład10 #. 1 2 3 4
daje1234
.u inv
zwraca odwrotność czasownikau
. W szczególnościx #. inv y
reprezentujey
jakox
liczbę podstawową ; na przykład10 #. 1234
daje1 2 3 4
. Należy zauważyć, żeinv
określa się jako^:_1
, że jestu
stosowana -1 czasu.x * y
Jest to produkt zx
iy
w ten sposóbx 10&#.inv@* y
uzyskuje się bazowym 10 przedstawienie produktux
iy
.x # y
kopiuje n- ty elementy
tak często, jak n- ty elementx
; kiedyx
jest wektorem wartości logicznych,x
wybiera, które przedmiotyy
wziąć. Na przykład1 0 1 0 # 1 2 3 4
daje1 3
.* y
otrzymano signum sięy
.x u~ y
jest zwrotna odu
, czyli taki sam jaky u x
.y #~ * y
uzyskuje się wektor wszystkich elementów,y
które są dodatnie. W milczącej notacji można to zapisać za pomocą haka jako(#~ *)
.{: y
daje ostatni element wy
.([:{:@(#~*)10&#.inv@*)
.u/ y
Jest to zmniejszenie oy
, to znaczy dwójkowym czasowniku
wstawione pomiędzy elementamiy
. Na przykład+/1 2 3 4
jest podobny1 + 2 + 3 + 4
i daje10
.([:{:@(#~*)10&#.inv@*)/ y
zwraca ostatnią cyfrę iloczynu pozycjiy
.ARGV
jest zapakowanym wektorem argumentów wiersza poleceń.".>{:ARGV
jest ostatnim argumentem rozpakowanym i interpretowanym jako liczba.i. y
oblicza liczby naturalne od0
doy - 1
.1+i. y
uzyskuje się liczby naturalne od1
doy
. Mógłbym również użyć>:
przyrostu tutaj, ale1+
jest jaśniejszy przy tym samym koszcie postaci.1+i.".>{:ARGV
(wektor1
do liczby w ostatnim argumencie wiersza poleceń) do czasownika([:{:@(#~*)10&#.inv@*)/
i wypisuje wynik za pomocąecho
.źródło
Pyt , 5 bajtów
Wyjaśnienie:
Wypróbuj online!
źródło
R ,
63555146 bajtówOblicza silnię, wyodrębnia ostatnią niezerową cyfrę. Dzięki Giuseppe za zapewnienie podstawowej struktury.
Wypróbuj online!
Alternatywnie, moja stara 51-bajtowa odpowiedź:
Oblicza silnię, konwertuje na postać, usuwa wszystkie
0
s, a następnie przyjmuje końcowy znak. Zaoszczędzono 2 bajty dzięki Giuseppe.Wypróbuj online!
źródło
gamma(x+1)
jest krótszy niżfactorial(x)
(y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]
54 bajty.nchar(x)
z1e5
rozwiązania 46-bajtowy! Miło się dzieje.> <> , 25 bajtów
Wypróbuj online!
Obsługuje 0! również poprawnie. Wartość przekazana przez
-v
flagę.źródło
1000
nie generuje żadnych wyników w TIO - co jest nie tak?Perl 6 ,
2635 bajtówSpróbuj
Jako pełny program:
Spróbuj
Rozszerzony:
źródło
C (gcc) , 72 bajty (funkcja)
Wypróbuj online!
C (gcc) ,
10199 bajtów (cały program)Wypróbuj online!
To pytanie jest po prostu nieśmiałe od 8 lat, więc „rozsądna maszyna” nie jest już taka sama jak wtedy, ale otrzymuję czasy ~ 0,01 sekundy na moim komputerze, kiedy wykonuję wszystkie przypadki testowe razem, więc chyba, że komputery przyspieszyły 1000 razy w ciągu ostatniej dekady powinno być w porządku.
źródło
Dodaj ++ , 11 bajtów
Wypróbuj online!
źródło
Attache , 26 bajtów
Wypróbuj online!
Wyjaśnienie
Jest to kompozycja 4 funkcji:
`!
- jest to funkcjonalna wersja operatora silniDigits
- otrzymuje cyfry silni\&:(All@V)
- To jest funkcja wyboru. Działa poprzez zostawienie spojenia (&:
) funkcjiAll@V
do\
, co wybrać. Z koleiAll@V
jest krótkim sposobem sprawdzenia, czy liczba nie jest równa 0. Działa poprzez rzutowanie danych wejściowych na wektor,0 -> [0]
a następnie sprawdzanie, czy wszystkie te elementy są zgodne z prawdą (tj. Nie 0). Daje to cyfry liczby bez zer.Last
- to po prostu uzyskuje ostatniego członka tej tablicy.źródło
APL (Dyalog Unicode) ,
1815 bajtówWypróbuj online!
Funkcja ukrytego przedrostka. Zwraca poprawną cyfrę dla pojedynczego przypadku testowego lub ciąg cyfr dla wielu przypadków testowych.
Dzięki @ Adám i @ErikTheOutgolfer za 3 bajty każdy.
W jaki sposób?
źródło
APL NARS, 28 bajtów, 14 znaków
Nie wiem dlaczego, ale ten test zdał:
źródło
AWK ,
4757 bajtówWypróbuj online!
Oryginalne rozwiązanie nie radziło sobie dobrze z „dużymi” wartościami wejściowymi. Można dodać,
-M
aby zmusić go do działania, ale wymaga to również dużo więcej czasu przetwarzania.źródło
inf
nie%
bardzo dobrze. :(Japt , 6 bajtów
Wymyśliłem kilka różnych 6-bajtowych, ale ten najbardziej mi się podobał. Jestem jednak przekonany, że musi być sposób, aby to zrobić w 5.
Spróbuj
Wyjaśnienie
Ê
oblicza silnię danych wejściowych,s
konwertuje ją na ciąg znaków i wraca do liczby całkowitej pow
odwróceniu go,ì
konwertuje wynik na tablicę cyfr iv
zwraca pierwszy element.Alternatywy
źródło
Perl 5 , 36 + 10 (
-p -Mbigint
) = 46 bajtówWypróbuj online!
źródło
f
(powinno być 4 ) i 100 ⇒7
(powinno być 4 )