Crie o programa ou a função mais curta que encontre o fatorial de um número inteiro não negativo.
O fatorial, representado por, !
é definido como tal
Em inglês simples, o fatorial de 0 é 1 e o fatorial de n, onde n é maior que 0 é n vezes o fatorial de um menor que n.
Seu código deve executar entrada e saída usando métodos padrão.
Requisitos:
- Não usa bibliotecas internas que possam calcular o fatorial (isso inclui qualquer forma de
eval
) - Pode calcular fatoriais para números de até 125
- Pode calcular o fatorial para o número 0 (igual a 1)
- Conclui em menos de um minuto para números de até 125
A finalização mais curta vence, no caso de empate, a resposta com mais votos no momento vence.
code-golf
arithmetic
factorial
Kevin Brown
fonte
fonte
Respostas:
Golfscript - 12 caracteres
Introdução ao Golfscript - Fatorial passo a passo
Aqui está algo para as pessoas que estão tentando aprender golfe. O pré-requisito é um entendimento básico do golfscript e a capacidade de ler a documentação do golfscript.
Então, queremos experimentar nossa nova ferramenta golfscript . É sempre bom começar com algo simples, então estamos começando com fatorial. Aqui está uma tentativa inicial, baseada em um simples pseudocódigo imperativo:
Espaço em branco é muito raramente usado no golfe. O truque mais fácil para se livrar do espaço em branco é usar diferentes nomes de variáveis. Cada token pode ser usado como uma variável (consulte a página de sintaxe ). Fichas úteis para usar como variáveis são caracteres especiais como
|
,&
,?
- geralmente não qualquer coisa usada em outras partes do código. Estes são sempre analisados como tokens de caracteres únicos. Por outro lado, variáveis comon
exigirão um espaço para empurrar um número para a pilha depois. Os números são essencialmente variáveis pré-inicializadas.Como sempre, haverá declarações que podemos mudar, sem afetar o resultado final. Em golfscript, tudo é avaliada como verdadeira, exceto
0
,[]
,""
e{}
(ver este ). Aqui, podemos alterar a condição de saída do loop para simplesmente{n}
(fazemos um loop adicional e terminamos quando n = 0).Como no golfe em qualquer idioma, ajuda a conhecer as funções disponíveis. Felizmente, a lista é muito curta para o golfscript. Nós podemos mudar
1-
para(
salvar outro personagem. No momento, o código se parece com o seguinte: (poderíamos estar usando em1
vez de|
aqui, se quiséssemos, o que eliminaria a inicialização.)É importante usar bem a pilha para obter as soluções mais curtas (praticar praticar praticar). Geralmente, se os valores forem usados apenas em um pequeno segmento de código, talvez não seja necessário armazená-los em variáveis. Ao remover a variável de produto em execução e simplesmente usar a pilha, podemos salvar muitos caracteres.
Aqui está outra coisa para pensar. Estamos removendo a variável
n
da pilha no final do corpo do loop, mas depois a pressionamos imediatamente. De fato, antes do início do loop, também o removemos da pilha. Em vez disso, devemos deixá-lo na pilha e podemos manter a condição do loop em branco.Talvez possamos até eliminar completamente a variável. Para fazer isso, precisaremos manter a variável na pilha o tempo todo. Isso significa que precisamos de duas cópias da variável na pilha no final da verificação de condição para não perdê-la após a verificação. O que significa que teremos um redundante
0
na pilha após o término do loop, mas isso é fácil de corrigir.Isso nos leva à nossa
while
solução ideal de loop!Agora ainda queremos tornar isso mais curto. O alvo óbvio deve ser a palavra
while
. Olhando para a documentação, existem duas alternativas viáveis - desdobrar e fazer . Quando você pode escolher diferentes rotas a seguir, tente pesar os benefícios de ambas. Desdobrar é 'praticamente um loop while', portanto, como uma estimativa, reduziremos o caractere 5while
em 4/
. Quanto ado
isso, cortamoswhile
3 caracteres e fundimos os dois blocos, o que pode salvar outro ou dois caracteres.Na verdade, há uma grande desvantagem em usar um
do
loop. Como a verificação da condição é feita depois que o corpo é executado uma vez, o valor de0
estará errado, portanto, podemos precisar de uma instrução if. Vou lhe dizer agora que o desdobramento é mais curto (algumas soluçõesdo
são fornecidas no final). Vá em frente e tente, o código que já temos exige alterações mínimas.Ótimo! Nossa solução agora é super curta e terminamos aqui, certo? Não. São 17 caracteres e J possui 12 caracteres. Nunca admita derrota!
Agora você está pensando com ... recursão
Usar recursão significa que devemos usar uma estrutura de ramificação. Lamentável, mas como fatorial pode ser expresso de forma tão sucinta e recursivamente, isso parece ser uma alternativa viável à iteração.
Bem, isso foi fácil - se tivéssemos tentado a recursão antes, talvez nem tivéssemos olhado usando um
while
loop! Ainda assim, temos apenas 16 caracteres.Matrizes
Matrizes geralmente são criadas de duas maneiras - usando os caracteres
[
e]
, ou com a,
função Se executado com um número inteiro no topo da pilha,,
retorna uma matriz desse comprimento com arr [i] = i.Para iterar sobre matrizes, temos três opções:
{block}/
: empurrar, bloquear, empurrar, bloquear, ...{block}%
: [push, block, push, block, ...] (isso tem algumas nuances, por exemplo, valores intermediários são removidos da pilha antes de cada push){block}*
: empurrar, empurrar, bloquear, empurrar, bloquear, ...A documentação do golfscript tem um exemplo de uso
{+}*
para somar o conteúdo de uma matriz. Isso sugere que podemos usar{*}*
para obter o produto de uma matriz.Infelizmente, não é tão simples assim. Todos os elementos estão desativados por um (em
[0 1 2]
vez de[1 2 3]
). Podemos usar{)}%
para corrigir esse problema.Bem, não exatamente. Isso não lida com zero corretamente. Podemos calcular (n + 1)! / (N + 1) para corrigir isso, embora isso custe demais.
Também podemos tentar manipular n = 0 no mesmo bloco que n = 1. Isso é extremamente curto, tente e trabalhe o mais curto possível.
Se queremos ter o incremento e a multiplicação no mesmo bloco, devemos iterar todos os elementos da matriz. Como não estamos construindo uma matriz, isso significa que devemos usá-la
{)*}/
, o que nos leva à implementação mais curta do fatorial! Com 12 caracteres, isso está associado a J!Soluções bônus
Começando com uma
if
solução direta para umdo
loop:Podemos extrair mais alguns disso. Um pouco complicado, então você terá que se convencer de que esses funcionam. Certifique-se de entender tudo isso.
Uma alternativa melhor é calcular (n + 1)! / (N + 1), o que elimina a necessidade de uma
if
estrutura.Mas a
do
solução mais curta aqui leva alguns caracteres para mapear de 0 a 1 e tudo o mais para si - portanto, não precisamos de nenhuma ramificação. Esse tipo de otimização é extremamente fácil de perder.Para qualquer pessoa interessada, são fornecidas aqui algumas soluções recursivas alternativas com o mesmo comprimento acima:
* Nota: Na verdade, eu não testei muitos dos trechos de código neste post, portanto, fique à vontade para informar se há erros.
fonte
Haskell, 17
fonte
[1..0] ==> []
eproduct [] ==> 1
f 0=1;f n=n*f$n-1
possui 17 caracteres.product
e, digamos,(*)
ou(-)
"podem calcular o fatorial", e todos são definidos através do Prelúdio. Por que um seria legal e não o outro?Python - 27
Simplesmente:
fonte
0**x
.math.factorial
? Não é um built-in, é?0**x
?APL (4)
Funciona como uma função anônima:
Se você quiser dar um nome, 6 caracteres:
fonte
⍳
um vetor de índice, ou seja,⍳5
é1 2 3 4 5
.×
é (obviamente) multiplicado,/
reduzido e∘
é composição da função. Portanto,×/∘⍳
é uma função que recebe um argumentox
e fornece o produto dos números[1..x]
.J (12)
Uma definição padrão em J:
Menos de 1 segundo para 125!
Por exemplo:
fonte
([:*/1+i.)
10 pontos, ou mesmo 8, os parênteses são necessários apenas para chamar a função, não para a definição.f 125x
o quex
faz? É um tipo especial de número?Golfscript - 13 caracteres (SYM)
define a função
!
versão alternativa de 13 caracteres
a versão completa do programa é de 10 caracteres
os casos de teste levam menos de 1/10 de segundo:
entrada:
resultado
entrada
resultado
fonte
Caracteres do Perl 6: 13
[*]
é o mesmo que Haskellproduct
e1..$_
é uma contagem de 1 a$_
, o argumento.fonte
[*]
(mensagem de erro "Dois termos consecutivos").Matlab, 15
Casos de teste
fonte
Python, 28 bytes
(com base na solução da Alexandru)
fonte
MATL , 2 bytes
Explicado:
Experimente online!
fonte
Ruby - 21 caracteres
Teste
fonte
Java, 85 caracteres
fonte
import java.math.*;
(portanto, +19 bytes).PostScript, 26 caracteres
Exemplo:
A função em si tem apenas 21 caracteres; o resto é vinculá-lo a uma variável. Para salvar um byte, também é possível vinculá-lo a um dígito, assim:
fonte
1.#INF
. (Eu usei estoque GNU Ghostscript 9.0.7 compilado para x64 do Windows.)JavaScript, 25
CoffeeScript, 19
Retorna
true
no caso de n = 0, mas o JavaScript coagirá esse tipo para 1 de qualquer maneira.fonte
return
declaração na função JavaScript?return
! Mas porque não?function f(n)n?n*f(--n):1
f=n=>!n||n*f(n-1)
Pegue isso, CoffeeScript!Ruby -
3029 caracteresTeste
fonte
end
diretamente depois:*
sem uma nova linha ou ponto e vírgula.(1..10).inject :*
# => 3628800f(0)
quê?f=->n{(1..n).inject 1,:*}
. Ligue comf[n]
.F #: 26 caracteres
Não há função de produto embutida em F #, mas você pode criar uma com uma dobra
fonte
C #, 20 ou 39 caracteres, dependendo do seu ponto de vista
Como um método de instância tradicional (39 caracteres; testado aqui ):
Como uma expressão lambda (20 caracteres, mas veja o aviso de isenção de responsabilidade; testado aqui ):
Temos que usar
double
porque 125! == 1,88 * 10 209 , que é muito maior queulong.MaxValue
.Isenção de responsabilidade sobre a contagem de caracteres da versão lambda:
Se você recursionar em um C # lambda, obviamente precisará armazenar o lambda em uma variável nomeada para que ela possa se chamar. Porém, diferente do JavaScript (por exemplo), um lambda auto-referente deve ter sido declarado e inicializado em uma linha anterior. Você não pode chamar a função na mesma instrução na qual declara e / ou inicializa a variável.
Em outras palavras, isso não funciona :
Mas isso faz :
Não há uma boa razão para essa restrição, pois
f
nunca pode ser desassociada no momento em que é executada. A necessidade daFunc<int,double> f=null;
linha é uma peculiaridade de C #. Se isso faz com que seja justo ignorá-lo na contagem de caracteres, depende do leitor.CoffeeScript,
2119 caracteres de verdadeTestado aqui: http://jsfiddle.net/0xjdm971/
fonte
Braquilog ,
76 bytesFazendo um intervalo e multiplicando-o
Tanques de -1 byte a ovs, com a ideia de usar a função max ()
Explicação
Experimente online!
Braquilog ,
109 bytesrecursão
Explicação
Experimente online!
fonte
;
vez de,
permite apenas uma entrada numérica regular. -1byte de qualquer maneiraC (39 caracteres)
fonte
double f(n){return!n?1:n*f(n-1);}
- 33 caracteres.f(125)
vai transbordar #D: 45 caracteres
Mais legível:
Um cooler (embora versão mais longa) é o modelo que faz tudo em tempo de compilação ( 64 caracteres ):
Mais legível:
Os modelos de mesmo nome são bastante detalhados, portanto, você não pode realmente usá-los muito bem no código golf. D já é detalhado o suficiente em termos de contagem de caracteres para ser bastante ruim para o código de golfe (embora realmente seja muito bom em reduzir o tamanho geral do programa para programas maiores). É a minha linguagem favorita, portanto, acho que é melhor tentar ver como é possível fazê-lo no código do golfe, mesmo se pessoas como o GolfScript quiserem usá-lo.
fonte
PowerShell - 36
Ingênuo:
Teste:
fonte
Scala, 39 caracteres
A maioria dos caracteres garante que
BigInt
s sejam usados para que os requisitos de valores até 125 sejam atendidos.fonte
(x:Int)=>(BigInt(1)to x).product
def f(x:Int)=(BigInt(1)to x).product
def f(x:BigInt)=(x.to(1,-1)).product
def f(x:BigInt)=(-x to-1).product.abs
Javascript, ES6 17
ES6:
fonte
PowerShell, 42 bytes
(salvou 2 caracteres usando filtro em vez de função )
Resultado:
fonte
filter f($x){if($x){$x*(f($x-1))}else{1}}
. E pode ser reduzido ainda mais para 36 caracteres se for chamado via pipeline, pois é um filtro (por exemplo125|f
):filter f{if($_){$_*($_-1|f)}else{1}}
Raquete (esquema)
403529 bytesCalcula 0! para ser 1 e calcula 125! em 0 segundos de acordo com o temporizador. Abordagem recursiva regular
Nova versão para vencer o lisp comum: multiplica todos os elementos de uma lista (o mesmo que a solução Haskell)
Versão mais recente para superar a outra solução de esquema e matemática a outra solução de raquete usando foldl em vez de aplicar e usando range em vez de buildlist
fonte
Mornington Crescent ,
18271698 caracteresEu estava com vontade de aprender um novo idioma hoje, e foi nisso que eu pousei ... (Por que eu faço isso comigo mesmo?) Essa entrada não ganhará nenhum prêmio, mas será melhor que todas as outras 0 respostas até agora usando o mesmo idioma!
Experimente online!
Qualquer pessoa que viajou por Londres entenderá isso instantaneamente, é claro, então tenho certeza de que não preciso dar uma explicação completa.
A maior parte do trabalho no início é no tratamento do caso 0. Após inicializar o produto em 1, posso usá-lo para calcular o máximo (entrada, 1) para obter a nova entrada, aproveitando o fato de que 0! = 1! Então o loop principal pode começar.
(EDIT: Um monte de viagens foram salvas removendo o 1 dos "Terminais 1, 2, 3 de Heathrow" em vez de gerá-lo dividindo 7 (Irmãs) por si só. Também uso um método mais barato para gerar -1 em o próximo passo.)
Decrementar é caro em Mornington Crescent (embora seja menos caro que o próprio metrô). Para tornar as coisas mais eficientes, eu gero um -1 pegando o NOT de um 0 analisado e o armazeno em Hammersmith durante grande parte do loop.
Coloquei um trabalho significativo nisso, mas como essa é minha primeira tentativa de jogar golfe em Mornington Crescent (na verdade, minha primeira tentativa em qualquer idioma), espero ter perdido algumas otimizações aqui e ali. Se você está interessado em programar nessa linguagem (e por que não estaria?), O Esoteric IDE - com seu modo de depuração e janela de visualização - é obrigatório!
fonte
Befunge - 2x20 = 40 caracteres
Essa é uma função, pois é um bloco de código independente que não utiliza a envolvente. Você deve colocar o argumento no topo da pilha e, em seguida, digite a partir do canto superior esquerdo, indo para a direita; a função sairá do canto inferior direito, indo para a direita, com o resultado no topo da pilha.
Por exemplo, para calcular o fatorial de 125
Teste 0
fonte
&:!#@_>:# 1# -# :# _$>\# :#* _$.@
(onde & deve ser substituído pela entrada). É 32 caracteres / bytesJ - 6 caracteres
Isso conta? Eu sei que é muito parecido com o exemplo anterior de J, mas é um pouco mais curto :)
Sou iniciante com J, mas até agora é muito divertido!
fonte
Em C (23 caracteres)
Isso abusa do "recurso" do GCC que faz com que a última atribuição conte como retorno, se nenhum retorno for especificado.
Em C adequado, 28 caracteres
fonte
0 == ({printf("Hello, world!"); 0;});
Kona (
116)K funciona da direita para a esquerda (na maior parte), por isso enumeramos
x
(fazemos uma lista / matriz de números de0
atéx-1
), adicionamos1
a ela (a faixa varia0
dex
) e multiplicamos todos os números juntos. Se não fosse necessário calcular125!
, eu poderia economizar mais 1 byte, eliminando.
próximo a1
. De qualquer forma, 125! é calculado em meros milissegundos:fonte
*/1.+!
: 6 bytes.