Fontanny jest układ monet w rzędach tak, że każda moneta porusza dwie monety w wierszu poniżej, lub jest w dolnym rzędzie, a dolny rząd jest podłączony. Oto fontanna na 21 monet:

Twoim zadaniem jest policzyć, jak wiele różnych fontann można stworzyć za pomocą określonej liczby monet.

Otrzymasz jako dane wejściowe dodatnią liczbę całkowitą n . Musisz npodać liczbę różnych fontann na monety, które istnieją.

Standardowe reguły we / wy, standardowe luki zabronione. Rozwiązania powinny być w stanie obliczyć n = 10w niecałą minutę.

Pożądana moc wyjściowa dla n = 1 ... 10:

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

Ta sekwencja to OEIS A005169 .

To jest kod golfowy. Wygrywa najmniej bajtów.

Python, 57 bajtów

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

Jak zaobserwowano w OEIS , jeśli przesuniesz każdy wiersz o pół kroku względem wiersza poniżej, rozmiary kolumn tworzą sekwencję dodatnich liczb całkowitych z maksymalnym krokiem w górę wynoszącym 1.

Funkcja f(n,i)zlicza sekwencje z sumą ni ostatnią liczbą i. Można je rekursywnie sumować dla każdego wyboru następnego rozmiaru kolumny od 1do i+1, czyli range(1,i+2). Obcinanie w celu range(1,i+2)[:n]uniemożliwienia kolumnom korzystania z większej liczby monet niż pozostało, unikając konieczności mówienia, że ​​wartość negatywna ndaje 0. Co więcej, unika się wyraźnego przypadku podstawowego, ponieważ pusta suma jest 0i nie powtarza się, ale zamiast tego f(0)należy ją ustawić na 1, co or 1wystarcza (jak by to było +0**n).

Mathematica, 59 bajtów

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

Na podstawie programu Mathematica na OEIS autorstwa Jean-François Alcover.

Haskell, 60 48 bajtów

Dzięki @nimi za dostarczenie krótszego rozwiązania!

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

Stara wersja.

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

Funkcją obliczającą wartość jest simplementacja wzoru rekurencyjnego znalezionego tutaj: https://oeis.org/A005169

Haskell, 43 bajty

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

Zobacz odpowiedź na Python na wyjaśnienia.

Ta sama długość z minzamiast take:

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

Pyth, 21 20 bajtów

Ms?>GHgL-GHShHqGHgQ1

Wypróbuj online. Zestaw testowy.

Jest to bezpośrednia implementacja formuły rekurencyjnej na stronie OEIS , podobnie jak odpowiedź Matlaba .

Matlab, 115 105 bajtów

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

Wdrożenie rekurencyjnej formuły znalezionej tutaj: 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;

Julia, 44 43 bajty

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

Wykorzystuje rekurencyjną formułę w OEIS.

Wyjaśnienie

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

Czy ktoś jeszcze zauważył, że strajk przez 44 jest normalny 44?

Python 3, 88 bajtów

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)

JavaScript (ES6), 63

Wdrożenie formuły rekurencyjnej na stronie OEIS

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