Fontes de contagem

17

Uma fonte é o arranjo de moedas em linhas, de modo que cada moeda toque duas moedas na linha abaixo dela, ou esteja na linha inferior e a linha inferior seja conectada. Aqui está uma fonte de 21 moedas:

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

Seu desafio é contar quantas fontes diferentes podem ser feitas com um determinado número de moedas.

Você receberá como entrada um número inteiro positivo n. Você deve ngerar o número de fontes de moedas diferentes que existem.

Regras de E / S padrão, brechas padrão proibidas. As soluções devem poder calcular n = 10em menos de um minuto.

Saída desejada para n = 1 ... 10:

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

Esta sequência é OEIS A005169 .

Isso é código de golfe. Menos bytes ganha.

code-golf sequence combinatorics isaacg
fonte
Existe uma npara a qual o programa deve estar garantido para funcionar? (ou seja, após o qual ele pode se romper)
quintopia 26/12/15
@quintopia Ele deve funcionar para todos n, até limitações do tipo de dados, hardware, etc.
isaacg

Respostas:

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 observado em OEIS , se você alternar cada linha meia etapa em relação à linha abaixo dela, os tamanhos das colunas formarão uma sequência de números inteiros positivos com uma etapa máxima máxima de 1.

A função f(n,i)conta as seqüências com soma ne último número i. Eles podem ser somados recursivamente para cada escolha do tamanho da próxima coluna de 1a i+1, que é range(1,i+2). Truncar para range(1,i+2)[:n]impedir que as colunas usem mais moedas do que as restantes, evitando precisar dizer que as negativas ndão 0. Além disso, evita um caso base explícito, já que a soma vazia é 0e não se repete, mas f(0)precisa ser configurada como 1, para a qual or 1é suficiente (como seria +0**n).

xnor
fonte
17 bytes em Pyth:M|sgL-Gd<ShHG1gQ0
isaacg
5

Mathematica, 59 bytes

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

Baseado no programa Mathematica no OEIS de Jean-François Alcover.

alefalpha
fonte
Você pode reescrever isso como uma fórmula (eu só quero comparar com a fórmula que encontrei)? Eu simplesmente não consigo ler o Mathematica =)
flawr
@flawr A função geradora da sequência é 1/(1-x/(1-x^2/(1-x^3/(1-x^4/(1-x^5/(...)))))).
Alephalpha 26/12/2015
Obrigado pela explicação, que é de fato uma abordagem agradável se você tem um poderoso CAS =) tal
flawr
3

Haskell, 60 48 bytes

Obrigado à @nimi por fornecer uma solução bem mais curta!

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

Versão antiga.

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

A função que calcula o valor é a simplementação da fórmula recursiva encontrada aqui: https://oeis.org/A005169

flawr
fonte
Um bug: a chamada recursiva é t (n-p) q. Golfe dicas: usar um operador infix para t, trocar os guardas e usar mapem vez da compreensão da lista: n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1. storna-se s=(#1), mas você não precisa atribuir um nome à função principal, o que (#1)é suficiente. 48 bytes.
nimi
Muito obrigado pelas dicas! Comecei a aprender o básico de Haskell. Vou ter que aprender sobre isso como o uso de #e $aqui em primeiro lugar =)
flawr
Um pouco de explicação: #é uma função infix definido pelo usuário como +, *, etc. são predefinidas funções infixas. $é outra maneira de ajustar a precedência (além dos parênteses) f (g (h x))-> f$g$h xou, no nosso caso sum(map(...)[...])-> sum$map(...)[...].
nimi
Obrigado, é muito útil saber, agradeço a sua explicação!
flawr
3

Haskell, 43 bytes

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

Vejo resposta do Python para explicação.

Mesmo comprimento com mine não take:

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

Matlab, 115 105 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

Implementação da fórmula recursiva encontrada aqui: 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;
flawr
fonte
1

Julia, 44 43 bytes

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

Isso usa fórmula recursiva no OEIS.

Explicação

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

Alguém mais notou que o strike através do 44 é 44 regular ??

Maquina de fax
fonte
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
fonte
0

JavaScript (ES6), 63

Implementando a fórmula recursiva na 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
fonte