Ein Brunnen ist eine Anordnung von Münzen in Reihen, so dass jede Münze zwei Münzen in der Reihe darunter berührt oder sich in der unteren Reihe befindet und die untere Reihe verbunden ist. Hier ist ein 21-Münzen-Brunnen:

Ihre Herausforderung besteht darin, zu zählen, wie viele verschiedene Brunnen mit einer bestimmten Anzahl von Münzen hergestellt werden können.

Sie erhalten als Eingabe eine positive ganze Zahl n. Sie müssen die Anzahl der verschiedenen vorhandenen nMünzbrunnen ausgeben.

Standard-E / A-Regeln, Standard-Regelungslücken verboten. Lösungen sollten n = 10in weniger als einer Minute rechnen können .

Gewünschte Ausgabe für n = 1 ... 10:

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

Diese Sequenz ist OEIS A005169 .

Das ist Code Golf. Wenigste Bytes gewinnt.

Python, 57 Bytes

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

Wie in OEIS beobachtet , bilden die Spaltengrößen eine Folge positiver Ganzzahlen mit einem maximalen Aufwärtsschritt von 1, wenn Sie jede Zeile um einen halben Schritt relativ zur darunter liegenden Zeile verschieben.

Die Funktion f(n,i)zählt die Folgen mit Summe nund letzter Nummer i. Diese können für jede Auswahl der nächsten Spaltengröße von 1bis i+1, also rekursiv aufsummiert werden range(1,i+2). Das Abschneiden auf range(1,i+2)[:n]verhindert , dass Spalten mehr Münzen verbrauchen als übrig bleiben, und vermeidet es, zu sagen, dass Negative ngeben 0. Darüber hinaus wird ein expliziter Basisfall vermieden, da die leere Summe 0rekursiv ist und nicht, sondern f(0)auf gesetzt 1werden muss, wofür or 1(wie gewünscht) ausreicht +0**n.

Mathematica, 59 Bytes

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

Basierend auf dem Mathematica-Programm zu OEIS von Jean-François Alcover.

Haskell, 60 48 Bytes

Vielen Dank an @nimi für die Bereitstellung einer viel kürzeren Lösung!

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

Alte Version.

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

Die Funktion zur Berechnung des Wertes ist die sImplementierung der hier angegebenen rekursiven Formel: https://oeis.org/A005169

Haskell, 43 Bytes

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

Siehe Python-Antwort für eine Erklärung.

Gleiche Länge mit minanstatt take:

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

Pyth, 21 bis 20 Bytes

Ms?>GHgL-GHShHqGHgQ1

Probieren Sie es online aus. Testsuite.

Dies ist eine direkte Implementierung der rekursiven Formel auf der OEIS-Seite , wie die Matlab-Antwort .

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

Die Implementierung der rekursiven Formel finden Sie hier: 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 Bytes

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

Dies verwendet eine rekursive Formel in OEIS.

Erläuterung

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

Hat jemand anderes bemerkt, dass Strike Through 44 regulär 44 ist?

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)

JavaScript (ES6), 63

Implementierung der rekursiven Formel auf der OEIS-Seite

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