Números de Narayana-Zidek-Capell

17

Genere el enésimo número de Narayana-Zidek-Capell con una entrada n . Pocos bytes ganan.

f (1) = 1, f (n) es la suma de los términos del piso anterior (n / 2) Narayana-Zidek-Capell.

Casos de prueba:

f(1)=1

f(9)=42

f(14)=1308

f(15)=2605

f(23)=664299
Oliver Daugherty-Long
fuente
12
¡Bienvenido a Programming Puzzles & Code Golf! Este es un buen primer desafío. Aunque en última instancia depende de usted, generalmente recomendamos esperar al menos una semana para aceptar una respuesta. Tener una respuesta aceptada desde el principio puede enviar una señal a otros usuarios de que el desafío está más o menos terminado, lo que los desalienta de participar.
Alex A.

Respuestas:

6

Jalea, 11 10 bytes

HĊrµṖ߀Sȯ1

Pruébalo en línea!

Toma ncomo argumento e imprime el resultado.

Explicación

H              divide input by 2
 Ċ             round up to get first n to recurse
  r            inclusive range from that to n
   µ           (chain separator)
    Ṗ          remove n itself from the range
     ߀        call self recursively on each value in the range
       S       sum results
        ȯ1     if sum was zero, return one
PurkkaKoodari
fuente
7

Ruby, 34 32 bytes

Utiliza una fórmula de la página OEIS para los números de Narayana-Zidek-Cappell .

Editar: Eliminé los paréntesis usando la precedencia del operador gracias a feersum y Neil.

f=->x{x<4?1:2*f[x-1]-x%2*f[x/2]}
Sherlock9
fuente
¿Seguramente no necesitas paréntesis x%2?
feersum
Bueno, no si pones x%2*al menos.
Neil
@feersum y Neil Gracias a ambos
Sherlock9
Las ediciones de preguntas anteriores sugirieron que la fórmula era x<2?... esto lo hace mucho más claro, gracias
Neil
6

Python 2, 48 42 38 36 bytes

Algoritmo tomado de la página OEIS. n<3puede cambiarse a n<4sin efecto. Devuelve el nnúmero th, donde nes un entero positivo.

a=lambda n:n<3or 2*a(n-1)-n%2*a(n/2)

Pruébalo en línea

mbomb007
fuente
5

05AB1E, 16 bytes

Una solución iterativa como 05AB1E no tiene funciones.

X¸sGDN>;ï£Os‚˜}¬

X¸               # initialize a list with 1
  sG          }  # input-1 number of times do
    D            # duplicate current list
     N>;ï£       # take n/2 elements from the list
          O      # sum those elements
           s‚˜   # add at the start of the list
               ¬ # get the first element and implicitly print

Pruébalo en línea

Emigna
fuente
5

C, 38

Una traducción del algoritmo OEIS. ¡Simplemente no hay suficiente código C por aquí!

f(n){return n<3?:2*f(n-1)-n%2*f(n/2);}
owacoder
fuente
Como n<3?:(...)funciona
LegionMammal978
2
Es una extensión GCC (parece funcionar también en clang) que evalúa el condicional en sí mismo si falta la expresión media. Vea la página relevante de GCC y esta pregunta SO para más detalles.
owacoder
4

Python 3, 67 bytes

def f(n):
 x=1,
 for i in range(n):x+=sum(x[-i//2:]),
 print(x[-1])

Una función que toma datos a través de argumentos e imprime en STDOUT. Esta es una implementación directa de la definición.

Cómo funciona

def f(n):               Function with input target term index n
 x=1,                   Initialise term list x as tuple (1)
 for i in range(n):...  For all term indices in [0,n-1]...
 x[-i//2:]              ..yield the previous floor(i/2) terms...
 x+=sum(...)            ...and append their sum to x
 print(x[-1])           Print the last term in x, which is the nth term

Pruébalo en Ideone

TheBikingViking
fuente
3

Mathematica, 38 bytes

If[#<4,1,2#0[#-1]-#~Mod~2#0[(#-1)/2]]&

Función anónima. Toma 𝑛 como entrada y devuelve 𝑓 (𝑛) como salida. Basado en la solución Ruby.

LegionMammal978
fuente
No hay construido en?
Loco
@Insane No, no hay incorporado.
LegionMammal978
¡Simplemente asombroso!
Loco
2

Haskell, 34 bytes

f 1=1
f n=sum$f<$>[n-div n 2..n-1]

Ejemplo de uso: f 14-> 1308.

Una implementación directa de la definición.

nimi
fuente
2

Java, 63 bytes

int z(int n){return n<3?1:n%2>0?(2*z(n-1)-z(n/2)):(2*z(n-1));}
usuario902383
fuente
1

Go, 63 bytes

func f(i int) int{if(i<4){return 1};return 2*f(i-1)-i%2*f(i/2)}

Más o menos un puerto directo de la respuesta C

Sefa
fuente
0

PHP, 81 bytes

Este es un programa completo sin recursividad. Se puede definir una función recursiva en 52 bytes (podría ser posible superar eso), pero eso es solo un puerto bastante aburrido de la respuesta de sherlock9 (y falla si pides f (100) o más), así que estoy poniendo esto versión más larga y más interesante

<?php for($i=$argv[1];$j=$i;$i--)for(;--$j*2>=$i;)$a[$j]+=$a[$i]?:1;echo$a[1]?:1;

Causa muchos avisos (O [n]) pero está bien.

usuario55641
fuente
O(n)avisos? ¿Eh?
gato
Los avisos son un tipo de error no crítico que no detiene la ejecución y generalmente se silencian en entornos de producción. cada vez que intente obtener el valor de una variable no declarada o un desplazamiento indefinido en una matriz, recibirá un aviso. Este programa intenta obtener el valor de los desplazamientos indefinidos de O [n] (y también un par de variables no declaradas) para que obtenga avisos de O [n].
user55641
0

R, 55 bytes

x[1]=1;for(i in 2:10){x[i]=sum(x[i-1:floor(i/2)])};x[9]

Cambie 10el forciclo y x[9]obtenga el índice que desee el usuario.

Remojo
fuente
Aquí hay una versión recursiva que tiene 54 bytes de largo: f=function(n)ifelse(n<4,1,2*f(n-1)-n%%2*f(floor(n/2)))
DSkoog
0

JavaScript 54 52

f=n=>Math.round(n<3?1:2*f(n-1)-n%2*f(parseInt(n/2)))

Basado en la respuesta C.

  • Se guardaron 2 bytes al usar en parseIntlugar deMath.floor
usuario2428118
fuente
0

Arce, 46 44 bytes

`if`(n<4,1,2*f(n-1)-(n mod 2)*f(floor(n/2)))

Uso:

> f:=n->`if`(n<4,1,2*f(n-1)-(n mod 2)*f(floor(n/2)));
> seq( f(i), i = 1..10 );
  1, 1, 1, 2, 3, 6, 11, 22, 42, 84
DSkoog
fuente
0

R, 63 bytes

f=function(n,a=0)if(n<2)1 else{for(i in n-1:(n%/%2))a=a+f(i);a}

a=0se agrega por defecto porque me ahorra dos llaves. La función se llama recursivamente a sí misma según sea necesario.

usuario5957401
fuente