Définition

a (1) = 1
a (2) = 1
a (n) = a (na (n-1)) + a (na (n-2)) pour n> 2 où n est un entier

Tâche

Étant donné un entier positif n, générez a(n).

Cas de test

Référence

Obligatoire OEIS A005185

code-golf sequence arithmetic Leaky Nun
la source

Connexes .

Leaky Nun

1

Pouvons-nous retourner True dans les langues où il peut être utilisé comme 1 ?

Dennis

1

@Dennis Si dans cette langue, true est équivalent à 1, alors oui.

Leaky Nun

4

En dehors du lien OEIS, il pourrait être bon de référencer GEB où la séquence est apparue pour la première fois.

Martin Ender

1

Compléter la liste des défis de séquence liés au GEB.

Martin Ender

9

Rétine , 84 83 79 74 octets

Le nombre d'octets suppose un codage ISO 8859-1.

.+
$*;1¶1¶
+`;(?=(1)+¶(1)+)(?=(?<-1>(1+)¶)+)(?=(?<-2>(1+)¶)+)
$3$4¶
G3=`
1

Essayez-le en ligne! (La première ligne active une suite de tests séparés par un saut de ligne.)

Je devrai jouer au golf un peu plus tard.

Martin Ender
la source

9

Haskell, 35 33 octets

a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)

Définit une fonction a.

Anders Kaseorg
la source

2

Belle astuce avec la liaison! Quelque chose comme ne serait-il pas (b.b)1+(b.b)2plus court que la somme?

xnor

Pourquoi oui, merci @xnor.

Anders Kaseorg

8

Julia, 29 octets

!n=n<3||!(n-!~-n)+!(n-!~-~-n)

Essayez-le en ligne!

Comment ça marche

Nous redéfinissons l'opérateur unaire !pour nos besoins.

Si n est 1 ou 2 , n<3renvoie vrai et ceci est notre valeur de retour.

Si n est supérieur à 2 , n<3renvoie false et le || la branche est exécutée. Il s'agit d'une implémentation simple de la définition, où les ~-nrendements n - 1 et les ~-~-nrendements n - 2 .

Dennis
la source

7

Sesos, 54 octets

0000000: eefb5b 04f83a a75dc2 36f8d7 cf6dd0 af7b3b 3ef8d7  ..[..:.].6...m..{;>..
0000015: cfed12 f661f0 ae9d83 ee63e6 065df7 ce6183 af7383  ....a.....c..]..a..s.
000002a: 76ef3c 3f6383 7eff9c b9e37f                       v.<?c.~.....

Essayez-le en ligne

Démonté

Ou en notation Brainfuck:

+>+>>>>>>,-[[->+<]>-<<++[<<<<[->>>+<<<]>>>>[-<<<+<+>>>>]<<<[->>>+<<<]>>>>++[<<<<<[<
[->>+<<]>[-<+>]<-]>>[-<+<+>>]>[<<[->+<]>>[-<<+>>]>]>>>-]<<[-<<<+>>>]>-]>>]<<<<<<<.

Anders Kaseorg
la source

6

C, 43 42 octets

1 octet enregistré grâce à @Dennis

Chaque réponse est la même, je dois faire quelque chose de différent!

Essayez-le en ligne!

a(n){return n<3?:a(n-a(n-2))+a(n---a(n));}

Explication: c'est fondamentalement a(n-a(n-2))+a(n-a(n-1))mais avec ^un comportement ^indéfini fanfaron (fonctionne sur mon téléphone (gcc) et ideone).

betseg
la source

4

1. Vous devez également mentionner le compilateur; votre "swag" est un comportement indéfini. 2. Avec GCC, vous n'avez pas besoin 1entre ?et :.

Dennis

@Dennis Fait intéressant, cette même formulation fonctionne dans ma réponse itérative PowerShell ...$b+=$b[$_-$b[$_-2]]+$b[$_---$b[$_]]

AdmBorkBork

@TimmyD certains compilateurs peuvent compiler le a (n) avant le n--, et il n'y a pas de comportement standard (ou défini) pour cela. Ainsi, comportement indéfini.

betseg

@betseg Oui, je suis d'accord. Je souligne juste que ce n'est pas nécessairement unique à C.

AdmBorkBork

@TimmyD Oh j'ai mal compris ça. Je voulais juste changer la fonction que tout le monde utilise, donc la mienne serait différente et arrogante: D

betseg

5

Mathematica, 36 octets

Le nombre d'octets suppose que le codage ISO 8859-1 et Mathematica sont $CharacterEncodingdéfinis sur WindowsANSI(la valeur par défaut sous Windows; d'autres paramètres peuvent également fonctionner, mais certains UTF-8ne le sont certainement pas).

±1=±2=1
±n_:=±(n-±(n-1))+±(n-±(n-2))

Définit ±comme un opérateur unaire.

J'ai essayé de me débarrasser de la duplication, mais j'ai fini avec le même nombre d'octets:

±1=±2=1
±n_:=Tr[±(n-±(n-#))&/@{1,2}]

Martin Ender
la source

Je peux vous donner une prime de +200 si vous le faites à Retina

Leaky Nun

@LeakyNun ok? :)

Martin Ender

Deux jours plus tard.

Leaky Nun

@LeakyNun Bientôt, vous n'aurez plus de représentant si vous distribuez des primes si facilement.

mbomb007

Continuons cette discussion dans le chat .

LegionMammal978

4

Gelée , 15 14 octets

2Rạ⁸ß€$⁺Sµ1>?2

Essayez-le en ligne! ou vérifiez tous les cas de test (prend quelques secondes).

Comment ça marche

2Rạ⁸ß€$⁺Sµ1>?2  Main link. Argument: n (integer)

2R              Yield [1, 2].
      $         Combine the previous three links into a monadic chain.
   ⁸                Yield n.
  ạ                 Take the absolute difference of the return value and n.
    ß€              Recursively call the main link on each result.
       ⁺            Duplicate the chain.
                    The first copy maps [1, 2] to [a(n - 1), a(n - 2)].
                    The second copy maps [a(n - 1), a(n - 2)] to
                    [a(n - a(n - 1)), a(n - a(n - 2))].
        S           Take the sum.
         µ          Combine all links to the left into a chain.
            ?       If...
           > 2          n is greater than 2, call the chain.
          1         Else, return 1.

Dennis
la source

Je peux vous donner une prime de +400 si vous le faites à Sesos.

Leaky Nun

@LeakyNun Il semble y avoir une réponse Sesos. Il est sorti un jour après votre commentaire.

Yytsi

4

Gelée , 14 12 11 octets

ịḣ2S;
1Ç⁸¡2ị

Il s'agit d'une approche itérative.

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

Comment ça marche

1Ç¡2ị   Main link. Argument: n

1       Set the return value to 1.
 Ç¡     Call the helper link n times, updating the return value after each call.
   2ị   Extract the second element of the resulting array.


ịḣ2S;   Helper link. Argument: A (array)

ị       At-index; retrieve the elements of A at the values of A.
 ḣ2     Head 2; extract the first two results.
    S   Take the sum of the result.
     ;  Prepend the sum to A.

Dennis
la source

3

Python, 45 40 octets

a=lambda n:n<3or a(n-a(n-1))+a(n-a(n-2))

Interprétation simple et naïve du défi.

5 octets enregistrés grâce à @LeakyNun!

Cuivre
la source

3

Haskell, 39 37 octets

h n|n<3=1|n>2=h(n-h(n-1))+h(n-h(n-2))

exactement comme décrit dans le défi, en utilisant des gardes

KarlKastor
la source

Désolé, je n'ai pas vu votre solution avant de poster ma (identique) solution haskell. Cependant, le nombre d'octets n'est-il pas 38 car la nouvelle ligne doit être prise en compte?

Laikoni

Et le garde doit être n<3pour h 2 être 1.

Laikoni

. @Laikoni Il de 37 selon la caractéristique Pythons len avec un multiligne ( « » ") de la chaîne, à moins que vous comptez deux octets comme nouvelle ligne Ouais, je remarquais l'autre chose qu'il est maintenant fixé.

KarlKastor

TIL notepad ++ compte la nouvelle ligne comme deux caractères.

Laikoni

@Laikoni s'est débarrassé de la nouvelle ligne, c'est indiscutablement 37 octets maintenant.

KarlKastor

3

R, 50 octets

a=function(n)ifelse(n<3,1,a(n-a(n-1))+a(n-a(n-2)))

Usage:

> a(1)
  1
> a(20)
  12

DSkoog
la source

3

CJam, 19 18 octets

XXri{_($2$$+}*]-3=

Essayez-le en ligne!

Utilise l'approche itérative.

Martin Ender
la source

3

C #, 51 44 octets

int a(int n)=>n<3?1:a(n-a(n-1))+a(n-a(n-2));

~~je me demande si cela peut être raccourci en le rendant anonyme~~ merci pinkfloydx33!

downrep_nation
la source

1

c # 6 fonction bodied d'expressionint a(int n)=>n<3?1:a(n-a(n-a))+a(n-a(n-2));

pinkfloydx33

On dirait que je tape en tapant ça sur mon téléphone. L'intérieur le plus -adans le premier jeu de parens devrait être-1

pinkfloydx33

Je ne l'ai pas remarqué non plus, je le

répare

3

JavaScript (ES6), 45 octets 34 octets

Une solution récursive dans ES6. Tous les conseils de golf sont très appréciés.

a=n=>n>2?a(n-a(n-1))+a(n-a(n-2)):1

Merci à / u / ismillo d' avoir raccourci encore plus.

BugHunterUK
la source

2

Golfscript, 29 octets

~[1 1]{..0=(=\..1=(=@+\+}@*2=

Essayez-le en ligne!

Leaky Nun
la source

2

05AB1E, 29 octets

Une solution itérative.

XˆXˆÍL>v¯¤ys-è¯y¯yÍè-è+ˆ}¯¹<è

Essayez-le en ligne

Emigna
la source

2

APL, 20 octets

{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}

Explication:

{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
 ⍵≤2:1               If argument is 2 or less, return 1
      ⋄              Otherwise:
               ⍵-⍳2  Subtract [1, 2] from the argument
             ∇¨      Recursive call on both
           ⍵-        Subtract both results from the argument     
         ∇¨          Recursive call on both again
       +/            Sum

marinus
la source

2

VBA Excel 87 octets

Non récursif, puisque je veux que cela fonctionne pour n = 100000, dites:

Function A(N):ReDim B(N):For i=3 To N:B(i)=B(i-B(i-1)-1)+B(i-B(i-2)-1)+1:Next:A=B(N)+1

... et appuyez sur return (octet # 87) à la fin de la ligne pour obtenir la End Functiondéclaration "gratuitement". Notez que les valeurs B sont décalées de -1 pour éviter l'initialisation pour n = 1 et 2.

Invoquer dans une feuille de calcul comme d'habitude, par exemple =A(100000) pour obtenir48157

La version récursive, 61 octets ,

Function Y(N):If N<3 Then Y=1 Else Y=Y(N-Y(N-1))+Y(N-Y(N-2))

commence à devenir excessivement lent pour n> 30, et on ne peut pas dire qu'il fonctionne du tout pour n> 40.

Joffan
la source

Nous ne nous soucions pas de la performance. Nous nous soucions de la longueur du code. Vous devez déplacer votre solution la plus courte en haut de votre réponse.

mbomb007

1

@ mbomb007 Puisque je suis loin de gagner le golf, je ferai mes propres choix sur ce qui constitue un programme de travail. Ne pas être capable de gérer même des entiers à un seul octet n'est pas assez bon en ce qui me concerne, quand il existe une solution qui peut le faire facilement.

Joffan

2

Rubis, 36 octets

Une mise en œuvre directe. Toutes les suggestions de golf sont les bienvenues.

a=->n{n<3?1:a[n-a[n-1]]+a[n-a[n-2]]}

Sherlock9
la source

Afaik, vous pouvez vous débarrasser de l'a =. Si vous le postez ici, cela suffit lorsque votre code commence par le ->. Cela compte alors comme une fonction anonyme.

Seims

@Seims Malheureusement, comme la fonction s'appelle avec a[n-1]et tel, la fonction doit être nommée.

Sherlock9

2

Java 7, 68 61 51 octets

17 sauvés grâce à Leaky Nun.

int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}

Justin
la source

Bienvenue chez PPCG!

AdmBorkBork

Bienvenue chez PPCG! Vous pourriez aimer Conseils pour jouer au golf en Java . Une autre forme serait int a(int n){return n<3?1:a(n-a(n-2))+a(n---a(n));}:, mais malheureusement, elle utilise la même quantité d'octets que la réponse que vous avez déjà .. Je préciserais également que votre réponse est en Java 7, car la réponse Java 8 serait plus courte: n->return n<3?1:a(n-a(n-1))+a(n-a(n-2))( 39 octets ) .

Kevin Cruijssen

Merci pour l'accueil des gars, et merci pour le conseil sur Java8 - Je ne savais pas que les lambdas étaient autorisés comme ça - bien qu'ils soient autorisés comme ça en Python, donc je suppose que je n'y ai jamais pensé. Le lambda a-t-il besoin d'un point-virgule?

Justin

@JustinTervay Je n'utilise pas beaucoup Java 8, mais d'après ce que j'ai entendu, le point-virgule n'est pas compté sur des expressions sur une seule ligne, selon un commentaire de @DavidConrad et @ CAD97 dans l' une de mes propres réponses Java .

Kevin Cruijssen

2

Oasis , 9 7 5 octets (non concurrent)

Non compétitif , car la langue est postérieure au défi. Merci à Kenny Lau d' avoir économisé 4 octets. Code:

ece+V

Forme développée ( Vest l'abréviation de 11):

a(n) = ece+
a(0) = 1
a(1) = 1

Code:

e        # Stack is empty, so a(n - 1) is used, and it calculates a(n - a(n - 1))
 c       # Calculate a(n - 2)
  e      # Calculate a(n - a(n - 2))
   +     # Add up

Essayez-le en ligne! . Calcule n = 1000 en 0,1 seconde.

Adnan
la source

1

PowerShell v2 +, 85 79 69 octets

param($n)$b=1,1;2..$n|%{$b+=$b[$_-$b[$_-1]]+$b[$_-$b[$_-2]]};$b[$n-1]

Prend l'entrée $n, définit $bcomme un tableau de @(1, 1), puis entre dans une boucle à partir de 2 .. $n. À chaque itération, nous abordons $ble dernier calcul de la séquence avec un simple +=et la définition de la séquence. Nous sortons ensuite le nombre approprié à partir de $b(avec un -1car les tableaux dans PowerShell sont indexés zéro). Cela fonctionne si $nest 1ou 2parce que ces deux valeurs sont pré-remplies dans les indices inférieurs de $bdès le début, donc même si la boucle claque sur les fichiers indésirables, elle est de toute façon ignorée.

Solution récursive 78 76 octets

$a={param($k)if($k-lt3){1}else{(&$a($k-(&$a($k-1))))+(&$a($k-(&$a($k-2))))}}

La première fois, j'ai utilisé l'équivalent d'un lambda comme réponse, car généralement une solution itérative est plus courte (comme vous pouvez le voir dans toutes les parenthèses imbriquées). ~~Mais, dans ce cas, les parens imbriqués sont presque dupliqués dans la solution itérative avec les appels de tableau imbriqués, de sorte que la solution récursive est plus courte.~~ Non, la solution itérative est en effet plus courte (voir ci-dessus).

Appelez-le via l'opérateur d'exécution, comme &$a 20. Juste un appel récursif direct.

AdmBorkBork
la source

1

JavaScript (ES6), 66 octets

n=>[...Array(n+1)].reduce((p,_,i,a)=>a[i]=i<3||a[i-p]+a[i-a[i-2]])

Version non récursive pour la vitesse; la version récursive est probablement plus courte mais je laisse le soin à quelqu'un d'autre d'écrire. J'aime toujours quand j'arrive à utiliser reduce. Remarque: 1 octet enregistré en retournant true(qui est converti en 1cas d'utilisation dans un contexte entier) pour de a(1)et a(2).

Neil
la source

1

Pyth, 16 octets

L|<b3smy-bytdtBb

L                  def y(b):
 |<b3                b < 3 or …
      m      tBb       map for d in [b - 1, b]:
       y-bytd            y(b - y(d - 1))
     s                 sum

Définit une fonction y.

Essayez-le en ligne (ajouté yMS20pour imprimer les 20 premières valeurs)

Anders Kaseorg
la source

1

Forth, 76 octets

Je l'ai finalement fait fonctionner!

: Q recursive dup dup 3 < if - 1+ else 2dup 2 - Q - Q -rot 1- Q - Q + then ;

Essayez-le en ligne

Explication:

: Q recursive                           \ Define a recursive function Q
    dup dup 3 <                         \ I moved a dup here to golf 2 bytes
    if                                  \ If n < 3, return 1
        - 1                             \ Golf: n-n is zero, add one. Same as 2drop 1+
    else
        2dup 2 - Q - Q                  \ Copy n until 4 on stack, find Q(n-Q(n-2))
        -rot                            \ Move the result below 2 copies of n
        1- Q - Q +                      \ Find Q(n-Q(n-2)), then add to previous ^
    then ;

Essayez-le en ligne (légèrement non golfé par le haut)

Malheureusement, la récurrence mutuelle est un peu trop verbeuse à utiliser pour le golf.

mbomb007
la source

1

Érable, 43 41 octets

a:=n->`if`(n>2,a(n-a(n-1))+a(n-a(n-2)),1)

Usage:

> a(1);
  1
> a(20);
  12

Ce problème est certainement un bon candidat pour la mémorisation. Grâce au cache d'options , les temps d'exécution sont considérablement réduits:

aC := proc(n) 
      option cache; 
      ifelse( n > 2, aC( n - aC(n-1) ) + aC( n - aC(n-2) ), 1 ); 
end proc:

Cela peut être vu en utilisant:

CodeTools:-Usage( aC(50) );

DSkoog
la source

0

J, 29 28 octets

1:`(+&$:/@:-$:@-&1 2)@.(2&<)

Utilise la définition récursive.

Usage

Des commandes supplémentaires sont utilisées pour formater plusieurs entrées / sorties.

   f =: 1:`(+&$:/@:-$:@-&1 2)@.(2&<)
   (,:f"0) >: i. 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 3 3 4 5 5 6  6  6  8  8  8 10  9 10 11 11 12

Explication

1:`(+&$:/@:-$:@-&1 2)@.(2&<)  Input: n
                        2&<   If n < 2
1:                              Return 1
                              Else
               -&1 2            Subtract [1, 2] from n to get [n-1, n-2]
            $:@                 Call recursively on n-1 and n-2
           -                    Subtract each of the results from n
        /@:                     Reduce using
      $:                          A recursive call on each
    +&                            Then summation
                                Return that value as the result

miles
la source

0

dc, 62 octets

?si2sa1dd2:a:a[la1+dsadd1-;a-;alad2-;a-;a+r:ali;a0=A]dsAxli;af

Cette solution utilise des tableaux et la récursivité.

?si          # Take input from stdin and store it in register `i'
2sa          # Initialise register `a' with 2, since we'll be putting in the first
             #   two values in the sequence
1dd2         # Stack contents, top-down: 2 1 1 1
:a           # Pop index, then pop value: Store 1 in a[2]
:a           # Ditto:                     Store 1 in a[1]
[            # Open macro definition
 la 1+ dsa   # Simple counter mechanism: Increment a and keep a copy on stack

# The STACK-TRACKER(tm): Top of stack will be at top of each column, under the
#   dashed line. Read commands from left to right, wrapping around to next line.
#   This will be iteration number n.
  dd   1-    ;a       -          ;a            la            d          
#-----------------------------------------------------------------------
# n    n-1   a[n-1]   n-a[n-1]   a[n-a[n-1]]   n             n          
# n    n     n        n          n             a[n-a[n-1]]   n          
# n    n     n                                 n             a[n-a[n-1]]
#                                                            n          
#                                                                       

  2-            ;a            -             ;a            +      r    :a
#-----------------------------------------------------------------------
# n-2           a[n-2]        n-a[n-2]      a[n-a[n-2]]   a[n]   n      
# n             n             a[n-a[n-1]]   a[n-a[n-1]]   n      a[n]   
# a[n-a[n-1]]   a[n-a[n-1]]   n             n                           
# n             n                                                       

 li;a        # Load index of target element, and fetch that element's current value
             #    Uninitialised values are zero
 0=A         # If a[i]==0, execute A to compute next term
]dsAx        # Close macro definition, store on `A' and execute
li;a         # When we've got enough terms, load target index and push value
f            # Dump stack (a[i]) to stdout

Joe
la source

En conclusion, si quelqu'un construit un IDE pour dc, faites le moi savoir!

Joe

0

Erlang, 46 octets

f(N)when N<3->1;f(N)->f(N-f(N-1))+f(N-f(N-2)).

cPu1
la source

0

Lua, 59 octets

function a(n)return n<3 and 1 or a(n-a(n-1))+a(n-a(n-2))end

brianush1
la source

Séquence Hofstadter Q

Définition

Tâche

Cas de test

Référence

Réponses:

Rétine , 84 83 79 74 octets

Haskell, 35 33 octets

Julia, 29 octets

Comment ça marche

Sesos, 54 octets

Démonté

C, 43 42 octets

Mathematica, 36 octets

Gelée , 15 14 octets

Comment ça marche

Gelée , 14 12 11 octets

Comment ça marche

Python, 45 40 octets

Haskell, 39 37 octets

R, 50 octets

CJam, 19 18 octets

C #, 51 44 octets

JavaScript (ES6), 45 octets 34 octets

Golfscript, 29 octets

05AB1E, 29 octets

APL, 20 octets

VBA Excel 87 octets

Rubis, 36 octets

Java 7, 68 61 51 octets

Oasis , 9 7 5 octets (non concurrent)

PowerShell v2 +, 85 79 69 octets

Solution récursive 78 76 octets

JavaScript (ES6), 66 octets

Pyth, 16 octets

Forth, 76 octets

Érable, 43 41 octets

J, 29 28 octets

Usage

Explication

dc, 62 octets

Erlang, 46 octets

Lua, 59 octets