Contando fuentes

17

Una fuente es una disposición de monedas en filas para que cada moneda toque dos monedas en la fila debajo de ella, o esté en la fila inferior, y la fila inferior esté conectada. Aquí hay una fuente de 21 monedas:

De http://mathworld.wolfram.com/Fountain.html

Su desafío es contar cuántas fuentes diferentes se pueden hacer con un número determinado de monedas.

Se le dará como entrada un número entero positivo n. Debe generar la cantidad de nfuentes de monedas diferentes que existen.

Reglas estándar de E / S, lagunas estándar prohibidas. Las soluciones deberían poder calcularse n = 10en menos de un minuto.

Salida deseada para n = 1 ... 10:

1, 1, 2, 3, 5, 9, 15, 26, 45, 78

Esta secuencia es OEIS A005169 .

Este es el código de golf. Pocos bytes ganan.

code-golf sequence combinatorics isaacg
fuente
¿Existe alguna npara la cual se debe garantizar que el programa funcione? (es decir, después de lo cual puede romperse)
quintopia
@quintopia Debería funcionar para todos n, hasta limitaciones de tipo de datos, hardware, etc.
isaacg

Respuestas:

3

Python, 57 bytes

f=lambda n,i=0:sum(f(n-j,j)for j in range(1,i+2)[:n])or 1

Como se observa en OEIS , si desplaza cada fila medio paso en relación con la fila debajo de ella, los tamaños de columna forman una secuencia de enteros positivos con un paso ascendente máximo de 1.

La función f(n,i)cuenta las secuencias con suma ny último número i. Estos se pueden sumar recursivamente para cada elección del siguiente tamaño de columna de 1a i+1, que es range(1,i+2). Truncar para range(1,i+2)[:n]evitar que las columnas usen más monedas de las que quedan, evitando tener que decir que los negativos ndan 0. Además, evita un caso base explícito, ya que la suma vacía es 0y no es recurrente, pero f(0)debe establecerse en su 1lugar, para lo cual es or 1suficiente (como lo haría +0**n).

xnor
fuente
17 bytes en Pyth:M|sgL-Gd<ShHG1gQ0
isaacg
5

Mathematica, 59 bytes

SeriesCoefficient[1-Fold[1-x^#2/#&,Range[#,0,-1]],{x,0,#}]&

Basado en el programa Mathematica en OEIS de Jean-François Alcover.

alephalpha
fuente
¿Puedes reescribir esto como una fórmula (solo quiero comparar con la fórmula que encontré)? Simplemente no puedo leer Mathematica =)
flawr
@flawr La función generadora de la secuencia es 1/(1-x/(1-x^2/(1-x^3/(1-x^4/(1-x^5/(...)))))).
alephalpha
Gracias por la explicación, que es de hecho un acercamiento agradable si usted tiene un potente CAS =) tal
flawr
3

Haskell 60 48 bytes

¡Gracias a @nimi por proporcionar una solución mucho más corta!

n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1
(#1)

Versión antigua.

t n p|p>n=0|p==n=1|p<n=sum[t (n-q) q|q<-[1..p+1]]
s n=t n 1

La función que calcula el valor es la simplementación de la fórmula recursiva que se encuentra aquí: https://oeis.org/A005169

falla
fuente
Un error: la llamada recursiva es t (n-p) q. Golf en las extremidades: utilizar un operador infijo para t, intercambiar los guardias y utilizar mapen lugar de la lista por comprensión: n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1. sse convierte s=(#1), pero no es necesario que le dé un nombre a la función principal, por lo que (#1)es suficiente. 48 bytes.
nimi
Muchas gracias por las pistas! Acabo de empezar a aprender los conceptos básicos de Haskell. Voy a tener que aprender sobre cómo el uso de #y $aquí primero =)
error
Un poco de explicación: #es una función infija definida por el usuario como +, *, etc., están funciones predefinidas infijos. $es otra forma de ajustar la precedencia (además de paréntesis) f (g (h x))-> f$g$h xo en nuestro caso sum(map(...)[...])-> sum$map(...)[...].
nimi
Gracias, es bastante útil saberlo, ¡agradezco su explicación!
flawr
3

Haskell, 43 bytes

n%i=sum[(n-j)%j|j<-take n[1..i+1]]+0^n
(%0)

Ver la respuesta de Python para obtener una explicación.

Misma longitud con minmás que take:

n%i=sum[(n-j)%j|j<-[1..min(i+1)n]]+0^n
(%0)
xnor
fuente
1

Matlab, 115105 bytes

function F=t(n,varargin);p=1;if nargin>1;p=varargin{1};end;F=p==n;if p<n;for q=1:p+1;F=F+t(n-p,q);end;end

Implementación de la fórmula recursiva que se encuentra aquí: https://oeis.org/A005169

function F=t(n,varargin);
p=1;
if nargin>1
    p=varargin{1};
end;
F=p==n;
if p<n;
    for q=1:p+1;
        F=F+t(n-p,q);
    end;
end;
falla
fuente
1

Julia, 44 43 bytes

f(a,b=1)=a>b?sum(i->f(a-b,i),1:b+1):1(a==b)

Esto utiliza la fórmula recursiva en OEIS.

Explicación

function f(a, b=1)
    if a > b
        # Sum of recursing
        sum(i -> f(a-b, i), 1:b+1)
    else
        # Convert bool to integer
        1 * (a == b)
    end
end

¿Alguien más se ha dado cuenta de que el strike 44 es regular 44?

Máquina de fax
fuente
0

Python 3, 88 bytes

f=lambda n,p:sum([f(n-p,q)for q in range(1,p+2)])if p<n else int(p==n)
t=lambda n:f(n,1)
monopolo
fuente
0

JavaScript (ES6), 63

Implementando la fórmula recursiva en la página OEIS

F=(n,p=1,t=0,q=0)=>p<n?eval("for(;q++<=p;)t+=F(n-p,q)"):p>n?0:1
edc65
fuente