Ne pas confondre avec Trouver la factorielle!

introduction

La factorielle d'un entier npeut être calculée par

$$n!=n\times(n-1)\times(n-2)\times(...)\times2\times1$$

C'est relativement facile et rien de nouveau. Cependant, les factorielles peuvent être étendues aux factorielles doubles , telles que

$$n!!=n\times(n-2)\times(n-4)\times(...)\times4\times2$$ pour les nombres pairs et $$n!!=n\times(n-2)\times(n-4)\times(...)\times3\times1$$ ( pour les nombres impairs. Mais nous ne sommes pas limités aux doubles factorielles. Par exemple $$n!!!=n\times(n-3)\times(n-6)\times(...)\times6\times3$$ ou $$n!!!=n\times(n-3)\times(n-6)\times(...)\times5\times2$$ ou $$n!!!=n\times(n-3)\times(n-6)\times(...)\times4\times1$$ en fonction de la valeur de départ.

En résumé:

$${\displaystyle n!^{(k)}={\begin{cases}1&{\text{if }}n=0 \\n&{\text{if }}0<n\leq k\\n\cdot\left({(n-k)!}^{(k)}\right)&{\text{if }}n>k\end{cases}}}$$ où $${\displaystyle n!^{(k)}=n\underbrace{!\dots!}_{k}}$$ Ou, en clair, anglais:Soustrayez le nombre factoriel du nombre de base à plusieurs reprises et multipliez tous les entiers positifs résultants.

Le défi

Ecrivez une fonction qui calculera tout type de factorielle répétée pour tout entier non négatif.

Contribution

Non plus

• Chaîne contenant un entier non négatif en base dix suivi d'un ou plusieurs points d'exclamation. Par exemple "6!"ou "9!!"ou "40!!!!!!!!!!!!!!!!!!!!".

ou

• Les mêmes valeurs représentées par deux entiers: une valeur de base non négative et une valeur positive représentant le compte factoriel. Cela peut être fait selon n'importe quel format à partir des règles d'E / S par défaut.

Sortie

Le résultat dudit calcul.

Remarques du challenge

• 0!est égal 1par définition. Votre code doit en tenir compte.
• Le comptage factoriel est limitée par $$0 < factorial~count \leq base~value$$ en dehors de cette plage, vous êtes libre de sortie quelconque. À part0! , qui est la seule exception à cette règle.

Exemples

Input                              Output

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

Essayez-le avec une implémentation Python non-golfée: essayez-le en ligne!

Remarques générales

• C'est du code-golf , donc la réponse utilisant le moins d'octets dans chaque langue gagne.
• Règles standard , les règles d' E / S et les règles échappatoire applicables.
• S'il vous plaît inclure un lien Essayez-le en ligne pour démontrer que votre code fonctionne.
• S'il vous plaît motiver votre réponse avec une explication de votre code.

R , 33 octets

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

Essayez-le en ligne!

Traite $n=0$ en ajoutant la négation logique de $n$ .

ArnoldC , 702 698 634 octets

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

Essayez-le en ligne!

Traduit en pseudocode:

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

Remarque: ArnoldC a un seul type de données: un entier signé 16 bits. Par conséquent, je ne peux pas tester le 420!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!cas.

Gelée , 4 octets

RṚmP

Essayez-le en ligne!

Comment? Compte tenu de $n$ et $k$ , il génère d' abord l'intervalle $n,\cdots, 1$ (avec RṚ), puis avec melle conserve tous les $k^{\text{th}}$ élément de cette gamme (donc $n, n-k, n-2k,\cdots,n-\lfloor n/k\rfloor k$ ), et finalement les multiplie en utilisant P.

APL (Dyalog Extended) , ^SBCS 7 octets

Fonction de préfixe tacite anonyme. Prend [n,b]comme argument.

×/-\…1¨

Essayez-le en ligne!

1¨ un pour chaque élément de l'argument; [1,1]

-\ différence cumulative; [n,n-b]

… plage en utilisant le deuxième élément de l'argument de gauche comme indicateur de pas, par exemple, [9,7]continue avec5

×/ produit

Haskell , 21 octets

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

Essayez-le en ligne!

La combinaison de la fonction de produit intégrée avec l'énumération échelonnée de la plage bat ce que je pouvais coder de manière récursive (même avec la sauvegarde fulgurante d'un octet).

22 octets

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

Essayez-le en ligne!

Voici une solution prenant en entrée au format chaîne 9!!, ce qui, à mon avis, est plus intéressant.

42 octets

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

Essayez-le en ligne!

Pyth , 6 octets

Ce sont tous équivalents 6-byters:

*F:Q1E
*F:E1Q
*F%E_S

Essayez-le en ligne! ( *F:Q1E)

Ou, 11 octets , en prenant l’entrée sous forme de chaîne:

*F:.vQ1/Q\!

Suite de tests.

JavaScript (ES6), 21 octets

Prend les entrées en tant que (k)(n).

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

Essayez-le en ligne!

Ou 24 octets pour prendre en charge BigInts.

---

JavaScript (ES6), 55 octets

Prend les entrées sous forme de chaîne, en utilisant le format décrit dans le défi.

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

Essayez-le en ligne!

Espaces blancs , 91 octets

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

Lettres S(espace), T(tabulation) et N(nouvelle ligne) ajoutées uniquement en surbrillance.
[..._some_action]ajouté comme explication seulement.

Essayez-le en ligne (avec des espaces bruts, des onglets et des nouvelles lignes uniquement).

Explication en pseudo-code:

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

Python 2 , 29 octets

f=lambda n,b:n<1or n*f(n-b,b)

Essayez-le en ligne!

Perl 6 , 22 octets

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

Essayez-le en ligne!

Codeblock anonyme qui renvoie le produit de la plage en partant de la première entrée, en diminuant de seconde en seconde 1, en excluant le dernier chiffre. Cela fonctionne pour 0, puisque le cas de base de la réduction par produit est 1, la sortie est donc 1.

05AB1E , 10 8 7 octets

ݦRIιнP

Entrée sous forme de deux entrées séparées: la première entrée étant base; deuxième entrée étant factorial.

Essayez-le en ligne ou vérifiez tous les cas de test .

-2 octets grâce à @ Mr.Xcoder .
-1 octet grâce à @JonathanAllan .

Explication:

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

Réponse originale de 10 octets :

L0KD¤-IÖÏP

Entrée sous forme de deux entrées séparées: la première entrée étant base; deuxième entrée étant factorial.

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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)

code machine x86-64, 12 octets

Le même code machine fait la même chose en mode 32 bits et pour les entiers 16 bits en mode 16 bits.

Cette fonction, appelable avec args n=RCX, k=ESI. Valeur de retour 32 bits en EAX.

Appelable en C avec la convention d'appel System V x86-64 avec des arguments factices pour obtenir les arguments réels dans les registres appropriés. uint32_t factk(int, uint32_t k, int, uint64_t n); Je ne pouvais pas simplement utiliser Windows x64 parce mulque RDX était un opérateur à 1 opérande , et nous ne voulons pas que les préfixes REX accèdent à R8 / R9. nPour que JRCXZ fonctionne, il ne doit pas y avoir de déchets dans les 32 bits les plus élevés, mais à part cela, tout est en 32 bits.

Liste NASM (adresse relative, code machine, source)

 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 octets

---

Ou 10 octets si nous n’avons pas besoin de traiter le n=0cas spécial, en laissant de côté le jrcxz.

Pour factorial standard, vous utiliseriez à la loopplace de sub / ja pour sauvegarder 2 octets, mais sinon, le même code.

---

Appelant de test qui passe argccomme k, avec ncodé en dur.

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`

```

APL (Dyalog Unicode) , ^{SBCS de} 11 octets

Fonction infixe tacite anonyme. Prend ncomme argument droit et bcomme argument gauche.

×/1⌈⊢,⊢-×∘⍳

Essayez-le en ligne!

×∘⍳ multiplier bpar les ɩ ntegers 1 àn

⊢- soustrayez cela de n

⊢, ajouter n

1⌈ max d'un et chacun de ceux

×/ produit

Ruby , 25 octets

f=->s,r{s<1?1:s*f[s-r,r]}

Essayez-le en ligne!

Wolfram Language (Mathematica) , 22 21 octets

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

Essayez-le en ligne!

-1 merci à attinat: Times --> 1##&

Explication: utilisez Rangepour faire la liste des valeurs {n, n-k, n-2k, n-3k, ...}, en vous arrêtant avant de descendre en dessous de 1 (c'est-à-dire en vous arrêtant juste). Puis multipliez tous les nombres de cette liste avec Times(ou 1##&).

Java 10, 44 octets

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

Prend la factorielle en première entrée, base en seconde.

Essayez-le en ligne.

La procédure ci-dessus ne fonctionne pas pour le cas de test le plus volumineux en raison de la plage d’entiers limitée (32 bits). Pour résoudre ce problème , nous pouvons utiliser BigIntegers, qui par hasard est exactement le double de la taille - 88 79 octets :

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

-9 octets grâce à @ OlivierGrégoire .

Essayez-le en ligne.

Explication:

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

Japt , 8 octets

TõUV f ×

L'essayer

-1 grâce à EoI qui a montré à quel point Shaggy peut être stupide et sans café!

C (gcc) , 41 octets

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

Essayez-le en ligne!

MathGolf , 7 à 6 octets

╙╒x%ε*

Essayez-le en ligne!

Trouvé un moyen intelligent de gérer 0! sans changer les autres cas de test. Prend les entrées en tant que k n(ordre inverse), ce qui facilite le popping implicite.

Explication

╙        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

Attaché , 21 à 19 octets

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

Essayez-le en ligne! Jolie implémentation récursive directe. (Remarque: trueest essentiellement 1, comme il peut être utilisé dans les opérations arithmétiques comme1 .) C’est l’un des rares programmes que j’ai écrit pour ce site où l’utilisation d’un opérateur Unicode enregistre les octets (1, pour être précis).

Des alternatives

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

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

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

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

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

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

Rust , 92 73 61 octets

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

Je commence tout juste à apprendre la rouille, alors je suis sûr que cela peut être plus court. Mettra à jour que j'apprends. La valeur de retour doit être i128afin de calculer le dernier test.

Edit: La récursivité est plus courte.

Essayez-le en ligne!

Vous pouvez ajouter votre propre test ou modifier l'un des tests existants.

q , 59 57 55 53 octets

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

explication:

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

voici aussi une version en k (même logique), 42 41 octets

{*/2+&1_i=last i:("J"$x@&~:n)#!+/n:"!"=x}

Physica , 22 octets

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

Essayez-le en ligne!

---

26 octets

Réapprendre à utiliser mon propre "langage" \ o / ... Si j'avais su écrire un analyseur il y a 2 ans, cela aurait été de 20 octets :(

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

ou

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

Essayez-le en ligne!

Retina , 66 octets

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

Essayez-le en ligne! Link inclut des cas de test plus rapides. Mauls nombres sans points d'exclamation. Explication:

^0
1

Réparer 0!.

\d+
*!,

Convertir nen unaire et ajouter un séparateur.

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

Soustrayez à plusieurs reprises kde nwhile n>ket collectez les résultats.

!+$
1

Remplacez kpar 1(en décimal).

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

Multipliez par chaque valeur intermédiaire à tour de rôle, en convertissant en décimal.

Japt , 8 octets

1õUV f ×

L'essayer

JavaScript (Node.js) , 35 octets

(n,i,f=i)=>i-n<1?f:r(n,i-n,f*(i-n))

Essayez-le en ligne!

Forth (gforth) , 50 octets

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

Essayez-le en ligne!

Explication du code

: 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           

Perl 5 -Mbigint -p , 45 octets

$b=s/!//g;$\=1*$_||1;$\*=$_ while($_-=$b)>0}{

Essayez-le en ligne!

Stax , 6 octets

å▐█ΩV∟

Exécuter et déboguer

Il prend une entrée dans le formulaire {count} {base}.

Gaia , 6 octets

…)¦v%Π

Essayez-le en ligne!

Prend l'entrée comme n, kdonc l'entrée 3 4serait 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.