Повторные! Факториалы!

34

Не путайте с Find the factorial!

Введение

Факториал целого числа nможно вычислить как

n!=n×(n1)×(n2)×(...)×2×1

Это относительно просто и ничего нового. Тем не менее, факториалы могут быть расширены до двойных факториалов , таких что для четных чисел и для нечетных чисел. Но мы не ограничены двойными факториалами. Например, или или зависимости от начальное значение.

n!!=n×(n2)×(n4)×(...)×4×2
n!!=n×(n2)×(n4)×(...)×3×1
n!!!=n×(n3)×(n6)×(...)×6×3
n!!!=n×(n3)×(n6)×(...)×5×2
n!!!=n×(n3)×(n6)×(...)×4×1

В итоге: где Или, на простом английском: вычитайте факториальное число из базового числа многократно и умножьте все получающиеся натуральные числа.

n!(k)={1if n=0nif 0<nkn((nk)!(k))if n>k
n!(k)=n!!k

Соревнование

Напишите функцию, которая будет вычислять любой вид повторяющегося факториала для любого неотрицательного целого числа.

вход

Или

  • Строка, содержащая неотрицательное целое число от основания до десяти, за которым следует 1 или более восклицательных знаков. Например, "6!"или "9!!"или "40!!!!!!!!!!!!!!!!!!!!".

или

  • Одинаковые значения представлены двумя целыми числами: одно неотрицательное базовое значение и одно положительное значение, представляющее счет факториала. Это можно сделать в соответствии с любым форматом из правил ввода / вывода по умолчанию.

Выход

Результат указанного расчета.

Вызов замечания

  • 0!равно 1по определению. Ваш код должен учитывать это.
  • Количество факториалов ограничено значением за пределами этого диапазона, вы можете выводить все что угодно. Кроме того , что является единственным исключением из этого правила.
    0<factorial countbase value
    0!

Примеры

Input                              Output

3!!!                               3
0!                                 1
6!                                 720
9!!                                945
10!!!!!!!!                         20
40!!!!!!!!!!!!!!!!!!!!             800
420!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  41697106428257280000000000000000

Попробуй это с незакрытой реализацией Python: попробуй онлайн!

Основные пометки

Jitse
источник
6
Список примеров, 0!но примечания к вызову говорят, что факториальное число будет меньше или равно базовому значению.
Джонатан Аллан
1
Не 3 быть нулем? n * (n-3) = 3 * (3-3) = 0.
ouflak
2
@ouflak Если это работает как 1 !, не совсем. Это больше похоже на 1! = 1. 2 !! = 2. 3 !!! = 3. Там нет расчета, потому что вы находитесь в конце рекурсивности. Нет 0 в продуктах, иначе каждый факториал в конце упал бы до 0.
В. Куртуа
4
3!!!!!!!не должно быть неопределенным - оно должно просто дать ответ 3. Это так же, как 1!!=1(не определено). Также в вашей входной спецификации сказано, что всегда будет хотя бы один !, поэтому первый пример 3не соответствует спецификации.
Грег Мартин
3
@ FabianRöling: Но это не то, что это. Это не (3!)!вместо этого, это удаляет термины из факториала. Это вводящее в заблуждение имя; Я пришел к выводу, что он будет неоднократно применять факториальную функцию в цепочке, и мне пришлось внимательно прочитать, чтобы увидеть, что это на самом деле. К счастью, вопрос объясняет это ясно. Лучшее имя может быть факториал шага или факториал шага или что-то.
Питер Кордес

Ответы:

13

ArnoldC , 702 698 634 байта

LISTEN TO ME VERY CAREFULLY f
I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE n
I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE p
GIVE THESE PEOPLE AIR
HEY CHRISTMAS TREE r
YOU SET US UP 1
HEY CHRISTMAS TREE c
YOU SET US UP 0
STICK AROUND n
GET TO THE CHOPPER r
HERE IS MY INVITATION r
YOU'RE FIRED n
ENOUGH TALK
GET TO THE CHOPPER n
HERE IS MY INVITATION n
GET DOWN p
ENOUGH TALK
GET TO THE CHOPPER c
HERE IS MY INVITATION 0
LET OFF SOME STEAM BENNET n
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE c
GET TO THE CHOPPER n
HERE IS MY INVITATION 0
ENOUGH TALK
YOU HAVE NO RESPECT FOR LOGIC
CHILL
I'LL BE BACK r
HASTA LA VISTA, BABY

Попробуйте онлайн!

Переведено в псевдокод:

f(n,p) {
  r=1;
  c=0;
  while (n) {
    r=r*n;
    n=n-p;
    c=n<0;
    if (c) n=0;
  }
  return r;
}

Примечание: ArnoldC имеет только один тип данных: 16-разрядное целое число со знаком. Поэтому я не могу проверить 420!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!случай.

Чарли
источник
Просто любопытно о вашем psuedocode. Для чего нужна переменная 'c'?
ouflak
@ouflak Я пару раз редактировал свой ответ и забыл его. cПеременная фактически сохраняет значение сравнения между nи 0.
Чарли
+1 и я заимствовал его (минус «с») для моего ответа LUA.
ouflak
12

Желе , 4 байта

RṚmP

Попробуйте онлайн!

Как? Учитывая и , он сначала генерирует диапазон (с ), затем вместе с ним сохраняет каждый элемент этого диапазона (поэтому ) и, наконец, умножает их, используя .nkn,,1k th n , n - k , n - 2 k , , n - n / k kRṚmkthn,nk,n2k,,nn/kkP

Мистер Xcoder
источник
Работает хорошо, и так просто в конце. Я совсем не знаю желе, но, по крайней мере, это выглядит хорошо :)
V. Courtois
1
@ V.Courtois Учитывая и , он сначала генерирует диапазон (с ), затем вместе с ним сохраняет каждый элемент этого диапазона (поэтому ) и, наконец, умножает их, используя . Просто прямой подход. Изменить: я добавил это объяснение в ответе. k n , , 1 k th n , n - k , n - 2 k , , n - n / k knkn,,1RṚmkthn,nk,n2k,,nn/kkP
г-н Xcoder
Ха, спасибо тебе большое. Однажды я, возможно, захочу поиграть в гольф на этом языке, поэтому мне придется выучить эти монады, диады и т. Д.
В. Куртуа
Альтернативные , который выглядит как CJam: r1mP.
Эрик Outgolfer
1
@KyeWShi Jelly имеет собственную кодовую страницу , поэтому каждый из 256 символов, которые он содержит, кодируется как 1 байт.
г-н Xcoder
8

APL (Dyalog Extended) , 7 байтов SBCS

Функция анонимного молчаливого префикса. Принимает в [n,b]качестве аргумента.

×/-\…1¨

Попробуйте онлайн!

 по одному на каждый элемент аргумента; [1,1]

-\ накопленная разница; [n,n-b]

 диапазон с использованием второго элемента левого аргумента в качестве индикатора шага, например, [9,7]продолжается с5

×/ продукт

Адам
источник
7

Haskell , 21 байт

n%a=product[n,n-a..1]

Попробуйте онлайн!

Объединение встроенной функции продукта с пошаговым перечислением диапазонов превосходит то, что я мог бы кодировать рекурсивно (даже при использовании flawr, сохраняющего байт).

22 байта

n%a|n<1=1|m<-n-a=n*m%a

Попробуйте онлайн!

Вот решение, принимающее ввод в строковом формате, например 9!!, которое мне кажется более интересным.

42 байта

(\[(n,a)]->product[n,n-length a..1]).reads

Попробуйте онлайн!

XNOR
источник
2
Я думаю, что вы могли бы сократить рекурсивное решение доn%a|n<1=1|m<-n-a=n*m%a
flawr
5

Пробел , 91 байт

[S S S T    N
Push_1][S N
S _Duplicate_1][S N
S _Duplicate_1][T   N
T   T   _Read_STDIN_as_integer_(base)][T    T   T   _Retrieve_base][S S S N
_Push_0][T  N
T   T   _Read_STDIN_as_integer_(factorial)][N
S S N
_Create_Label_LOOP][S N
S _Duplicate_base][S S S T  N
_Push_1][T  S S T   _Subtract][N
T   T   S N
_If_negative_jump_to_Label_PRINT_RESULT][S N
S _Duplicate_base][S T  S S T   S N
_Copy_0-based_2nd_(result)][T   S S N
_Multiply][S N
T   _Swap_top_two][S S S N
_Push_0][T  T   T   _Retrieve_factorial][T  S S T   _Subtract][N
S N
N
_Jump_to_Label_LOOP][N
S S S N
_Create_Label_PRINT_RESULT][S N
N
_Discard_top][T N
S T _Print_result_as_integer]

Буквы S(пробел), T(табуляция) и N(новая строка) добавляются только как подсветка.
[..._some_action]добавлено только в качестве объяснения.

Попробуйте онлайн (только с необработанными пробелами, вкладками и новыми строками).

Объяснение в псевдокоде:

Integer result = 1
Integer base = STDIN as integer
Integer factorial = STDIN as integer
Start LOOP:
  If(base <= 0):
    Call function PRINT_RESULT
  result = result * base
  base = base - factorial
  Go to next iteration of LOOP

function PRINT_RESULT:
  Print result as integer to STDOUT
Кевин Круйссен
источник
4

Perl 6 , 22 байта

{[*] $^a,*-$^b...^1>*}

Попробуйте онлайн!

Анонимный кодовый блок, который возвращает произведение диапазона, начиная с первого ввода, с уменьшением на второй, пока не станет ниже 1, за исключением последнего числа. Это работает 0, поскольку базовый случай уменьшения на произведение равен 1, поэтому выходной результат равен 1.

Джо Кинг
источник
4

05AB1E , 10 8 7 байт

ݦRIιнP

Ввод как два отдельных входа: первый вход base; вторым входом является factorial.

Попробуйте онлайн или проверьте все контрольные примеры .

-2 байта благодаря @ Mr.Xcoder .
-1 байт благодаря @JonathanAllan .

Объяснение:

Ý        # Create a list in the range [0, (implicit) base-input]
 ¦       # And remove the first item to make it the range [1, base]
         # (NOTE: this is for the edge case 0. For the other test cases simply `L` instead
         #  of `ݦ` is enough.)
  R      # Reverse this list so the range is [base, 1]
   Iι    # Uninterleave with the second input as step-size
         #  i.e. base=3, factorial=7: [[3],[2],[1],[],[],[],[]]
         #  i.e. base=10, factorial=8: [[10,2],[9,1],[8],[7],[6],[5],[4],[3]]
         #  i.e. base=420, factorial=30: [[420,390,360,...,90,60,30],[419,389,359,...],...]
     н   # Only leave the first inner list
      P  # And take the product of its values
         # (which is output implicitly as result)

Оригинальный 10- байтовый ответ:

L0KD¤-IÖÏP

Ввод как два отдельных входа: первый вход base; вторым входом является factorial.

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

L           # Create a list in the range [1, (implicit) base-input]
 0K         # Remove all 0s (edge case for input 0, which will become the list [1,0])
   D        # Duplicate this list
    ¤       # Get the last value (without popping)
            # (could also be `Z` or `¹` for max_without_popping / first input respectively)
     -      # Subtract it from each item in the list
      IÖ    # Check for each if they're divisible by the second factorial-input
        Ï   # In the list we copied, only leave the values at the truthy indices
         P  # And take the product of those
            # (which is output implicitly as result)
Кевин Круйссен
источник
1
Этот 6-байтовый код: LR²ιнP( Попробуйте онлайн! ) Работает для каждого теста, кроме 0.
Мистер Xcoder
Но я думаю, что 0 регистр может быть исправлен не более чем в 2 байта. Если вы найдете способ исправить это, вы можете взять его :) РЕДАКТИРОВАТЬ: Возможно LR²ιн0KPдля 8 байтов?
г-н Xcoder
@ Mr.Xcoder Хороший ответ! Никогда даже не использовал uninterleave с заданным шагом. :)
Кевин Круйссен
0Kдолжно быть ненужным, так как 0!это неверный ввод в спецификации (даже если он включен в примеры) - я прокомментировал это.
Джонатан Аллан
1
... а если 0! во входном домене ݦRXιнPсохраняет байт.
Джонатан Аллан
4

машинный код x86-64, 12 байт

Тот же машинный код делает то же самое в 32-битном режиме и для 16-битных целых в 16-битном режиме.

Это функция, вызываемая с арг n=RCX, k=ESI. 32-битное возвращаемое значение в EAX.

Вызывается из C с помощью соглашения о вызовах System V x86-64 с фиктивными аргументами, чтобы получить реальные аргументы в правильные регистры. uint32_t factk(int, uint32_t k, int, uint64_t n); Я не мог просто использовать Windows x64, потому что 1- mulоперандный клоббер RDX, и мы не хотим, чтобы префиксы REX имели доступ к R8 / R9. nне должно быть никакого мусора в старших 32 битах, чтобы JRCXZ работал, но кроме этого он все 32-битный.

Список NASM (относительный адрес, машинный код, источник)

 1                         factk:
 2 00000000 6A01             push 1
 3 00000002 58               pop rax             ; retval = 1
 4 00000003 E306             jrcxz  .n_zero      ; if (n==0) return
 5                         .loop:                ; do {
 6 00000005 F7E1              mul   ecx            ; retval *= n  (clobbering RDX)
 7 00000007 29F1              sub   ecx, esi       ; n -= k
 8 00000009 77FA              ja   .loop         ; }while(sub didn't wrap or give zero)
 9                         .n_zero:
10 0000000B C3               ret

0xc = 12 байт


Или 10 байтов, если нам не нужно обрабатывать n=0особый случай, исключая jrcxz.

Для стандартного факториала вы бы использовали loopвместо sub / ja, чтобы сохранить 2 байта, но в остальном точно такой же код.


Тест вызывающего абонента, который проходит argcкак k, с nжестко закодированным.

align 16
global _start
_start:
  mov  esi, [rsp]
;main:
  mov  ecx, 9
  call factk

  mov  esi, eax
  mov  edx, eax
  lea  rdi, [rel print_format]
  xor  eax, eax
extern printf
  call printf
extern exit
  call exit

section .rodata
print_format: db `%#x\t%u\n`

```
Питер Кордес
источник
3

APL (Dyalog Unicode) , 11 байтов SBCS

Анонимная молчаливая инфиксная функция. Принимает в nкачестве правого аргумента и в bкачестве левого аргумента.

×/1⌈⊢,⊢-×∘⍳

Попробуйте онлайн!

×∘⍳ кратно bпо ɩ ntegers 1 черезn

⊢- вычесть это из n

⊢, перед именем n

1⌈ максимум одного и каждого из тех

×/ продукт

Адам
источник
3

Wolfram Language (Mathematica) , 22 21 байт

1##&@@Range[#,1,-#2]&

Попробуйте онлайн!

-1 благодаря attinat: Times --> 1##&

Объяснение: используйте, Rangeчтобы составить список значений {n, n-k, n-2k, n-3k, ...}, останавливаясь перед тем, как опуститься ниже 1 (то есть останавливаясь как раз вправо). Затем умножьте все числа в этом списке на Times(или 1##&).

Римский
источник
-1 байт с 1##&вместоTimes
attinat
3

Java 10, 44 байта

f->b->{int r=1;for(;b>0;b-=f)r*=b;return r;}

Принимает факториал в качестве первого ввода, а базу в качестве второго.

Попробуйте онлайн.

Это выше не работает для самого большого тестового случая из-за ограниченного целочисленного диапазона (32 бита). Чтобы исправить это , мы можем использовать BigIntegers, который по совпадению является именно двойной размер - 88 79 байт :

f->b->{var r=f.ONE;for(;b.signum()>0;b=b.subtract(f))r=r.multiply(b);return r;}

-9 байт благодаря @ OlivierGrégoire .

Попробуйте онлайн.

Объяснение:

f->b->{       // Method with two integer parameters and integer return-type
  int r=1;    //  Result-integer, starting at 1
  for(;b>0;   //  Loop as long as the base is still larger than 0
      b-=f)   //    After every iteration: decrease the base by the factorial
    r*=b;     //   Multiply the result by the base
  return r;}  //  Return the result
Кевин Круйссен
источник
@ OlivierGrégoire Np, и спасибо! :)
Кевин Круйссен
2

Japt , 8 байт

TõUV f ×

Попытайся

-1 Спасибо EoI за то, что он глупый без кофеина Шегги!

мохнатый
источник
kTможно заменить fна 1 байт
Воплощение невежества
1
@EmbodimentofIgnorance, конечно, может! Я знал, что это было слишком рано для гольфа! : \
Лохматый
2

MathGolf , 7 6 байтов

╙╒x%ε*

Попробуйте онлайн!

Нашел умный способ справиться с 0! без изменения других тестовых случаев. Принимает ввод как k n(обратный порядок), который помогает с неявным появлением.

объяснение

╙        maximum of two elements (pops largest of k and n,
         which is n for every valid case except 0!, where 1 is pushed)
 ╒       range(1,n+1)
  x      reverse int/array/string
   %     slice every k:th element
    ε*   reduce list with multiplication
maxb
источник
2

Атташе , 21 19 байт

${x<y∨x*$[x-y,y]}

Попробуйте онлайн! Довольно прямая рекурсивная реализация. (Примечание: trueпо сути 1, так как его можно использовать в арифметических операциях, как 1.) Это одна из немногих программ, которые я написал для этого сайта, где использование оператора Юникод сохраняет байты (1, если быть точным).

альтернативы

20 байтов: ${x<y or x*$[x-y,y]}

21 байт: Prod@${{_%y=x%y}\1:x}

27 байт: ${x*[`1,$][x>y][x-y,y]∨1}

27 байт: ${If[x>y,x*$[x-y,y],_or 1]}

27 байт: ${x*[`1,$][x>y][x-y,y]or 1}

29 байт: ${If[x>y,x*$[x-y,y],_+not _]}

Конор О'Брайен
источник
2

Ржавчина , 92 73 61 байт

fn f(n:i128,k:i128)->i128{if n<=0{return 1}return n*f(n-k,k)}

Я только начинаю изучать ржавчину, поэтому я уверен, что это может быть короче. Буду обновлять по мере того как я учу. Возвращаемое значение должно быть i128для того, чтобы вычислить последний тест.

Изменить: рекурсия короче.

Попробуйте онлайн!

Вы можете добавить свой собственный тест или отредактировать один из уже существующих.

emilanov
источник
2

q , 59 57 55 53 байта

{prd 2+(&)1_i=last i:("J"$x(&)not[n])#(!)sum n:"!"=x}

объяснение:

q)x:"12!!" / let our input be 12!!, assign to x
q)sum n:"!"=x / count "!"s
2i
q)(!)sum n:"!"=x / (!)m -> [0,m)
0 1
q)("J"$x(&)not[n]) / isolate the number in input
12
q)("J"$x(&)not[n])#(!)sum n:"!"=x / x#y means take x items from list y, if x>y, circle around
0 1 0 1 0 1 0 1 0 1 0 1
q)i:("J"$x(&)not[n])#(!)sum n:"!"=x / assign to i
q)i
0 1 0 1 0 1 0 1 0 1 0 1
q)(last i)=i:("J"$x(&)not[n])#(!)sum n:"!"=x / take last elem of i and see which are equal in i
010101010101b
q)1_(last i)=i:("J"$x(&)not[n])#(!)sum n:"!"=x / drop first elem
10101010101b
q)(&)1_(last i)=i:("J"$x(&)not[n])#(!)sum n:"!"=x / indices of 1b (boolean TRUE)
0 2 4 6 8 10
q)2+(&)1_(last i)=i:("J"$x(&)not[n])#(!)sum n:"!"=x / add 2 across array
2 4 6 8 10 12
q)prd 2+(&)1_(last i)=i:("J"$x(&)not[n])#(!)sum n:"!"=x / product across array
46080

здесь также есть версия в k (та же логика), 42 41 байт

{*/2+&1_i=last i:("J"$x@&~:n)#!+/n:"!"=x}
каракули
источник
Добро пожаловать на сайт! Я добавил в ваш пост форматирование кода, которое можно сделать с четырьмя пробелами перед строкой или заключив его в тройные обратные кавычки.
Пшеничный волшебник
@ SriotchilismO'Zaic спасибо :-)
каракули
1
Я рекомендую добавить объяснение и, возможно, ссылку на онлайн-переводчика, такого как TIO . Ответы только для кода обычно автоматически помечаются как некачественные.
mbomb007
@ mbomb007 интересно. есть ли бот, отмечающий ответы? что происходит с некачественными материалами? скоро обновлю!
каракули
Да, есть бот. StackExchange использует ботов для поиска потенциального спама и низкого качества ответов. Люди с достаточно высокой репутацией могут просматривать Очередь просмотра. meta.stackexchange.com/a/161391/285610
mbomb007,
1

Сетчатка , 66 байт

^0
1
\d+
*!,
+`(!+)(!+),\1$
$1$2,$2,$1
!+$
1
+`(!+),(\d+)
$.($2*$1

Попробуйте онлайн! Ссылка включает в себя более быстрые тестовые случаи. Молс номера без восклицательных знаков. Объяснение:

^0
1

Исправить 0!.

\d+
*!,

Преобразовать nв одинарный и добавить разделитель.

+`(!+)(!+),\1$
$1$2,$2,$1

Несколько раз вычесть kиз в nто время n>k, и собрать результаты.

!+$
1

Заменить kна 1(в десятичном виде).

+`(!+),(\d+)
$.($2*$1

Умножьте на каждое промежуточное значение по очереди, преобразовав в десятичное число.

Нил
источник
1

Forth (gforth) , 50 байтов

: f 1 1 2over / 1+ 0 do 2over i * - 1 max * loop ;

Попробуйте онлайн!

Код Объяснение

: f                \ start a new word definition
  1 1              \ add placeholder and accumulator to stack
  2over / 1+       \ get the number of times to run the loop (num/factorial + 1)
  0 do             \ start loop from 0 to num/factorial
    2over          \ copy num and factorial to the top of the stack
    i * -          \ get the current number to multiply by (num - factorial * i)
    1 max          \ make sure it can't be 0 or negative [set to 1 if it is]
    *              \ multiply accumulator by result
  loop             \ end loop
;                  \ end the word definition           
reffu
источник
1

Gaia , 6 байт

…)¦v%Π

Попробуйте онлайн!

Принимает ввод как n, kтак что ввод 3 4будет 3!!!!.

…	 push [0...n-1], or [] if n == 0
 )¦	 increment each value (does nothing if [])
   v	 reverse list
    %	 take every k'th element
     Π	 product; product([]) = 1.
Giuseppe
источник