Contexte
Considérons une séquence définie comme suit:
- Le premier élément est 0;
- Le deuxième élément est 4;
- A partir du troisième élément, sa valeur peut être calculée par:
- Prendre l'ensemble des entiers de 0 à l'élément précédent de la séquence (inclusif ou exclusif, peu importe);
- Supprimer tous les entiers qui sont déjà apparus plus tôt dans la séquence de l'ensemble;
- Additionner les éléments restants de l'ensemble; c'est la valeur que vous voulez.
Fait intéressant, cette séquence ne semble pas encore être sur OEIS .
La tâche
Écrivez un programme ou une fonction qui prend un entier n en entrée et génère le n ème élément de la séquence.
Cas de test
Les premiers éléments de la séquence sont:
- 0
- 4
- 6 (1 + 2 + 3)
- 11 (1 + 2 + 3 + 5)
- 45 (1 + 2 + 3 + 5 + 7 + 8 + 9 + 10)
- 969 (1 + 2 + 3 + 5 + 7… 10 + 12… 44)
- 468930 (1 + 2 + 3 + 5 + 7… 10 + 12… 44 + 46… 968)
Clarifications
- Votre programme devrait en théorie être capable de gérer arbitrairement n s'il est exécuté sur une variante de votre langue qui a des nombres entiers sans limites et un accès à une quantité illimitée de mémoire. (Il est peu probable que les langues sans bignum puissent aller bien au-delà de 468930, mais ce n'est pas une excuse pour coder en dur les réponses.)
- Vous pouvez choisir une indexation basée sur 0 ou 1 pour la séquence (par exemple, c'est à vous de décider si n = 1 renvoie le premier élément, n = 2 le deuxième élément, etc.) ou si n = 0 renvoie le premier élément , n = 1 le deuxième élément, etc.).
- Il n'y a aucune exigence sur l'algorithme que vous utilisez, ni sur son efficacité; vous pouvez implémenter directement la définition de la séquence (même si elle est vraiment inefficace), et vous pouvez également implémenter un algorithme différent qui conduit aux mêmes résultats.
Condition de victoire
Il s'agit de code-golf , donc le programme correct le plus court, mesuré en octets, gagne.
Réponses:
Gelée ,
13129 octetsUtilise l'indexation basée sur 0.
Essayez-le en ligne!
Comment ça marche
la source
Python,
6660 octetsMerci à @Dennis d'avoir rasé 6 octets!
Ce n'est pas le code le plus golfique de tous les temps, mais il utilise une formule que j'ai faite:
Où se trouve
x
sur le côté droitf(n - 1)
, ety
estf(n - 2)
.Explication:
La somme des entiers continus de
a
àb
(inclus) peut être décrite par cette formule:Où
amount
(quantité de nombres) est décrit comme suit:Et
average
(la moyenne de tous les nombres) est décrite comme suit:Donc, la formule complète est maintenant:
La façon dont nous mettons en œuvre cette formule dans la formule finale consiste à substituer
a
àf(n - 1)
,b
pourf(n - 2)
, qui calcule essentiellement la somme de tous les nouveaux termes, et ajouter une autref(n - 1)
(qui est maintenanta
) sur, qui est la somme de tous les termes précédents.En combinant cela ensemble, nous obtenons:
Remplacez
a
parx
etb
pary
, et hé hop, vous devez faire la formule ci-dessus.la source
Python 2 ,
585450 octetsEssayez-le en ligne!
la source
Mathematica,
4948 octetsUtilise l'encodage CP-1252. Définit la fonction
PlusMinus (±)
. 1 indexé.Explication
la source
Oasis , 11 octets
Code:
Explication:
Pour visualiser la relation de f n , prenons l'exemple f 5 . Pour calculer f 5 , regardons la somme suivante:
1 + 2 + 3 + 5 + 7 + 8 + 9 + 10
La partie en gras est identique à f 4 . La partie 7 + 8 + 9 + 10 est la plage [f n-2 + 1, f n-1 - 1] . Cela fait la formule f n-1 + Σ [f n-2 + 1 ... f n-1 - 1] ( lien Wolfram ):
f n = 0,5 × (f n-1 2 - f n-2 2 + f n-1 - f n-2 )
Qui peut être réécrit en:
f n = 0,5 × ((f n-1 - f n-2 ) (f n-1 + f n-2 ) + (f n-1 - f n-2 ))
f n = 0,5 × ((f n-1 - f n-2 ) (f n-1 + f n-2 + 1))
Quelle est la formule que nous utiliserons dans le code:
Explication du code
La
640
partie nous donne les cas de base:Le code qui sera exécuté (qui définit un (n) ):
Essayez-le en ligne!
la source
Julia,
393332 octetsBasé sur 0.
Merci à @Dennis, économisé 6 octets.
Merci à @GlenO, a sauvé un octet.
Essayez-le en ligne!
Réponse précédente 1- basée:
Essayez-le en ligne!
Réponse précédente non golfée basée sur 1:
Essayez-le en ligne!
la source
n<3?5n-n^2:
plutôt quen<4?2(n>1)n:
- notez qu'il passe à l'utilisation de l'indexation basée sur 0, cependant.JavaScript (ES6), 47 octets
Utilise la relation de récurrence
f(n) = sum(range(f(n-2) + 1, f(n-1) + 1))
pour n> 2.la source
PowerShell ,
84898887 octetsEssayez-le en ligne!
Explication
Indexation basée sur 0. Fonctionne uniquement
n = 6
(sur ma machine Windows, il se bloque avec un débordement de pile pourn = 7
).En utilisant la même méthode que la réponse de JungHwan Min (somme de la plage moins somme des termes précédents).
La somme d'une plage / d'un tableau dans PowerShell est longue, j'utilise donc une astuce pour joindre un tableau avec
+
pour créer une expression longue (comme1+2+3+4...etc
), puis l'envoyer viaiex
(Invoke-Expression
).Étant donné que je dois le faire deux fois, au lieu d'utiliser,
-join
je définis la variable spéciale$OFS
, qui signifie séparateur de champ de sortie. Lorsque vous chaînez un tableau, c'est le caractère utilisé pour joindre les éléments; c'est un espace par défaut. Donc, en le définissant sur+
(une fois), je peux remplacer quelque chose comme$a-join'+'|iex
avec"$a"|iex
.Une simple
for
boucle continue jusqu'à ce que le nombre de séquences soit inférieur ou égal à l'entier d'entrée, puis je retourne le$n
e élément.la source
;
besoin après lafor
boucle. Je n'avais jamais réalisé ça auparavant.MATL ,
1716 octets1
l'indexation basée sur est utilisée. Le code est très inefficace. Carn = 6
il dépasse déjà la limite de mémoire du compilateur en ligne.Essayez-le en ligne!
Comment ça marche
Pour 20 octets , la version suivante évite la limitation de mémoire. Mais il y a toujours la limitation du type de données (le
double
type ne peut garantir que les entiers sont représentés avec précision jusqu'à2^53
), donc les résultats ne sont valides que jusqu'àn = 8
.Essayez-le aussi en ligne !
la source
Haskell , 42 octets
Essayez-le en ligne!
Cela implémente directement la récurrence qui, pour
n>2
,f(n)
est égal àf(n-1)
plus la somme de l'intervalle ouvert à partirf(n-2)
def(n-1)
laquelle est à nouveau égal à la somme de l'intervalle semi-ouvert def(n-2)
àf(n-1)
inclusif.la source
Haskell, 31 octets
Exemple d'utilisation:
((0:4#6)!!) 6
->468930
. Essayez-le en ligne! .Récursivité simple, qui garde
m
jusqu'à présent l' élément maximum et la valeur suivantes
.la source
JavaScript,
123119 octetsEssayez-le en ligne! Cette solution est basée 1,
f(1) => 0
.la source
Perl 6 ,
52 49 4435 octetsEssayez-le
Essayez-le
Essayez-le
Essayez-le
Étendu:
la source
PowerShell ,
7773 octetsEssayez-le en ligne!
Implémente l'algorithme tel que défini et est indexé 0. L'entrée de
6
est trop pour TIO à gérer.Définit
$a
comme un tableau[0,4]
. Boucles de l'1
entrée à l'entrée$n
. Dans la boucle, nous prenons la plage de nombres du0
plus grand nombre que nous avons$a[-1]
, et utilisons uneWhere-Object
clause|?{...}
pour extraire uniquement les nombres qui ne sont pas déjà présents. Ce tableau de nombres est-join
édité avec+
s, puis alimentéiex
(abréviation deInvoke-Expression
et similaire àeval
). Cette valeur est ensuite concaténée en tableau à la fin de$a
. Enfin, nous quittons notre boucle et prenons le$n
numéro e dans notre tableau. Ce nombre est laissé sur le pipeline et la sortie est implicite.la source
Python 2 , 85 octets
Essayez-le en ligne!
la source
Lot, 108 octets
Port de ma réponse JavaScript.
la source
dc , 47 octets
Fonctionne avec des entiers aussi grands que vous le souhaitez, jusqu'à la capacité de mémoire de l'ordinateur.
Essayez-le en ligne!
Indexation basée sur 0, entrée sur stdin, sortie sur stdout. (Il y a aussi une sortie sur stderr, qui doit être ignorée.)
Exemples de cycles:
Cela utilise le même algorithme que la solution suivante dans bash, qui est (un peu) plus lisible:
Pure bash, 60 octets
Mais le programme bash ne fonctionne que pour les entrées jusqu'à 7, car il dépasse le dépassement d'entier.
la source
Pyth - 15 octets
Suite de tests .
la source
C # - 74 octets
Non golfé:
Il existe probablement un moyen de le convertir en lambda pour économiser encore plus, ou quelque chose en utilisant la fonction .Aggregate. Bien qu'actuellement je n'aie pas d'importations, alors peut-être que ça égalise?
la source
> <> , 43 + 3 = 46 octets
Utilise la formule présentée dans les réponses d' Adnan et de Qwerp-Derp .
Attend que l'entrée soit présente sur la pile, donc +3 octets pour l'
-v
indicateur.Essayez-le en ligne!
la source