23

Heute ist es Ihr Ziel, die Ganzzahlen a und b zu finden, denen eine nicht negative Ganzzahl n gegeben ist, so dass:

(3 + sqrt (5)) ^ n = a + b * sqrt (5)

Sie sollten ein Programm oder eine Funktion schreiben, die den Parameter n verwendet und a und b in einem Format Ihrer Wahl ausgibt .

Es gelten Standardlücken. Darüber hinaus ist es beabsichtigt, dass Sie das obige Problem mithilfe grundlegender Arithmetik selbst implementieren. Daher können Sie möglicherweise keine eingebauten Funktionen für die exakte Algebra, keine Rationalen oder Funktionen verwenden, die nicht triviale mathematische Konstrukte implementieren (z. B. die Lucas-Sequenz ).

Kürzester Code in Bytes gewinnt.

Beispiel Ein- / Ausgabe:

0 → 1, 0
1 → 3, 1
2 → 14, 6
3 → 72, 32
4 → 376, 168
5 → 1968, 880
6 → 10304, 4608
7 → 53952, 24128
8 → 282496, 126336
9 → 1479168, 661504

code-golf arithmetic orlp
quelle

3

Dyalog APL, 18 Bytes

((3∘×+5 1×⌽)⍣⎕)1 0

Dies ist ein Programm, das Eingaben durchläuft ⎕.

 (         )         Monadic train:
  3∘×                3 times argument
     +               Plus
      5 1×⌽          (5 1) times the reverse
(           ⍣⎕)      Apply that function (input) times
               1 0   starting with (1 0)

Die hier verwendeten Funktionen wurden lange vor April 2015 implementiert, sodass diese Antwort gültig ist.

Probieren Sie es hier aus . Beachten Sie, dass tryapl.org eine begrenzte Teilmenge von Dyalog ist und nicht unterstützt ⎕.

Lirtosiast
quelle

16

Oktave, 26 Bytes

[3 5;1 3]**input('')*[1;0]

Weil ( a + b * sqrt (5)) * (3 + sqrt (5)) = ( 3a + 5b ) + ( a + 3b ) * sqrt (5),

Multiplizieren des Eingabevektors

| 1 |    /* a = 1 */
| 0 |    /* b = 0 */

was für 1 = (3 + sqrt (5)) ^ 0 durch Matrix steht

| 3 5 |
| 1 3 |

scheint natürlich. Anstatt die nZeiten zu schleifen , erhöhen wir die Matrix auf die Potenz von nund multiplizieren sie dann mit dem Eingangsvektor.

pawel.boczarski
quelle

Sie verkaufen sich kurz, [3 5;1 3]**input('')*[1;0]ist 26 Bytes, nicht 41.

Orlp

3

@(n)[3 5;1 3]^n*[1;0](Funktionshandle) würde dir fünf Zeichen sparen, mut nette Idee!

Fehler

14

Python 2, 50

a=1;b=0
exec"a,b=3*a+5*b,3*b+a;"*input()
print a,b

Multipliziert mit 3+sqrt(5)immer wieder durch seine Wirkung auf das Paar (a,b)darstellt a+b*sqrt(5). Entspricht dem Beginn mit dem Spaltenvektor [1,0]und den Linksmultiplikationszeiten nmit der Matrix [[3,5],[1,3]].

xnor
quelle

12

Julia, 22 20 Bytes

n->[3 5;1 3]^n*[1;0]

Dies erzeugt eine Lambda-Funktion, die eine einzelne Ganzzahl als Eingabe verwendet und einen 2-Element-Vektor von Ganzzahlen entsprechend der Lösung [a, b] zurückgibt. Um es zu nennen, geben Sie ihm einen Namen, z f=n->....

Beginnen Sie mit der Multiplikation

Anfänglich erweitern

Wir können dann die rechte Seite dieser Gleichung in eine zweispaltige Matrix übersetzen, wobei die erste dem Koeffizienten von a und die zweite dem Koeffizienten von b entspricht :

Matrix

Multiplizieren Sie diese Matrix mit sich selbst n- mal, dann multiplizieren Sie rechts mit dem Spaltenvektor (1, 0) und POOF! Out öffnet den Lösungsvektor.

Beispiele:

julia> println(f(0))
[1,0]

julia> println(f(5))
[1968,880]

Alex A.
quelle

8

J, 20 Bytes

+/@:*(3 5,.1 3&)&1 0

Multiplizieren Sie den Vektor [1 0]mit den Matrixzeiten [[3 5] [1 3]] n.

2 Bytes gespart dank @algorithmshark.

Verwendung und Test:

   (+/@:*(3 5,.1 3&)&1 0) 5
1968 880

   (+/@:*(3 5,.1 3&)&1 0) every i.6
   1   0
   3   1
  14   6
  72  32
 376 168
1968 880

randomra
quelle

Sie können durch die Nutzung der stillschweigenden Adverb Parsing an 20 nach unten: +/ .*(3 5,:1 3&)&1 0.

Algorithmushai

@algorithmshark Danke, obwohl warum (+/@:*&(3 5,.1 3)&1 0)funktioniert und (+/@:*&1 0&(3 5,.1 3))nicht? Sollte die zweite nicht richtig sein und die erste tauschen?

Randomra

Verstanden, sie verbinden sich, wie ich erwartet hatte, aber das Äußere &macht das Ein- / Ausschalten, so dass Sie den Eingang auf der linken Seite während des Einschaltens modifizieren (im Gegensatz zu der normalen Modifikation auf der rechten Seite).

Randomra

7

Pyth, 20 Bytes

u,+*3sGyeG+sGyeGQ,1Z

udie im allgemeinen reduziert ist, wird hier als Wiederholungsschleife verwendet. Die Aktualisierungsfunktion ist G-> ,+*3sGyeG+sGyeG, wobei Ges sich um ein 2-Tupel handelt. Diese Funktion übersetzt nach 3*sum(G) + 2*G[1], sum(G) + 2*G[1]. sist sum, yist *2.

isaacg
quelle

Ich habe @ randomras Antwort Ihrer vorgezogen, weil seine / ihre 16 Minuten zuvor gepostet wurde, sorry.

Orlp

5

APL (22)

{⍵+.×⍨2 2⍴3 5 1}⍣⎕⍨2↑1

Erläuterung:

{... }⍣⎕⍨2↑1: Lesen Sie eine Zahl und führen Sie die folgende Funktion so oft aus, [1,0]wie Sie sie eingegeben haben.
- 2 2⍴3 5 1: die Matrix [[3,5],[1,3]]
- ⍵+.×⍨: multipliziere die erste Zahl in ⍵ mit 3, die zweite mit 5 und addiere sie, dies ist die neue erste Zahl; dann multipliziere die erste Zahl in ⍵ mit 1, die zweite mit 3 und summiere diese, das ist die neue zweite Zahl.

Marinus
quelle

1

Awww yiss, APL.

Nit

5

Jelly , 13 Bytes

5W×U++Ḥ
2BÇ³¡

Probieren Sie es online!

Wie es funktioniert

5W×U++Ḥ    Helper link. Argument: [a, b]

5W         Yield [5].
  ×U       Multiply it by the reverse of [a, b]. This yields [5b, a].
    +      Hook; add the argument to the result. This yields [a + 5b, a + b].
     +Ḥ    Fork; add the doubled argument ([2a, 2b]) to the result.
           This yields [3a + 5b, a + 3b].

2BÇ³¡      Main link. Argument: n

2B         Convert 2 to binary, yielding [1, 0].
    ¡      Repeat:
  Ç            Apply the helper link...
   ³           n times.

Dennis
quelle

Nein, ich bin mir ziemlich sicher, dass es Jelly schon lange vor der Erschaffung des Internets gegeben hat: P

Conor O'Brien

1

@ Doᴡɴɢᴏᴀᴛ Für nicht konkurrierende Antworten ziehe ich es vor, die Byteanzahl in der zweiten Zeile zu belassen. Dies verhindert, dass die Antwort in Bestenlisten und User-Skripten nach oben steigt, was unfair erscheint.

Dennis

3

Mathematica, 31

Nest[{{3,5},{1,3}}.#&,{1,0},#]&

Alephalpha
quelle

3

CJam, 21 Bytes

0X{_2$3*+@5*@3*+}li*p

Probieren Sie es online aus.

Wie es funktioniert

0X       " Stack: [ 0 1 ]                                ";
li{      " Do int(input()) times:                        ";
  _2$    " Stack: [ a b ] -> [ a b b a ]                 ";
  3*+    " Stack: [ a b b a ] -> [ a b (b+3a) ]          ";
  @5*@3* " Stack: [ a b (b+3a) ] -> [ (b+3a) 5a 3b ]     ";
  +      " Stack: [ (b+3a) 5a 3b ] -> [ (b+3a) (5a+3b) ] ";
}*       "                                               ";
p        " Print topmost stack item plus linefeed.       ";
         " Print remaining stack item (implicit).        ";

Dennis
quelle

3

Javascript, 63 61 Bytes

Ich verwende eine rekursive Auswertung des Binomials: (x + y) ^ n = (x + y) (x + y) ^ {n-1}

Neu (danke an @ edc65)

F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

Alt

F=n=>{for(i=y=0,x=1;i<n;i++)[x,y]=[3*x+5*y,x+3*y];return [x,y]}

Fehler
quelle

1

Vielleicht möchten Sie Ihre Formel bearbeiten. Wir haben kein MathJax mehr.

Alex A.

Ich dachte, es wurde erst vor ein paar Tagen vorgestellt?

Fehler

Ja, aber es hat die Stack-Schnipsel durcheinander gebracht, also musste es deaktiviert werden.

Alex A.

Ich zähle 63, wie es ist, und kann um F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

edc65 13.04.15

n=>[...Array(n)].map(_=>[x,y]=[3*x+5*y,x+3*y],y=0,x=1)[n-1]gleiche Länge

l4m2

2

C 114 Bytes

g(n){int i,a[2]={1,0},b[2];for(i=0;i<n;i++)*b=*a*3+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];printf("%d,%d",*a,a[1]);}

Dies implementiert die Matrixmultiplikation auf langweilige Weise. Für eine unterhaltsamere (Zitat: "awesomely horrific") 238-Byte-Lösung suchen Sie nicht weiter!

f(n){int p[2][n+3],i,j,k=0,a[2]={0};for(j=0;j<n+3;j++)p[0][j]=0;*p[1]=0;(*p)[1]=1;for(j=0;j<n;j++,k=!k)for(i=1;i<n+3;i++)p[!k][i]=p[k][i-1]+p[k][i];for(i=1;i<n+2;i++)a[!(i%2)]+=p[k][i]*pow(3,n+1-i)*pow(5,(i-1)/2);printf("%d,%d",*a,a[1]);}

Entwirrt:

g(n){
    int i,a[2]={1,0},b[2];
    for(i=0;i<n;i++)
        *b=3**a+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];
    printf("%d,%d",*a,a[1]);
}

Dies könnte wahrscheinlich etwas verkürzt werden. Probieren Sie ein Testprogramm online aus !

BrainSteel
quelle

1

Dies verwendet einen ziemlich

komplizierten

@orlp Ich konnte mir keinen kürzeren Algorithmus für diese Sprache vorstellen. Ich dachte, das würde klappen, aber es ist irgendwie außer Kontrolle geraten, haha. Das Implementieren der Matrixmultiplikation von Hand könnte sehr wohl kürzer sein.

BrainSteel

1

Upvote, weil das furchtbar schrecklich ist.

Kirbyfan64sos

2

k2 - 22 char

Funktion mit einem Argument.

_mul[(3 5;1 3)]/[;1 0]

_mulIst die Matrixmultiplikation so curry wir sie mit der Matrix (3 5;1 3)und schlagen sie dann mit dem funktionalen Potenzadverb: f/[n;x]gilt ffür x, ntimes. Wieder curry wir es, diesmal mit dem Startvektor 1 0.

  _mul[2 2#3 5 1]/[;1 0] 5
1968 880
  f:_mul[2 2#3 5 1]/[;1 0]
  f'!8  /each result from 0 to 7 inclusive
(1 0
 3 1
 14 6
 72 32
 376 168
 1968 880
 10304 4608
 53952 24128)

Dies funktioniert in Kona nicht, da es aus irgendeinem Grund f/[n;x]nicht korrekt implementiert ist. Da nur die n f/xSyntax funktioniert, liegt der kürzeste Fix {x _mul[(3 5;1 3)]/1 0}bei 23 Zeichen.

algorithmshark
quelle

Wow. Diese Verwendung des Currys ist so klug, dass ich der Meinung bin, dass meine K-Antwort dumm ist. Wie auch immer, ich habe das Problem, das Sie in Kona gefunden haben, in ihrem Bug Tracker angesprochen .

kirbyfan64sos

Zu Ihrer Information, dies wurde kürzlich in Kona behoben .

kirbyfan64sos

2

isiert, 25 Bytes (20 Zeichen)

({:{2,4}·x±Σx:}$1)∘1

Ich habe mir etwas Besseres erhofft, aber es werden einfach zu viele Zahnspangen benötigt, um es kompetent zu machen. Die Rangfolge der Bediener ist für das Golfen nicht optimal.

Es wird erwartet, dass sich die Eingabe im $ 1-Speicherplatz befindet. Das funktioniert also:

ised '@1{9};' '({:{2,4}·x±Σx:}$1)∘1'

Bei n = 0 wird die Null übersprungen (Ausgänge 1 anstelle von 1 0). Wenn das ein Problem ist, ersetzen Sie das Finale 1durch ~[2].

orion
quelle

2

Im Ernst, 32 Bytes, nicht konkurrierend

,╗43/12`╜";)@4*≈(6*-"£n.X4ì±0`n

Hex Dump:

2cbb34332f313260bd223b2940342af728362a2d229c6e2e58348df130606e7f

Probieren Sie es online

Offensichtlich kein Kandidat für kürzeste, aber zumindest die Methode ist originell. (Unter Hinweis darauf, dass ein solches Problem notwendigerweise auf eine Lucas-Sequenz hinweist, wie in der Beschreibung erwähnt, generiert dieses Programm aufeinanderfolgende Terme der Sequenzen unter Verwendung der Wiederholungsrelation

a_n = 6 * a_ {n-1} - 4 * a_ {n-2}.)

Quintopie
quelle

1

Haskell, 41 Bytes

(iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!)

Anwendungsbeispiel: (iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!) 8-> (282496,126336).

nimi
quelle

1

C / C ++ 89 Bytes

void g(int n,long&a,long&b){if(n){long j,k;g(n-1,j,k);a=3*j+5*k;b=j+3*k;}else{a=1;b=0;}}

Formatiert:

    void g(int n, long&a, long&b) {
if (n) {
    long j, k;
    g(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
} else {
    a = 1;
    b = 0;
}}

Gleiches Konzept:

void get(int n, long &a, long& b) {
    if (n == 0) {
        a = 1;
        b = 0;
        return;
    }
    long j, k;
    get(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
}

Der Prüfstand:

#include <iostream>
using namespace std;    
int main() {
    long a, b;
    for (int i = 0; i < 55; i++) {
        g(i, a, b);
        cout << i << "-> " << a << ' ' << b << endl;
    }
    return 0;
}

Die Ausgabe:

0-> 1 0
1-> 3 1
2-> 14 6
3-> 72 32
4-> 376 168
5-> 1968 880
6-> 10304 4608
7-> 53952 24128
8-> 282496 126336
9-> 1479168 661504
10-> 7745024 3463680
11-> 40553472 18136064
12-> 212340736 94961664
13-> 1111830528 497225728
14-> 5821620224 2603507712
15-> 30482399232 13632143360
16-> 159607914496 71378829312
17-> 835717890048 373744402432
18-> 4375875682304 1956951097344
19-> 22912382533632 10246728974336
20-> 119970792472576 53652569456640
21-> 628175224700928 280928500842496
22-> 3289168178315264 1470960727228416
23-> 17222308171087872 7702050360000512
24-> 90177176313266176 40328459251089408
25-> 472173825195245568 211162554066534400
26-> 2472334245918408704 1105661487394848768

philn
quelle

Willkommen auf der Seite und schöne erste Antwort!

DJMcMayhem

0

K, 37 Bytes

f:{:[x;*(1;0)*_mul/x#,2 2#3 1 5;1 0]}

oder

f:{:[x;*(1;0)*_mul/x#,(3 1;5 3);1 0]}

Sie sind beide dasselbe.

kirbyfan64sos
quelle

0

Python 3, 49 Bytes

w=5**0.5;a=(3+w)**int(input())//2+1;print(a,a//w)

obwohl auf meinem Computer, gibt dies nur die richtige Antwort für Eingaben im Bereich 0 <= n <= 18.

Dies implementiert die geschlossene Formularformel

w = 5 ** 0.5
u = 3 + w
v = 3 - w
a = (u ** n + v ** n) / 2
b = (u ** n - v ** n) / (2 * w)

und nutzt die Tatsache, dass das v ** nTeil klein ist und eher durch Rundung als durch direkte Berechnung berechnet werden kann.

quelle

1

Dies ist keine gültige Lösung (Sie müssen ein beliebiges n unterstützen ), aber da Sie bei weitem nicht die kürzeste sind, sehe ich keinen Grund für eine Ablehnung. Es ist eine coole Lösung.

Orlp

0

Schema, 97 Bytes

(define(r n)(let s([n n][a 1][b 0])(if(= 0 n)(cons a b)(s(- n 1)(+(* a 3)(* b 5))(+ a(* b 3))))))

Pinguino
quelle

0

C 71 Bytes (60 mit vorinitialisierten Variablen)

Noch Spielraum fürs Golfen, aber nur um zu beweisen, dass C nicht "furchtbar schrecklich" sein muss.

f(int n,int*a){for(*a=1,a[1]=0;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

Wenn die Werte in a auf {1,0} initialisiert sind, ist das besser.

f(int n,int*a){for(;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

Dies geschieht iterativ unter Verwendung der Zuordnungen a-> 3a + 5b, b-> a + 3b, wobei jedoch eine temporäre Variable vermieden wird, indem stattdessen a aus dem neuen Wert von b berechnet wird.

Alchymist
quelle

Ihre Lösung

läuft

@orlp - Das ist C für dich. Zugegeben, diese Lösung schlägt früher als andere fehl, da die Zwischenberechnung in Klammern angegeben ist. Sie würde jedoch ohnehin nur ein paar zusätzliche Schritte ausführen, sofern ich den Datentyp nicht ändere. Lohnt es sich, die Frage explizit zu ändern, um den Bereich anzugeben, den Sie unterstützen möchten? Wahrscheinlich zu spät.

Alchymist

Es gibt keinen zu unterstützenden Bereich. Für jede Eingabe sollte eine geeignete Lösung funktionieren. In C bedeutet dies, dass Sie Ganzzahlen mit beliebiger Breite implementieren müssen, sorry = /

orlp

Schlagen Sie a[*a=1]=0stattdessen vor*a=1,a[1]=0

ceilingcat

0

(nicht konkurrierend) Jelly, 10 Bytes

31,53Dæ*³Ḣ

Probieren Sie es online!

Verwendet Matrix. Berechnet ([[3,1], [5,3]] ** input ()) [0].

Undichte Nonne
quelle

Berechnung (3 + sqrt (5)) ^ n genau

Antworten:

Dyalog APL, 18 Bytes

Oktave, 26 Bytes

Python 2, 50

Julia, 22 20 Bytes

J, 20 Bytes

Pyth, 20 Bytes

APL (22)

Jelly , 13 Bytes

Wie es funktioniert

Mathematica, 31

CJam, 21 Bytes

Wie es funktioniert

Javascript, 63 61 Bytes

C 114 Bytes

k2 - 22 char

isiert, 25 Bytes (20 Zeichen)

Im Ernst, 32 Bytes, nicht konkurrierend

Haskell, 41 Bytes

K, 37 Bytes

Python 3, 49 Bytes

Schema, 97 Bytes

(nicht konkurrierend) Jelly, 10 Bytes