Definición

a (1) = 1
a (2) = 1
a (n) = a (na (n-1)) + a (na (n-2)) para n> 2 donde n es un número entero

Tarea

Dado entero positivo n, generar a(n).

Casos de prueba

Referencia

Obligatorio OEIS A005185

code-golf sequence arithmetic Monja permeable
fuente

Relacionados .

Leaky Nun

1

¿Podemos devolver True en idiomas donde se puede usar como 1 ?

Dennis

1

@Dennis Si en ese idioma verdadero es equivalente a 1, entonces sí.

Leaky Nun

44

Además del enlace OEIS, podría ser bueno hacer referencia a GEB donde apareció por primera vez la secuencia.

Martin Ender

1

Completando la lista de desafíos de secuencia relacionados con GEB.

Martin Ender

9

Retina , 84 83 79 74 bytes

El recuento de bytes asume la codificación ISO 8859-1.

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

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas separado por salto de línea).

Tendré que jugar al golf un poco más tarde.

Martin Ender
fuente

9

Haskell, 35 33 bytes

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

Define una función a.

Anders Kaseorg
fuente

2

Buen truco con el enlace! ¿No sería algo (b.b)1+(b.b)2más corto que la suma?

xnor

¿Por qué sí, gracias @xnor.

Anders Kaseorg

8

Julia, 29 bytes

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

Pruébalo en línea!

Cómo funciona

Redefinimos el operador unario !para nuestros fines.

Si n es 1 o 2 , n<3devuelve verdadero y este es nuestro valor de retorno.

Si n es mayor que 2 , n<3devuelve falso y el || la rama se ejecuta. Esta es una implementación directa de la definición, donde ~-nproduce n - 1 y ~-~-nproduce n - 2 .

Dennis
fuente

7

Sesos, 54 bytes

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.~.....

Pruébalo en línea

Desmontado

O en notación Brainfuck:

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

Anders Kaseorg
fuente

6

C, 43 42 bytes

Guardado 1 byte gracias a @Dennis

Cada respuesta es la misma, ¡debo hacer algo diferente!

Pruébalo en línea!

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

Explicación: es básicamente a(n-a(n-2))+a(n-a(n-1))pero con ^un comportamiento ^{indefinido e} impreciso (funciona en mi teléfono (gcc) e ideone).

Betseg
fuente

44

1. También debe mencionar el compilador; su "botín" es un comportamiento indefinido. 2. Con GCC, no necesita 1entre ?y :.

Dennis

@Dennis Curiosamente, esa misma formulación funciona en mi respuesta iterativa de PowerShell ...$b+=$b[$_-$b[$_-2]]+$b[$_---$b[$_]]

AdmBorkBork

@TimmyD, algunos compiladores pueden compilar el a (n) antes del n--, y no hay un comportamiento estándar (o definido) para eso. Por lo tanto, comportamiento indefinido.

betseg

@betseg Sí, estoy de acuerdo. Solo señalando que no es necesariamente exclusivo de C.

AdmBorkBork

@TimmyD Oh, no entendí eso. Solo quería cambiar la función que todos usan, por lo que la mía sería diferente e irregular: D

betseg

5

Mathematica, 36 bytes

El recuento de bytes asume la codificación ISO 8859-1 y la $CharacterEncodingconfiguración de Mathematica en WindowsANSI(el valor predeterminado en Windows; otras configuraciones también podrían funcionar, pero algunas como UTF-8definitivamente no).

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

Define ±como operador unario.

Intenté deshacerme de la duplicación, pero terminé con el mismo número de bytes:

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

Martin Ender
fuente

Puedo darte una recompensa de +200 si lo haces en Retina

Leaky Nun

@LeakyNun ¿de acuerdo? :)

Martin Ender

Dos días después.

Leaky Nun

@LeakyNun Pronto no te quedará ningún representante si das recompensas tan fácilmente.

mbomb007

Continuemos esta discusión en el chat .

LegionMammal978

4

Jalea , 15 14 bytes

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

Pruébalo en línea! o verificar todos los casos de prueba (toma unos segundos).

Cómo funciona

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
fuente

Puedo darte una recompensa de +400 si lo haces en Sesos.

Leaky Nun

@LeakyNun Parece que hay una respuesta de Sesos. Salió un día después de tu comentario.

Yytsi

4

Jalea , 14 12 11 bytes

ịḣ2S;
1Ç⁸¡2ị

Este es un enfoque iterativo.

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

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
fuente

3

Python, 45 40 bytes

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

Interpretación simple e ingenua del desafío.

¡Guardado 5 bytes gracias a @LeakyNun!

Cobre
fuente

3

Haskell, 39 37 bytes

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

exactamente como se describe en el desafío, usando guardias

KarlKastor
fuente

Lo siento, no vi su solución antes de publicar mi solución haskell (idéntica). Sin embargo, ¿no es el número de bytes 38 ya que la nueva línea debe tenerse en cuenta?

Laikoni

Y la guardia tiene que ser n<3para h 2 ser 1.

Laikoni

@Laikoni Es 37 según la función de Pythons len con una cadena multilínea ("" "), a menos que cuentes la nueva línea como dos bytes. Sí, noté lo otro que está arreglado ahora.

KarlKastor

TIL notepad ++ cuenta la nueva línea como dos caracteres.

Laikoni

@Laikoni se deshizo de la nueva línea, es indiscutiblemente 37 bytes ahora.

KarlKastor

3

R, 50 bytes

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

Uso:

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

DSkoog
fuente

3

CJam, 19 18 bytes

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

Pruébalo en línea!

Utiliza el enfoque iterativo.

Martin Ender
fuente

3

C #, 51 44 bytes

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

Me ~~pregunto si esto puede acortarse haciéndolo anónimo~~ gracias pinkfloydx33!

downrep_nation
fuente

1

c # 6 función corporal de expresiónint a(int n)=>n<3?1:a(n-a(n-a))+a(n-a(n-2));

pinkfloydx33

Parece que escribí al escribir en mi teléfono. Lo más interno -aen el primer grupo de padres debería ser-1

pinkfloydx33

Yo tampoco lo noté, lo arreglaré rq

downrep_nation

3

JavaScript (ES6), 45 bytes 34 bytes

Una solución recursiva en ES6. Cualquier consejo de golf muy apreciado.

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

Gracias a / u / ismillo por acortar aún más.

BugHunterUK
fuente

2

Golfscript, 29 bytes

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

Pruébalo en línea!

Monja permeable
fuente

2

05AB1E, 29 bytes

Una solución iterativa.

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

Pruébalo en línea

Emigna
fuente

2

APL, 20 bytes

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

Explicación:

{⍵≤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
fuente

2

VBA Excel 87 bytes

No recursivo, ya que quiero que esto funcione para n = 100000, diga:

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

... y presione return(byte # 87) al final de la línea para obtener la End Functiondeclaración "gratis". Tenga en cuenta que los valores B se compensan con -1 para evitar la inicialización de n = 1 y 2.

Invocar en la hoja de cálculo de forma normal, por ejemplo, =A(100000)para obtener48157

La versión recursiva, 61 bytes ,

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

comienza a ser irrazonablemente lento para n> 30, y no se puede decir que funcione para n> 40.

Joffan
fuente

No nos importa el rendimiento. Nos importa la longitud del código. Debe mover su solución más corta a la parte superior de su respuesta.

mbomb007

1

@ mbomb007 Como no estoy cerca de ganar el golf, tomaré mis propias decisiones sobre lo que constituye un programa de trabajo. No puedo manejar incluso números enteros de un solo byte no es lo suficientemente bueno en lo que a mí respecta, cuando hay una solución que puede hacerlo fácilmente.

Joffan

2

Ruby, 36 bytes

Una implementación directa. Cualquier sugerencia de golf es bienvenida.

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

Sherlock9
fuente

Afaik, puedes deshacerte de a =. Si lo publica aquí, es suficiente cuando su código comienza con ->. Cuenta como una función anónima entonces.

Seims

@Seims Desafortunadamente, como la función se llama a sí misma a[n-1]y tal, la función necesita ser nombrada.

Sherlock9

2

Java 7 68 61 51 bytes

17 salvados gracias a Leaky Nun.

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

Justin
fuente

Bienvenido a PPCG!

AdmBorkBork

Bienvenido a PPCG! Puede que te gusten los consejos para jugar golf en Java . Una forma alternativa sería: int a(int n){return n<3?1:a(n-a(n-2))+a(n---a(n));}pero, desafortunadamente, usa la misma cantidad de bytes que la respuesta que ya tiene. Además, especificaría que su respuesta está en Java 7, ya que la respuesta de Java 8 sería más corta: n->return n<3?1:a(n-a(n-1))+a(n-a(n-2))( 39 bytes ) .

Kevin Cruijssen

Gracias por la bienvenida chicos, y gracias por el consejo sobre Java8, no me di cuenta de que las lambdas se permitían así, aunque sí se permiten en Python, así que supongo que nunca lo pensé. ¿La lambda necesita un punto y coma?

Justin

@JustinTervay No uso mucho Java 8, pero por lo que he escuchado, el punto y coma no se cuenta con expresiones de una sola línea, según un comentario de @DavidConrad y @ CAD97 en una de mis propias respuestas de Java .

Kevin Cruijssen

2

Oasis , 9 7 5 bytes (no competidor)

No competitiva , ya que el lenguaje es posterior al desafío. Gracias a Kenny Lau por guardar 4 bytes. Código:

ece+V

Forma ampliada ( Ves la abreviatura de 11):

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

Código:

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

Pruébalo en línea! . Calcula n = 1000 en 0.1 segundos.

Adnan
fuente

1

PowerShell v2 +, 85 79 69 bytes

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

Toma entrada $n, establece $bque sea una matriz de @(1, 1), luego ingresa un bucle desde 2 .. $n. Cada iteración añadimos $bel último cálculo en la secuencia con un simple +=y la definición de la secuencia. Luego sacamos el número apropiado de $b(con un -1porque las matrices en PowerShell están indexadas a cero). Esto funciona si $nes 1o 2porque ambos valores están rellenados previamente en los índices más bajos $bdesde el principio, por lo que incluso si el bucle se suma a la basura, se ignora de todos modos.

Solución recursiva 78 76 bytes

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

La primera vez que utilicé el equivalente de una lambda como respuesta, ya que generalmente una solución iterativa es más corta (como puede ver en todos los padres anidados). ~~Pero, en este caso, los parens anidados están casi duplicados en la solución iterativa con las llamadas de matriz anidadas, por lo que la solución recursiva es más corta.~~ No, la solución iterativa es de hecho más corta (ver arriba).

Llámalo a través del operador de ejecución, como &$a 20. Solo una llamada recursiva directa.

AdmBorkBork
fuente

1

JavaScript (ES6), 66 bytes

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

Versión no recursiva para la velocidad; La versión recursiva es probablemente más corta pero la dejaré para que otra persona la escriba. Siempre me gusta cuando puedo usar reduce. Nota: 1 byte guardado al devolver true(que se convierte en 1cuando se usa en un contexto entero) para de a(1)y a(2).

Neil
fuente

1

Pyth, 16 bytes

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

Define una función y.

Pruébelo en línea (agregado yMS20para imprimir los primeros 20 valores)

Anders Kaseorg
fuente

1

Adelante, 76 bytes

¡Finalmente lo hice funcionar!

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

Pruébalo en línea

Explicación:

: 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 ;

Pruébelo en línea (un poco sin golf desde arriba)

Desafortunadamente, la recursividad mutua es demasiado complicada para jugar al golf.

mbomb007
fuente

1

Arce, 43 41 bytes

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

Uso:

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

Este problema es ciertamente un buen candidato para la memorización. Usando la opción de caché , los tiempos de ejecución se reducen significativamente:

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

Esto se puede ver usando:

CodeTools:-Usage( aC(50) );

DSkoog
fuente

0

J, 29 28 bytes

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

Utiliza la definición recursiva.

Uso

Se utilizan comandos adicionales para formatear múltiples entradas / salidas.

   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

Explicación

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

millas
fuente

0

cc, 62 bytes

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

Esta solución hace uso de matrices y recursividad.

?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
fuente

En conclusión, si alguien está creando un IDE dc, ¡hágamelo saber!

Joe

0

Erlang, 46 bytes

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

cPu1
fuente

0

Lua, 59 bytes

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

brianush1
fuente

Secuencia Q de Hofstadter

Definición

Tarea

Casos de prueba

Referencia

Respuestas:

Retina , 84 83 79 74 bytes

Haskell, 35 33 bytes

Julia, 29 bytes

Cómo funciona

Sesos, 54 bytes

Desmontado

C, 43 42 bytes

Mathematica, 36 bytes

Jalea , 15 14 bytes

Cómo funciona

Jalea , 14 12 11 bytes

Cómo funciona

Python, 45 40 bytes

Haskell, 39 37 bytes

R, 50 bytes

CJam, 19 18 bytes

C #, 51 44 bytes

JavaScript (ES6), 45 bytes 34 bytes

Golfscript, 29 bytes

05AB1E, 29 bytes

APL, 20 bytes

VBA Excel 87 bytes

Ruby, 36 bytes

Java 7 68 61 51 bytes

Oasis , 9 7 5 bytes (no competidor)

PowerShell v2 +, 85 79 69 bytes

Solución recursiva 78 76 bytes

JavaScript (ES6), 66 bytes

Pyth, 16 bytes

Adelante, 76 bytes

Arce, 43 41 bytes

J, 29 28 bytes

Uso

Explicación

cc, 62 bytes

Erlang, 46 bytes

Lua, 59 bytes