Repetido! Fatoriais!

34

Não confunda com Encontre o fatorial!

Introdução

O fatorial de um número inteiro npode ser calculado por

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

Isso é relativamente fácil e nada de novo. No entanto, os fatoriais podem ser estendidos para fatoriais duplos , de modo que

n!!=n×(n2)×(n4)×(...)×4×2
para números pares, e
n!!=n×(n2)×(n4)×(...)×3×1
para números ímpares. Mas não estamos limitados a fatoriais duplos. Por exemplo
n!!!=n×(n3)×(n6)×(...)×6×3
ou
n!!!=n×(n3)×(n6)×(...)×5×2
ou
n!!!=n×(n3)×(n6)×(...)×4×1
, dependendo do valor de partida.

Em resumo:

n!(k)={1if n=0nif 0<nkn((nk)!(k))if n>k
onde
n!(k)=n!!k
Ou, em inglês simples:Subtraia a contagem fatorial do número base repetidamente e multiplique todos os números inteiros positivos resultantes.

O desafio

Escreva uma função que calcule qualquer tipo de fatorial repetido para qualquer número inteiro não negativo.

Entrada

Ou

  • Uma sequência contendo um número inteiro de base dez não negativo, seguido por 1 ou mais pontos de exclamação. Por exemplo, "6!"ou "9!!"ou "40!!!!!!!!!!!!!!!!!!!!".

ou

  • Os mesmos valores representados por dois números inteiros: um valor base não negativo e um valor positivo representando a contagem fatorial. Isso pode ser feito de acordo com qualquer formato das regras de E / S padrão.

Saída

O resultado do referido cálculo.

Comentários do desafio

  • 0!é igual 1por definição. Seu código deve ser responsável por isso.
  • A contagem factorial é limitado por
    0<factorial countbase value
    fora desta faixa, você está livre para a saída de qualquer outra coisa. Além de 0!, que é a única exceção a esta regra.

Exemplos

Input                              Output

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

Experimente com uma implementação Python não destruída: Experimente online!

Observações gerais

Jitse
fonte
6
Os exemplos listam, 0!mas as observações do desafio dizem que a contagem fatorial será menor ou igual ao valor base.
Jonathan Allan
1
Não seria 3 !!! ser zero? n * (n-3) = 3 * (3-3) = 0.
ouflak
2
@ouflak Se funciona como 1 !, na verdade não. É mais como 1! = 1. 2 !! = 2. 3 !!! = 3. Não há cálculo, porque você está no final da recursividade. Nenhum 0 em produtos; caso contrário, cada fatorial cairá para 0 no final.
V. Courtois
4
3!!!!!!!não deve ser indefinido - deve apenas dar a resposta 3. É o mesmo que 1!!=1(não indefinido). Além disso, sua especificação de entrada diz que sempre haverá pelo menos uma !, portanto o primeiro exemplo 3não se ajusta à especificação.
Greg Martin
3
@ FabianRöling: Mas não é isso que é. Não é (3!)!a remoção de termos de um fatorial. É um nome enganador; Eu assumi que ele aplicaria a função fatorial repetidamente em uma cadeia e tive que ler atentamente para ver o que realmente era. Felizmente, a pergunta explica claramente. Um nome melhor pode ser fatorial de passo ou fatorial de etapa ou algo assim.
Peter Cordes

Respostas:

17

R , 33 bytes

function(n,k)prod(seq(n+!n,1,-k))

Experimente online!

Manipula n=0 adicionando a negação lógica de n .

Nick Kennedy
fonte
13

ArnoldC , 702 698 634 bytes

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

Experimente online!

Traduzido para pseudocódigo:

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

Nota: ArnoldC possui apenas um tipo de dados: número inteiro assinado de 16 bits. Portanto, não posso testar o 420!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!caso.

Charlie
fonte
Apenas curioso sobre o seu código psued. Para que serve a variável 'c'?
ouflak
@ouflak Eu editei minha resposta algumas vezes e esqueci. A cvariável realmente armazena o valor da comparação entre ne 0.
Charlie em
+1 e peguei emprestado (menos o 'c') para a minha resposta LUA.
ouflak
12

Gelatina , 4 bytes

RṚmP

Experimente online!

Quão? Dado n e k , ele primeiro gera o intervalo n,,1 (com RṚ) e, em seguida m, mantém cada kº elemento desse intervalo (então n,n-k,n-2k,,n-n/kk ) e, finalmente, multiplica-os usando P.

Mr. Xcoder
fonte
Funciona bem, e tão simples no final. Eu não conheço Jelly, mas pelo menos parece bom :)
V. Courtois
1
nkn,,1RṚmkth element of this range (so n,nk,n2k,,nn/kk), and finally multiplies them using P. Just the straightforward approach. Edit: I added this explanation in the answer.
Mr. Xcoder
Hah thank you very much. One day I might want to golf in this language so I'll have to learn those monads, dyads etc.
V. Courtois
Alternative that looks like CJam: r1mP.
Erik the Outgolfer
1
@KyeWShi Jelly has its own codepage, so each of the 256 characters it contains is encoded as 1 byte.
Mr. Xcoder
8

APL (Dyalog Extended), 7 bytesSBCS

Anonymous tacit prefix function. Takes [n,b] as argument.

×/-\…1¨

Try it online!

 one for each element of the argument; [1,1]

-\ cumulative difference; [n,n-b]

 range using second element of left argument as indicator of step, e.g. [9,7] continues with 5

×/ product

Adám
fonte
7

Haskell, 21 bytes

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

Try it online!

Combinar a função interna do produto com a enumeração de intervalos escalonados supera o que eu poderia codificar recursivamente (mesmo com falhas ao salvar um byte).

22 bytes

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

Experimente online!

Aqui está uma solução que aceita dados no formato string 9!!, que eu acho mais interessante.

42 bytes

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

Experimente online!

xnor
fonte
2
Eu acho que você pode encurtar a solução recursiva paran%a|n<1=1|m<-n-a=n*m%a
flawr
5

JavaScript (ES6), 21 bytes

Toma entrada como (k)(n).

k=>g=n=>n<1||n*g(n-k)

Experimente online!

Ou 24 bytes para oferecer suporte a BigInts.


JavaScript (ES6), 55 bytes

Recebe a entrada como uma sequência, usando o formato descrito no desafio.

s=>(a=s.split`!`,k=a.length-1,g=n=>n<1||n*g(n-k))(a[0])

Experimente online!

Arnauld
fonte
5

Espaço em branco , 91 bytes

[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]

Letras S(espaço), T(tabulação) e N(nova linha) adicionadas apenas como destaque.
[..._some_action]adicionado apenas como explicação.

Experimente online (apenas com espaços brutos, guias e novas linhas).

Explicação em pseudo-código:

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
Kevin Cruijssen
fonte
4

Perl 6 , 22 bytes

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

Experimente online!

Codeblock anônimo que retorna o produto do intervalo começando na primeira entrada, diminuindo a cada segundo até ficar abaixo 1, excluindo o último número. Isso funciona porque 0, como o caso base de uma redução por produto é 1, a saída é 1.

Brincadeira
fonte
4

05AB1E , 10 8 7 bytes

ݦRIιнP

Entrada como duas entradas separadas: sendo a primeira entrada base; segunda entrada sendo factorial.

Experimente online ou verifique todos os casos de teste .

-2 bytes graças a @ Mr.Xcoder .
-1 byte graças a @ JonathanAllan .

Explicação:

Ý        # 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)

Resposta original de 10 bytes :

L0KD¤-IÖÏP

Entrada como duas entradas separadas: sendo a primeira entrada base; segunda entrada sendo factorial.

Experimente online ou verifique todos os casos de teste .

Explicação:

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)
Kevin Cruijssen
fonte
1
Este código de 6 caracteres: LR²ιнP( Experimente on-line! ) Funciona para todos os casos de teste, exceto para 0.
Sr. Xcoder
Mas acho que o caso 0 pode ser corrigido em no máximo 2 bytes. Se você descobrir uma maneira de corrigi-lo, você pode segui-lo :) EDIT: Talvez LR²ιн0KPpor 8 bytes?
Sr. Xcoder
@ Mr.Xcoder Resposta agradável! Nunca usei uninterleave em uma determinada etapa. :)
Kevin Cruijssen
0Kdeve ser desnecessário, pois 0!é uma entrada inválida pela especificação (mesmo que tenha sido incluída nos exemplos) - eu comentei sobre isso.
Jonathan Allan
1
... e se 0! estiver no domínio de entrada, ݦRXιнPsalva um byte.
Jonathan Allan
4

código de máquina x86-64, 12 bytes

O mesmo código de máquina faz a mesma coisa no modo de 32 bits e para números inteiros de 16 bits no modo de 16 bits.

Esta é uma função, que pode ser chamado com argumentos n=RCX, k=ESI. Valor de retorno de 32 bits emEAX .

É possível chamar de C com a convenção de chamada do System V x86-64 com argumentos fictícios para obter os argumentos reais nos registros corretos. uint32_t factk(int, uint32_t k, int, uint64_t n); Eu não podia simplesmente usar o Windows x64 porque um operando mulbloqueia o RDX e não queremos que os prefixos REX acessem o R8 / R9. nnão deve ter nenhum lixo nos 32 bits altos, para que o JRCXZ funcione, mas, além disso, é tudo de 32 bits.

Listagem NASM (endereço relativo, código da máquina, origem)

 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 bytes


Ou 10 bytes, se não precisássemos lidar com o n=0caso especial, deixando de fora o jrcxz.

Para fatorial padrão, você usaria em loopvez de sub / ja para economizar 2 bytes, mas, caso contrário, o mesmo código.


Chamador teste que passa argccomo k, com ncodificados.

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`

```
Peter Cordes
fonte
3

APL (Dyalog Unicode) , 11 bytes SBCS

Função de infixo tácito anônimo. Toma ncomo argumento certo e bcomo argumento esquerdo.

×/1⌈⊢,⊢-×∘⍳

Experimente online!

×∘⍳ multiplicar bpelas Ɩ ntegers 1 atravésn

⊢- subtrair isso de n

⊢, preceder n

1⌈ máximo de um e cada um deles

×/ produtos

Adão
fonte
3

Wolfram Language (Mathematica) , 22 21 bytes

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

Experimente online!

-1 graças a attinat: Times --> 1##&

Explicação: use Rangepara fazer uma lista dos valores {n, n-k, n-2k, n-3k, ...}, parando antes de ficar abaixo de 1 (ou seja, parando exatamente à direita). Multiplique todos os números nesta lista com Times(ou 1##&).

romano
fonte
-1 byte com em 1##&vez deTimes
attinat 5/08
3

Java 10, 44 bytes

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

Toma o fatorial como primeira entrada, base como segundo.

Experimente online.

Isso acima não funciona para o maior caso de teste devido ao intervalo inteiro limitado (32 bits). Para corrigir isso, podemos usar BigIntegers, que coincidentemente é exatamente o dobro do tamanho - 88 79 bytes :

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

-9 bytes graças a @ OlivierGrégoire .

Experimente online.

Explicação:

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
Kevin Cruijssen
fonte
@ OlivierGrégoire Np, e obrigado! :)
Kevin Cruijssen
2

Japonês , 8 bytes

TõUV f ×

Tente

-1 graças a EoI, apontando o quão desgrenhado e descafeinado Shaggy pode ser!

Shaggy
fonte
kTpode ser substituído fpor 1 byte
Modalidade de ignorância
1
@EmbodimentofIgnorance, é claro que pode! Eu sabia que era muito cedo para o golfe! : \
Shaggy
2

C (gcc) , 41 bytes

r;f(n,k){for(r=1;n>0;n-=k)r*=n;return r;}

Experimente online!

Leo Tenenbaum
fonte
36 bytes r;f(n,k){for(r=1;n>0;n-=k)r*=n;n=r;}para C (gcc)
GPS em
2

MathGolf , 7 6 bytes

╙╒x%ε*

Experimente online!

Encontrei uma maneira inteligente de lidar com 0! sem alterar os outros casos de teste. Recebe a entrada como k n(ordem inversa), o que ajuda no pop-up implícito.

Explicação

╙        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
fonte
2

Anexo , 21 19 bytes

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

Experimente online! Implementação recursiva bastante direta. (Nota:true é essencialmente 1, pois pode ser usado em operações aritméticas como1 .) Este é um dos poucos programas que escrevi para este site em que o uso de um operador unicode salva bytes (1, para ser mais preciso).

Alternativas

20 bytes: ${x<y or x*$[x-y,y]}

21 bytes: Prod@${{_%y=x%y}\1:x}

27 bytes: ${x*[`1,$][x>y][x-y,y]∨1}

27 bytes: ${If[x>y,x*$[x-y,y],_or 1]}

27 bytes: ${x*[`1,$][x>y][x-y,y]or 1}

29 bytes: ${If[x>y,x*$[x-y,y],_+not _]}

Conor O'Brien
fonte
2

Ferrugem , 92 73 61 bytes

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

Estou apenas começando a aprender ferrugem, então tenho certeza de que isso pode ser mais curto. Será atualizado conforme eu aprender. O valor de retorno deve seri128 em ordem para calcular o último teste.

Editar: a recursão é mais curta.

Experimente online!

Você pode adicionar seu próprio teste ou editar um dos já existentes.

emilanov
fonte
2

q , 59 57 55 53 bytes

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

explicação:

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

aqui também está uma versão em k (mesma lógica), 42 41 bytes

{*/2+&1_i=last i:("J"$x@&~:n)#!+/n:"!"=x}
rabisco
fonte
Bem vindo ao site! Adicionei formatação de código à sua postagem, que pode ser feita com quatro espaços antes da linha ou anexando-a com reticências triplas.
Wheat Wizard
@ Graças SriotchilismO'Zaic :-)
rabisco
1
Eu recomendo adicionar uma explicação e talvez um link para um intérprete online como o TIO . As respostas somente de código geralmente são sinalizadas automaticamente como baixa qualidade.
mbomb007 9/08
@ mbomb007 interessante. existe um bot sinalizando respostas? o que acontece com envios de baixa qualidade? vou atualizar em breve!
rabisco
Sim, existe um bot. O StackExchange usa bots para procurar possíveis spam e respostas de baixa qualidade. Pessoas com reputação alta o suficiente podem visualizar a fila de revisão. meta.stackexchange.com/a/161391/285610
mbomb007
1

Physica , 22 bytes

f=>n;k:n<1||n*f[n-k;k]

Experimente online!


26 bytes

Re-aprendendo a usar minha própria "linguagem" \ o / ... Se eu soubesse escrever um analisador há 2 anos, isso teria sido 20 bytes :(

->n;k:GenMul##[n…1]{%%k}

ou

->n;k:GenMul##Range[n;1;k]

Experimente online!

Mr. Xcoder
fonte
1

Retina , 66 bytes

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

Experimente online! O link inclui casos de teste mais rápidos. Números mauls sem pontos de exclamação. Explicação:

^0
1

Conserte 0!.

\d+
*!,

Converta nem unário e adicione um separador.

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

Subtraia repetidamente kde nenquanto n>ke colete os resultados.

!+$
1

Substitua kpor 1(em decimal).

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

Multiplique por cada valor intermediário, por sua vez, convertendo para decimal.

Neil
fonte
1

Quarto (gforth) , 50 bytes

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

Experimente online!

Código Explicação

: 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
fonte
1

Gaia , 6 bytes

…)¦v%Π

Experimente online!

Toma entrada como n, k, a fim de entrada de 3 4seria 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
fonte