Если в качестве входных данных задано целое число 1 ≤ N ≤ 1 000 000 , выведите последнюю ненулевую цифру N! где ! является факториалом (произведение всех чисел от 1 до N включительно). Это последовательность OEIS A008904 .
Ваша программа должна завершиться в течение 10 секунд на приемлемой машине для любого допустимого ввода.
Тестовые случаи
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
Это код-гольф, поэтому выигрывает самый короткий код в байтах!
Ответы:
Рубин - 63 символа
Источник - http://oeis.org/A008904
Обрабатывает до тысячи цифр за секунду.
Тест
источник
Mathematica,
4536 байтОчень читабельный для победного ответа. :) (Опять же, пока еще нет заявки от GolfScript & Co.)
Это обрабатывает ввод 1 000 000 примерно за 5 секунд на моей машине.
источник
Питон - 75
источник
PARI / GP - 27 байт
Это меняет скорость на размер - тестовый сценарий занимает много времени (~ 6 секунд).
Эта версия намного быстрее (~ 15 микросекунд), но занимает 81 байт:
Вы можете использовать этот код (не для игры в гольф) для проверки:
источник
Windows PowerShell, 53
565960637390Заметки:
История:
$input
в строку; приведение кint
применяется неявно.источник
Perl, 53
5861символыВсе пробелы могут быть удалены, но я оставил их для «читабельности». Примечание: не использовать какую-то глупую явную формулу от Слоана.
Вычисляет f (10 ^ 6) за 8,7 секунд на моей машине.
Обновление : OP хотел, чтобы это была целая программа:
Это делает его 55 символами.
источник
CJam - 28
Вы можете попробовать это на http://cjam.aditsu.net/ для значений до 10000 или около того; для больших чисел вы должны использовать Java-интерпретатор . 1000000 работает примерно на 3 секунды на моем ноутбуке.
Объяснение:
К сожалению, простое решение слишком медленное, поэтому я сохраняю только последние 7 цифр (перед конечными нулями) после каждого умножения.
Примечание: этот язык намного новее, чем вопрос.
источник
Mathematica, 34 байта
источник
05AB1E , 4 байта
Попробуйте онлайн!
объяснение
источник
Желе , 4 байта
Попробуйте онлайн!
объяснение
Использует тот факт, что когда
Ṛ
(инвертировать список; не векторизовать) применяется к целому числу, оно автоматически беретD
(цифры) в первую очередь.С входом 8:
Я не думаю, что существует однобайтовый «первый истинный элемент» (который
ȯ/
действует как), но если он есть, его можно сократить до трех байтов.источник
Java (OpenJDK 8) , 62 байта
Попробуйте онлайн!
Похож на @Kevin Cruijssen, но экономит 5 байтов, комбинируя циклы.
источник
||
на|
, и дополнительный байт, заменив==0
на<1
. Приятного пребывания!C
150140135 байтовЭто версия для систем ASCII; замените строку
33436
на11214
для системы EBCDIC или на\1\1\2\1\4
для переносимой программы.Решения C немного затруднены требованием предоставить полную программу; однако это полностью отвечает на вопрос.
Попробуйте онлайн (требуется Javascript):
объяснение
Он основан на алгоритме, описанном в наименее значимой ненулевой цифре n! Обернулся, чтобы мы вернулись, чтобы найти наибольшую силу пяти, и выполним расчет на выходе. Таблицы констант были слишком большими, поэтому я сократил их, найдя взаимосвязь между предыдущим остатком
r
, текущей цифройd
и глубиной рекурсииk
:Для
r>0
, это решает постоянныеr
времена2^dk
(мод 5); константы указаныa[]
ниже (указано в коде для игры в гольф). Мы также наблюдаем, что(2^4)%5
это 1, поэтому мы можем уменьшить показатель степени, чтобы избежать переполнения диапазонаint
.тесты:
Производительность тоже респектабельная. Вот максимальный вход для системы с 32-битным
int
:Я получил те же тайминги с максимальной 64-битной
int
тоже.источник
2147483647!
нем более 19 миллиардов цифр и(2^63-1)!
более 170 000 000 000 000 000 000 цифр, так что это большой выигрыш в расчете факториалов.1000000!
как указано в вопросе возможно рассчитать на текущем оборудовании; это только 5 с половиной миллионов цифр. :-)PHP - 105
Запускается менее 10 секунд с данным тестовым сценарием.
источник
python3
239 символовМожет сделать 10000 за ~ 3,2 секунды (Ideone отключает меня за 8 секунд, но я уверен, что это займет больше времени, чем 10 секунд :()
python2.6
299 символов (немного быстрее)источник
Хаскель, 78 персонажей
(Вероятно, потребуется скомпилировать для вычисления 1 000 000! За 10 секунд).
источник
foldl1
наproduct
(см. Codegolf.stackexchange.com/questions/607/find-the-factorial/… ). Но вы действительно пробовали с 1000000! ?J -
4240 знаковЦелая программа. Сохраните эту программу в файле и запустите
jconsole script.ijs 1234
. Обратите внимание, что эта программа не выходит из интерпретатора после печати результата. Введите^D
или,exit]0
чтобы выйти из интерпретатора.Вот объяснение:
x #. y
интерпретирует целочисленный векторy
как базовоеx
число; например,10 #. 1 2 3 4
урожайность1234
.u inv
дает инверсию глаголаu
. В частности,x #. inv y
представляетy
собой базовоеx
число; например,10 #. 1234
урожайность1 2 3 4
. Обратите внимание , чтоinv
определяется как^:_1
, то есть,u
применяется -1 раз.x * y
это продукт изx
иy
, таким образом ,x 10&#.inv@* y
дает представление основанию 10 из продуктаx
иy
.x # y
копирует n-й элементy
так же часто, как n-й элементx
; whenx
- вектор логических значений,x
выбирает, какие элементыy
взять. Например,1 0 1 0 # 1 2 3 4
урожайность1 3
.* y
дает Signum изy
.x u~ y
является рефлексивный изu
, то есть такой же , какy u x
.y #~ * y
дает вектор всех элементов,y
которые являются положительными. В молчаливом обозначении это может быть написано с крючком как(#~ *)
.{: y
дает последний элемент вy
.([:{:@(#~*)10&#.inv@*)
.u/ y
это сокращение отy
, то есть, двоичного глаголu
вставляется между элементамиy
. Например,+/1 2 3 4
это как1 + 2 + 3 + 4
и дает10
.([:{:@(#~*)10&#.inv@*)/ y
дает последнюю цифру произведения пунктовy
.ARGV
в штучной упаковке вектор аргументов командной строки.".>{:ARGV
последний аргумент распакован и интерпретируется как число.i. y
вычисляет натуральные числа от0
доy - 1
.1+i. y
дает натуральные числа от1
доy
. Я мог бы также использовать>:
приращение здесь, но1+
это более понятно при той же стоимости символов.1+i.".>{:ARGV
(вектор1
к числу в последнем аргументе командной строки) к глаголу([:{:@(#~*)10&#.inv@*)/
и печатает результат сecho
.источник
Пыть , 5 байт
Объяснение:
Попробуйте онлайн!
источник
R ,
63555146 байтВычисляет факториал, извлекает последнюю ненулевую цифру. Спасибо Джузеппе за предоставление базовой структуры.
Попробуйте онлайн!
В качестве альтернативы мой старый 51-байтовый ответ:
Вычисляет факториал, преобразует в символ, удаляет все
0
s, а затем принимает последний символ. Сохранено 2 байта благодаря Джузеппе.Попробуйте онлайн!
источник
gamma(x+1)
короче чемfactorial(x)
(y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]
54 байта.nchar(x)
с1e5
для раствора 46 байт! Хорошо идет.> <> , 25 байт
Попробуйте онлайн!
Ручки 0! правильно также. Значение передается через
-v
флаг.источник
1000
не дает никакого вывода на TIO - что не так?Perl 6 ,
2635 байтПопытайся
Как полная программа:
Попытайся
Expanded:
источник
C (gcc) , 72 байта (функция)
Попробуйте онлайн!
C (gcc) ,
10199 байт (вся программа)Попробуйте онлайн!
Этот вопрос просто стесняется 8 лет, поэтому «разумная машина» - не то же самое, что было тогда, но я получаю время ~ 0,01 секунды на моем компьютере при выполнении всех тестовых случаев вместе, так что, если скорость компьютеров не увеличилась в 1000 раз за последнее десятилетие все должно быть хорошо.
источник
Добавить ++ , 11 байт
Попробуйте онлайн!
источник
Атташе , 26 байт
Попробуйте онлайн!
объяснение
Это композиция из 4 функций:
`!
- это функциональная версия факториального оператораDigits
- это получает цифры факториала\&:(All@V)
- Это функция выбора. Он работает путем левого соединения (&:
) функцииAll@V
к\
, что выбрать. В свою очередь,All@V
это короткий способ проверки, если число не равно 0. Он работает путем приведения своего ввода к вектору0 -> [0]
затем запрашивая, являются ли все эти члены истинными (то есть, не 0). Это дает цифры номера без 0s.Last
- это просто получает последний член этого массива.источник
APL (Dyalog Unicode) ,
1815 байтПопробуйте онлайн!
Функция молчаливого префикса. Возвращает правильную цифру для одного контрольного примера или строку цифр для нескольких контрольных примеров.
Спасибо @ Adám и @ErikTheOutgolfer за 3 байта каждый.
Как?
источник
APL NARS, 28 байтов, 14 символов
Я не знаю, почему, но это пройти тест:
источник
AWK ,
4757 байтПопробуйте онлайн!
Исходное решение не очень хорошо обрабатывало «большие» входные значения. Можно добавить,
-M
чтобы заставить его работать, но это также требует гораздо больше времени обработки.источник
inf
не%
очень хорошо. :(Japt , 6 байт
Придумал несколько разных 6-байтовых символов, но этот мне понравился больше всего. Я уверен, что должен быть способ сделать это в 5, хотя.
Попытайся
объяснение
Ê
вычисляет факториал входных данных,s
преобразует его в строку и обратно в целое число после того,w
как перевернул его,ì
преобразует результат в массив цифр иv
возвращает первый элемент.альтернативы
источник
Perl 5 , 36 + 10 (
-p -Mbigint
) = 46 байтПопробуйте онлайн!
источник
f
(должно быть 4 ) и 100 ⇒7
(должно быть 4 )