Вы должны написать программу или функцию, которая дает три положительных целых числа в n b k
качестве входных данных или возвращает последние k
цифры перед конечными нулями в базовом b
представлении n!
.
пример
n=7 b=5 k=4
factorial(n) is 5040
5040 is 130130 in base 5
the last 4 digits of 130130 before the trailing zeros are 3013
the output is 3013
вход
- 3 натуральных числа
n b k
где2 <= b <= 10
. - Порядок ввода целых чисел может быть выбран произвольно.
Выход
- Список цифр, возвращаемых или выводимых в виде целочисленного или целочисленного списка.
- Ведущие нули необязательны.
- Ваше решение должно разрешить любой пример теста менее чем за минуту на моем компьютере (я буду тестировать только закрытые случаи. У меня компьютер ниже среднего.).
Примеры
Добавлены новые тесты для проверки правильности представлений. (Они не являются частью правила выполнения менее 1 минуты.)
Input => Output (с возможностью опускания ведущих нулей)
3 10 1 => 6
7 5 4 => 3013
3 2 3 => 11
6 2 10 => 101101
9 9 6 => 6127
7 10 4 => 504
758 9 19 => 6645002302217537863
158596 8 20 => 37212476700442254614
359221 2 40 => 1101111111001100010101100000110001110001
New tests:
----------
9 6 3 => 144
10 6 3 => 544
Это код-гольф, поэтому выигрывает самый короткий вход.
7 5 3
выводить «013» или «13»?7 10 4
тестового примера, я бы сказал13
n
илиk
? Или мы можем ограничить их диапазоном целочисленного типа языка?Ответы:
Дьялог АПЛ , 23 байта
Эта программа работает до тех пор, пока факториал не превышает внутренний предел представления. В Dyalog APL предел может быть увеличен на
⎕FR←1287
.Предполагается, что переменные n, b и k были установлены (например
n b k←7 5 4
), но если вы предпочитаете запрашивать n , b и k (в этом порядке), то замените три символа на⎕
.источник
Mathematica,
5748 байтовСохранено 9 байт благодаря @ 2012rcampion.
источник
b
чтобы сэкономить 2 байта?IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&
(и это, и ваш оригинал довольно быстро)SlotSequence
трюк, который я использовал в своем комментарии, работает только с текущим порядком, поэтому вы больше не можете сохранить.Питон,
198192181 символЭто достаточно быстро, ~ 23 секунды на самом большом примере. И никакой факториал встроен (я смотрю на тебя, Mathematica!).
источник
[2,3,2,5,3,7,2,3,5][b-2]
может быть,int('232537235'[b-2])
чтобы сохранить 3 байта.[1,1,2,1,1,1,3,2,1][b-2]
по аналогии.111973>>2*(b-2)&3
еще короче. Это же количество байтов для первого (хотя90946202>>3*(b-2)&7
).Pyth,
2635 байтЭто функция из 3 аргументов, число, основание, количество цифр.
Демонстрация.
Самый медленный тестовый пример, последний, занимает 15 секунд на моей машине.
источник
PARI / GP, 43 байта
Скорость торговли для космоса дает этот простой алгоритм:
Каждый из тестовых случаев выполняется на моей машине менее чем за секунду.
источник
Mathematica - 48 байтов
Ungolfed:
Пример:
Для самых больших случаев ограничивающий фактор не генерирует цифры:
Похоже
O(n^2)
, что сопоставление с образцом приводит к тому , что последние два контрольных примера значительно превышают одну минуту.источник
Bash / coreutils / dc, 60 байт
Использует
dc
скрипт из моего ответа для поиска факториала , выводя в базу$2
,sed
чтобы обрезать конечные нули иtail
выбрать последние$3
цифры.источник
rev
для уменьшения обратного отслеживания, но это то,dc
что съедает процессор ...Haskell,
111109 байтИспользование:
f 158596 8 20
->[3,7,2,1,2,4,7,6,7,0,0,4,4,2,2,5,4,6,1,4]
Занимает около 4 секунд
f 359221 2 40
на моем 4-летнем ноутбуке.Как это работает: сложите умножение (
*
) в список[1..n]
. Преобразуйте каждый промежуточный результат в основаниеb
в виде списка цифр (сначала наименее значимого), уберите начальные нули, затем возьмите первыеk
цифры и снова преобразуйте в основание 10. Наконец,b
снова преобразуйте в базу , но с самой старшей цифрой.источник
Python 3, 146 байт
Я не уверен, что все тестовые случаи будут выполняться достаточно быстро - более крупные - очень медленные (так как они циклически перебирают число).
Попробуйте это онлайн здесь (но будьте осторожны).
источник
Java,
303299296 байтНа моем компьютере это в среднем чуть меньше трети секунды в
359221 2 40
тестовом примере. Принимает ввод через аргументы командной строки.источник
до н.э., 75 байт
Это использует некоторые расширения GNU для уменьшения размера кода; эквивалентный POSIX эквивалент весит 80 байт:
Чтобы сохранить разумное время выполнения, мы обрезаем конечные нули (
while(!x%b)x/=b
) и усекаем до последнихk
цифр (x%=b^k
) при вычислении факториала (for(x=1;n;)x*=n--
).Тестовая программа:
Время выполнения полного набора тестов составляет примерно 4¼ секунды на моей рабочей станции 2006 года выпуска.
источник
bc
программа (гольф или нет), поэтому любые советы особенно приветствуются ...PHP, 80 байт
Используется как
f(359221,2,40)
для последнего контрольного примера. Работает довольно гладко для всех тестовых случаев.Попробуй здесь!
источник