Binäre Wiederholungssequenzen

10

Eine binäre Wiederholungssequenz ist eine rekursiv definierte Sequenz der folgenden Form:

Definition der binären Wiederholungssequenz

Dies ist eine Verallgemeinerung der Fibonacci ( x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1) - Sequenz und der Lucas ( x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1) -Sequenz.

Die Herausforderung

In Anbetracht n, x, y, a, alpha, und betain jedem vernünftigen Format, Ausgabe der nth Laufzeit der entsprechenden binären Rezidiv - Sequenz.

Regeln

  • Sie können wählen, ob die Sequenz entweder 1-indiziert oder 0-indiziert sein soll, aber Ihre Auswahl muss über alle Eingaben hinweg konsistent sein, und Sie müssen Ihre Auswahl in Ihrer Antwort notieren.
  • Sie können davon ausgehen, dass keine ungültigen Eingaben angegeben werden (z. B. eine Sequenz, die vor endet n, oder eine Sequenz, die auf undefinierte Begriffe verweist, wie F(-1)oder F(k)wo k > n). Infolgedessen xund ywird immer positiv sein.
  • Die Ein- und Ausgänge sind immer Ganzzahlen innerhalb der Grenzen des natürlichen Ganzzahltyps Ihrer Sprache. Wenn Ihre Sprache unbegrenzte Ganzzahlen hat, liegen die Ein- und Ausgänge innerhalb des Bereichs [2**31, 2**31-1](dh des Bereichs für eine 32-Bit-Ganzzahl mit vorzeichenbehafteten Zweierkomplementen).
  • aenthält immer genau yWerte (gemäß Definition).

Testfälle

Hinweis: Alle Testfälle sind 0-indiziert.

x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1, n = 6 => 13
x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1, n = 8 => 47
x = 3, y = 5, a = [2, 3, 5, 7, 11], alpha = 2, beta = 3, n = 8 => 53
x = 1, y = 3, a = [-5, 2, 3], alpha = 1, beta = 2, n = 10 => -67
x = 5, y = 7, a = [-5, 2, 3, -7, -8, 1, -9], alpha = -10, beta = -7, n = 10 => 39
Mego
quelle
Zählt die Annahme einer aumgekehrten Reihenfolge als angemessen?
Dennis
@ Tennis Ja, das tut es.
Mego
OK, danke für die Klarstellung.
Dennis

Antworten:

2

Gelee , 11 Bytes

⁴Cịæ.⁵ṭµ¡⁶ị

Probieren Sie es online aus!  1  |  2  |  3  |  4  |  5 

Wie es funktioniert

⁴Cịæ.⁵ṭµ¡⁶ị  Main link. Arguments: a; [x, y]; [α, β]; n (1-based)

       µ     Combine the links to the left into a chain.
        ¡    Execute that chain n times, updating a after each execution.
⁴              Yield [x, y].
 C             Complement; yield [1 - x, 1 - y].
  ị            Retrieve the elements of a at those indices.
               Indexing is 1-based and modular in Jelly, so this retrieves
               [a[-x], a[-y]] (Python syntax).
     ⁵         Yield [α, β].
   æ.          Take the dot product of [a[-x], a[-y]] and [α, β].
         ⁶   Yield n.
          ị  Retrieve the element of a at index n.
Dennis
quelle
2

Python 2, 62 Bytes

x,y,l,a,b=input();f=lambda n:l[n]if n<y else a*f(n-x)+b*f(n-y)

Eine direkte rekursive Lösung. Alle Eingaben werden von STDIN übernommen, mit Ausnahme neines Funktionsarguments, einer Aufteilung, die standardmäßig zulässig ist (wenn auch umstritten).

Es scheint keine Möglichkeit zu geben, Bytes mit and/oranstelle von if/elseweil l[n]Falsey als 0 gespeichert werden könnte.

xnor
quelle
2

Python 2, 59 Bytes

x,y,A,a,b,n=input()
exec'A+=a*A[-x]+b*A[-y],;'*n
print A[n]

Testen Sie es auf Ideone .

Dennis
quelle
2

JavaScript (ES6), 51 44 Byte

(x,y,z,a,b)=>g=n=>n<y?z[n]:a*g(n-x)+b*g(n-y)

Beachten Sie, dass die Funktion teilweise verwirrt ist, z. B. f(1,2,[1,1],1,1)(8)34 zurückgibt. Es würde 2 Byte kosten, um die Zwischenfunktionen unabhängig voneinander zu machen (derzeit funktioniert nur die zuletzt generierte Funktion korrekt).

Bearbeiten: 7 Bytes gespeichert dank @Mego, der darauf hinwies, dass ich übersehen hatte, dass das übergebene Array immer die ersten yElemente des Ergebnisses enthält.

Neil
quelle
@ Mego Ich weiß, dass ich oft Details von Fragen übersehen habe, aber das kam mir besonders subtil vor.
Neil
2

Haskell, 54 48 Bytes

l@(x,y,a,p,q)%n|n<y=a!!n|k<-(n-)=p*l%k x+q*l%k y
Damien
quelle
0

J, 43 Bytes

{:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.

Berechnet bei einer anfänglichen Folge von Termen A den nächsten Term n- mal unter Verwendung der Parameter x , y , α und β . Anschließend wählt es den n- ten Term in der erweiterten Sequenz aus und gibt ihn als Ergebnis aus.

Verwendungszweck

Da J nur 1 oder 2 Argumente unterstützt, gruppiere ich alle Parameter als Liste von Listen mit Boxen. Die anfänglichen Startwerte A sind zuerst, gefolgt von den Parametern von x und y als Liste, gefolgt von den Parametern von α und β als Liste und endend mit dem Wert n .

   f =: {:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.
   2 3 5 7 11;3 5;2 3;8
┌──────────┬───┬───┬─┐
│2 3 5 7 11│3 5│2 3│8│
└──────────┴───┴───┴─┘
   f 2 3 5 7 11;3 5;2 3;8
53
   f _5 2 3 _7 _8 1 _9;5 7;_10 _7;10
39
Meilen
quelle