Definition

a (1) = 1
a (2) = 1
a (n) = a (na (n-1)) + a (na (n-2)) für n> 2 wobei n eine ganze Zahl ist

Aufgabe

Bei positiver Ganzzahl ngenerieren a(n).

Testfälle

Referenz

Obligatorisch OEIS A005185

code-golf sequence arithmetic Undichte Nonne
quelle

Verwandte .

Undichte Nonne

1

Können wir True in Sprachen zurückgeben, in denen es als 1 verwendet werden kann ?

Dennis

1

@ Tennis Wenn in dieser Sprache true gleich 1 ist, dann yes.

Undichte Nonne

4

Abgesehen von der OEIS-Verknüpfung kann es sinnvoll sein, auf GEB zu verweisen, wo die Sequenz zum ersten Mal aufgetaucht ist.

Martin Ender

1

Vervollständigen der Liste der GEB-bezogenen Sequenzherausforderungen.

Martin Ender

9

Retina , 84 83 79 74 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

.+
$*;1¶1¶
+`;(?=(1)+¶(1)+)(?=(?<-1>(1+)¶)+)(?=(?<-2>(1+)¶)+)
$3$4¶
G3=`
1

Probieren Sie es online! (Die erste Zeile aktiviert eine durch Zeilenvorschub getrennte Testsuite.)

Ich muss später noch mehr Golf spielen.

Martin Ender
quelle

9

Haskell, 35 33 Bytes

a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)

Definiert eine Funktion a.

Anders Kaseorg
quelle

2

Schöner Trick mit dem Binden! Wäre etwas (b.b)1+(b.b)2nicht kürzer als die Summe?

XNOR

Warum ja, danke @xnor.

Anders Kaseorg

8

Julia, 29 Bytes

!n=n<3||!(n-!~-n)+!(n-!~-~-n)

Probieren Sie es online!

Wie es funktioniert

Wir definieren den unären Operator neu ! für unsere Zwecke neu.

Wenn n ist 1 oder 2 , n<3kehrt wahr und das ist unser Rückgabewert.

Wenn n größer als 2 , n<3kehrt falsch und die || Zweig wird ausgeführt. Dies ist eine einfache Implementierung der Definition, wobei ~-nAusbeuten n - 1 und ~-~-nAusbeuten n - 2 .

Dennis
quelle

7

Sesos, 54 Bytes

0000000: eefb5b 04f83a a75dc2 36f8d7 cf6dd0 af7b3b 3ef8d7  ..[..:.].6...m..{;>..
0000015: cfed12 f661f0 ae9d83 ee63e6 065df7 ce6183 af7383  ....a.....c..]..a..s.
000002a: 76ef3c 3f6383 7eff9c b9e37f                       v.<?c.~.....

Probieren Sie es online aus

Zerlegt

Oder in Brainfuck-Notation:

+>+>>>>>>,-[[->+<]>-<<++[<<<<[->>>+<<<]>>>>[-<<<+<+>>>>]<<<[->>>+<<<]>>>>++[<<<<<[<
[->>+<<]>[-<+>]<-]>>[-<+<+>>]>[<<[->+<]>>[-<<+>>]>]>>>-]<<[-<<<+>>>]>-]>>]<<<<<<<.

Anders Kaseorg
quelle

6

C 43 42 Bytes

1 Byte dank @Dennis gespeichert

Jede Antwort ist die gleiche, ich muss etwas anderes machen!

Probieren Sie es online!

a(n){return n<3?:a(n-a(n-2))+a(n---a(n));}

Erklärung: es ist im Grunde a(n-a(n-2))+a(n-a(n-1))aber mit ^{undefiniertem} Verhalten swaggy (funktioniert auf meinem Telefon (gcc) und ideone).

betseg
quelle

4

1. Sie sollten auch den Compiler erwähnen; Ihr "Beute" ist undefiniertes Verhalten. 2. Bei GCC brauchen Sie das 1zwischen ?und nicht :.

Dennis

@ Tennis Interessanterweise funktioniert die gleiche Formulierung in meiner iterativen PowerShell-Antwort ...$b+=$b[$_-$b[$_-2]]+$b[$_---$b[$_]]

AdmBorkBork

@TimmyD Einige Compiler kompilieren möglicherweise das a (n) vor dem n--, und dafür gibt es kein standardmäßiges (oder definiertes) Verhalten. Also undefiniertes Verhalten.

Betseg

@betseg Ja, ich stimme zu.

Ich

@TimmyD Oh, das habe ich falsch verstanden. Ich wollte nur die Funktion ändern, die jeder benutzt, damit meine anders und prahlerisch ist: D

betseg

5

Mathematica, 36 Bytes

Byteanzahl nimmt an ISO 8859-1 - Codierung und Mathematicas $CharacterEncodingSatz WindowsANSI(den Standard auf Windows, andere Einstellungen könnten genauso gut funktionieren, aber einige , wie UTF-8definitiv nicht).

±1=±2=1
±n_:=±(n-±(n-1))+±(n-±(n-2))

Definiert ± als unärer Operator.

Ich habe versucht, die Duplizierung zu beseitigen, habe aber die gleiche Anzahl von Bytes erhalten:

±1=±2=1
±n_:=Tr[±(n-±(n-#))&/@{1,2}]

Martin Ender
quelle

Ich kann dir ein Kopfgeld von +200 geben, wenn du es in Retina

Leaky Nun

@LeakyNun okay? :)

Martin Ender

Zwei Tage später.

Undichte Nonne

@LeakyNun Bald wirst du keine Repräsentanten mehr haben, wenn du so leicht Kopfgelder verteilst.

mbomb007

Lassen Sie uns diese Diskussion im Chat fortsetzen .

LegionMammal978

4

Jelly , 15 bis 14 Bytes

2Rạ⁸ß€$⁺Sµ1>?2

Probieren Sie es online! oder überprüfen Sie alle Testfälle (dauert einige Sekunden).

Wie es funktioniert

2Rạ⁸ß€$⁺Sµ1>?2  Main link. Argument: n (integer)

2R              Yield [1, 2].
      $         Combine the previous three links into a monadic chain.
   ⁸                Yield n.
  ạ                 Take the absolute difference of the return value and n.
    ß€              Recursively call the main link on each result.
       ⁺            Duplicate the chain.
                    The first copy maps [1, 2] to [a(n - 1), a(n - 2)].
                    The second copy maps [a(n - 1), a(n - 2)] to
                    [a(n - a(n - 1)), a(n - a(n - 2))].
        S           Take the sum.
         µ          Combine all links to the left into a chain.
            ?       If...
           > 2          n is greater than 2, call the chain.
          1         Else, return 1.

Dennis
quelle

Ich kann dir ein Kopfgeld von 400 geben, wenn du es in Sesos tust.

Undichte Nonne

@LeakyNun Es scheint eine Antwort von Sesos zu geben. Es kam einen Tag nach Ihrem Kommentar heraus.

Yytsi

4

Jelly , 14 12 11 Bytes

ịḣ2S;
1Ç⁸¡2ị

Dies ist ein iterativer Ansatz.

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

1Ç¡2ị   Main link. Argument: n

1       Set the return value to 1.
 Ç¡     Call the helper link n times, updating the return value after each call.
   2ị   Extract the second element of the resulting array.


ịḣ2S;   Helper link. Argument: A (array)

ị       At-index; retrieve the elements of A at the values of A.
 ḣ2     Head 2; extract the first two results.
    S   Take the sum of the result.
     ;  Prepend the sum to A.

Dennis
quelle

3

Python, 45 bis 40 Bytes

a=lambda n:n<3or a(n-a(n-1))+a(n-a(n-2))

Einfache naive Interpretation der Herausforderung.

5 Bytes gespart dank @LeakyNun!

Kupfer
quelle

3

Haskell, 39 37 Bytes

h n|n<3=1|n>2=h(n-h(n-1))+h(n-h(n-2))

genau wie in der Herausforderung beschrieben, mit Wachen

KarlKastor
quelle

Entschuldigung, ich habe Ihre Lösung nicht gesehen, bevor ich meine (identische) Haskell-Lösung gepostet habe. Ist die Byteanzahl 38 jedoch nicht zu berücksichtigen, da die neue Zeile berücksichtigt werden muss?

Laikoni

Und die Wache muss sein, n<3um h 2 zu sein 1.

Laikoni

. @Laikoni Es ist 37 nach Pythons len Funktion mit einem mehrzeiligen ( „“ ") string, es sei denn , Sie Newline als zwei Bytes zählen Ja, bemerkte ich die andere Sache , die es nun behoben ist.

KarlKastor

TIL notepad ++ zählt Newline als zwei Zeichen.

Laikoni

@Laikoni hat die neue Zeile entfernt, es sind jetzt unbestreitbar 37 Bytes.

Karl Kastor

3

R, 50 Bytes

a=function(n)ifelse(n<3,1,a(n-a(n-1))+a(n-a(n-2)))

Verwendung:

> a(1)
  1
> a(20)
  12

DSkoog
quelle

3

CJam, 19 18 Bytes

XXri{_($2$$+}*]-3=

Probieren Sie es online!

Verwendet den iterativen Ansatz.

Martin Ender
quelle

3

C #, 51 44 Bytes

int a(int n)=>n<3?1:a(n-a(n-1))+a(n-a(n-2));

~~Ich frage mich, ob dies verkürzt werden kann, indem man es anonym macht,~~ danke pinkfloydx33!

downrep_nation
quelle

1

c # 6 Ausdruck körperliche Funktionint a(int n)=>n<3?1:a(n-a(n-a))+a(n-a(n-2));

pinkfloydx33

Scheint, als würde ich tippen, während ich das auf meinem Handy tippe. Das Innerste -aim ersten Satz von Parens sollte sein-1

pinkfloydx33

Ich habe es auch nicht bemerkt, ich werde es reparieren rq

downrep_nation

3

JavaScript (ES6), 45 Bytes 34 Bytes

Eine rekursive Lösung in ES6. Alle Golftipps sehr geschätzt.

a=n=>n>2?a(n-a(n-1))+a(n-a(n-2)):1

Vielen Dank an / u / ismillo für die weitere Verkürzung.

BugHunterUK
quelle

2

Golfscript, 29 Bytes

~[1 1]{..0=(=\..1=(=@+\+}@*2=

Probieren Sie es online!

Undichte Nonne
quelle

2

05AB1E, 29 Bytes

Eine iterative Lösung.

XˆXˆÍL>v¯¤ys-è¯y¯yÍè-è+ˆ}¯¹<è

Probieren Sie es online aus

Emigna
quelle

2

APL, 20 Bytes

{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}

Erläuterung:

{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
 ⍵≤2:1               If argument is 2 or less, return 1
      ⋄              Otherwise:
               ⍵-⍳2  Subtract [1, 2] from the argument
             ∇¨      Recursive call on both
           ⍵-        Subtract both results from the argument     
         ∇¨          Recursive call on both again
       +/            Sum

Marinus
quelle

2

VBA Excel 87 Bytes

Nicht rekursiv, da ich möchte, dass dies für n = 100000 funktioniert, sagen Sie:

Function A(N):ReDim B(N):For i=3 To N:B(i)=B(i-B(i-1)-1)+B(i-B(i-2)-1)+1:Next:A=B(N)+1

... und drücken Sie return(Byte # 87) am Ende der Zeile, um die End FunctionAnweisung für "frei" zu erhalten. Beachten Sie, dass B-Werte um -1 versetzt sind, um eine Initialisierung für n = 1 und 2 zu vermeiden.

Rufen Sie die Tabelle wie gewohnt auf, um z. B. =A(100000)zu erhalten48157

Die rekursive Version, 61 Bytes ,

Function Y(N):If N<3 Then Y=1 Else Y=Y(N-Y(N-1))+Y(N-Y(N-2))

fängt an, für n> 30 unangemessen langsam zu werden, und man kann nicht sagen, dass es für n> 40 überhaupt funktioniert.

Joffan
quelle

Leistung ist uns egal. Wir kümmern uns um die Codelänge. Sie sollten Ihre kürzere Lösung an den Anfang Ihrer Antwort setzen.

mbomb007

1

@ mbomb007 Da ich nicht annähernd das Golf gewinnen kann, werde ich meine eigenen Entscheidungen treffen, was ein Arbeitsprogramm ausmacht. Es ist für mich nicht gut genug, auch nur Einzelbyte-Ganzzahlen zu verarbeiten, wenn es eine Lösung gibt, die dies problemlos kann.

Joffan

2

Ruby, 36 Bytes

Eine direkte Umsetzung. Anregungen zum Golfen sind willkommen.

a=->n{n<3?1:a[n-a[n-1]]+a[n-a[n-2]]}

Sherlock9
quelle

Afaik, du kannst das a = loswerden. Wenn Sie es hier posten, reicht es aus, wenn Ihr Code mit -> beginnt. Es gilt dann als anonyme Funktion.

Seims

@Seims Leider muss die Funktion benannt werden, da die Funktion sich selbst mit a[n-1]und so aufruft .

Sherlock9

2

Java 7, 68 61 51 Bytes

17 dank Leaky Nun gerettet.

int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}

Justin
quelle

Willkommen bei PPCG!

AdmBorkBork

Willkommen bei PPCG! Vielleicht gefallen Ihnen Tipps zum Golfen in Java . Eine alternative Form wäre:, int a(int n){return n<3?1:a(n-a(n-2))+a(n---a(n));}aber leider verwendet es die gleiche Anzahl von Bytes wie die Antwort, die Sie bereits haben. Außerdem würde ich angeben, dass Ihre Antwort in Java 7 ist, da die Java 8-Antwort kürzer wäre: n->return n<3?1:a(n-a(n-1))+a(n-a(n-2))( 39 Bytes ) .

Kevin Cruijssen

Vielen Dank für die Begrüßung, und vielen Dank für den Tipp zu Java8 - ich wusste nicht, dass Lambdas so erlaubt sind - obwohl sie in Python so erlaubt sind, also habe ich wohl nie darüber nachgedacht. Braucht der Lambda ein Semikolon?

Justin

@JustinTervay Ich benutze Java 8 nicht oft, aber nach dem, was ich gehört habe, wird das Semikolon nicht für einzeilige Ausdrücke gezählt, so ein Kommentar von Semikolon @DavidConrad und @ CAD97 in einer meiner eigenen Java-Antworten .

Kevin Cruijssen

2

Oasis , 9 7 5 Bytes (nicht konkurrierend)

Nicht konkurrierend , da die Sprache die Herausforderung datiert. Vielen Dank an Kenny Lau für das Speichern von 4 Bytes. Code:

ece+V

Erweiterte Form ( VKurzform 11):

a(n) = ece+
a(0) = 1
a(1) = 1

Code:

e        # Stack is empty, so a(n - 1) is used, and it calculates a(n - a(n - 1))
 c       # Calculate a(n - 2)
  e      # Calculate a(n - a(n - 2))
   +     # Add up

Probieren Sie es online! . Berechnet n = 1000 in 0,1 Sekunden.

Adnan
quelle

1

PowerShell v2 +, 85 79 69 Byte

param($n)$b=1,1;2..$n|%{$b+=$b[$_-$b[$_-1]]+$b[$_-$b[$_-2]]};$b[$n-1]

Übernimmt die Eingabe $n, setzt $bsie als Array von @(1, 1)und tritt dann in eine Schleife von ein 2 .. $n. Bei jeder Iteration wird $bdie letzte Berechnung in der Sequenz mit einer einfachen +=und der Definition der Sequenz angeheftet. Wir geben dann die entsprechende Nummer aus$b (mit einem, -1weil Arrays in PowerShell mit Nullen indiziert sind). Dies funktioniert , wenn $nsich 1oder 2weil diese beiden Werte in die unteren Indizes der vorausgefüllt $bvon Anfang an , so dass selbst wenn die Schleife Angriffe auf Junk, ist es sowieso ignoriert.

Rekursive Lösung 78 76 Bytes

$a={param($k)if($k-lt3){1}else{(&$a($k-(&$a($k-1))))+(&$a($k-(&$a($k-2))))}}

Zum ersten Mal habe ich das Äquivalent eines Lambda als Antwort verwendet, da normalerweise eine iterative Lösung kürzer ist (wie Sie aus allen verschachtelten Parens ersehen können). ~~In diesem Fall werden die verschachtelten Parens jedoch in der iterativen Lösung mit den verschachtelten Arrayaufrufen fast dupliziert, sodass die rekursive Lösung kürzer ist.~~ Nein, die iterative Lösung ist in der Tat kürzer (siehe oben).

Rufen Sie es über den Execution-Operator auf, wie &$a 20. Nur ein rekursiver Direktaufruf.

AdmBorkBork
quelle

1

JavaScript (ES6), 66 Byte

n=>[...Array(n+1)].reduce((p,_,i,a)=>a[i]=i<3||a[i-p]+a[i-a[i-2]])

Nicht rekursive Version für Geschwindigkeit; Die rekursive Version ist wahrscheinlich kürzer, aber ich überlasse es jemand anderem, sie zu schreiben. Ich mag es immer, wenn ich es benutze reduce. Anmerkung: 1 Byte gespeichert durch Rücksendung true(die wirft , 1wenn sie in einem ganzzahligen Zusammenhang verwendet) für von a(1)und a(2).

Neil
quelle

1

Pyth, 16 Bytes

L|<b3smy-bytdtBb

L                  def y(b):
 |<b3                b < 3 or …
      m      tBb       map for d in [b - 1, b]:
       y-bytd            y(b - y(d - 1))
     s                 sum

Definiert eine Funktion y.

Probieren Sie es online aus (hinzugefügt yMS20, um die ersten 20 Werte zu drucken)

Anders Kaseorg
quelle

1

Viertens 76 Bytes

Ich habe es endlich geschafft!

: Q recursive dup dup 3 < if - 1+ else 2dup 2 - Q - Q -rot 1- Q - Q + then ;

Probieren Sie es online aus

Erläuterung:

: Q recursive                           \ Define a recursive function Q
    dup dup 3 <                         \ I moved a dup here to golf 2 bytes
    if                                  \ If n < 3, return 1
        - 1                             \ Golf: n-n is zero, add one. Same as 2drop 1+
    else
        2dup 2 - Q - Q                  \ Copy n until 4 on stack, find Q(n-Q(n-2))
        -rot                            \ Move the result below 2 copies of n
        1- Q - Q +                      \ Find Q(n-Q(n-2)), then add to previous ^
    then ;

Probieren Sie es online aus (von oben etwas ungegolft)

Leider ist die gegenseitige Rekursion etwas zu wortreich , um sie zum Golfen zu verwenden.

mbomb007
quelle

1

Ahorn, 43 41 Bytes

a:=n->`if`(n>2,a(n-a(n-1))+a(n-a(n-2)),1)

Verwendung:

> a(1);
  1
> a(20);
  12

Dieses Problem ist sicherlich ein guter Kandidat für das Auswendiglernen. Durch die Verwendung des Optionscaches werden die Laufzeiten erheblich verkürzt:

aC := proc(n) 
      option cache; 
      ifelse( n > 2, aC( n - aC(n-1) ) + aC( n - aC(n-2) ), 1 ); 
end proc:

Dies ist zu sehen mit:

CodeTools:-Usage( aC(50) );

DSkoog
quelle

0

J 29 28 Bytes

1:`(+&$:/@:-$:@-&1 2)@.(2&<)

Verwendet die rekursive Definition.

Verwendung

Zusätzliche Befehle werden zum Formatieren mehrerer Ein- / Ausgaben verwendet.

   f =: 1:`(+&$:/@:-$:@-&1 2)@.(2&<)
   (,:f"0) >: i. 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 3 3 4 5 5 6  6  6  8  8  8 10  9 10 11 11 12

Erläuterung

1:`(+&$:/@:-$:@-&1 2)@.(2&<)  Input: n
                        2&<   If n < 2
1:                              Return 1
                              Else
               -&1 2            Subtract [1, 2] from n to get [n-1, n-2]
            $:@                 Call recursively on n-1 and n-2
           -                    Subtract each of the results from n
        /@:                     Reduce using
      $:                          A recursive call on each
    +&                            Then summation
                                Return that value as the result

Meilen
quelle

0

Gleichstrom, 62 Bytes

?si2sa1dd2:a:a[la1+dsadd1-;a-;alad2-;a-;a+r:ali;a0=A]dsAxli;af

Diese Lösung nutzt Arrays und Rekursion.

?si          # Take input from stdin and store it in register `i'
2sa          # Initialise register `a' with 2, since we'll be putting in the first
             #   two values in the sequence
1dd2         # Stack contents, top-down: 2 1 1 1
:a           # Pop index, then pop value: Store 1 in a[2]
:a           # Ditto:                     Store 1 in a[1]
[            # Open macro definition
 la 1+ dsa   # Simple counter mechanism: Increment a and keep a copy on stack

# The STACK-TRACKER(tm): Top of stack will be at top of each column, under the
#   dashed line. Read commands from left to right, wrapping around to next line.
#   This will be iteration number n.
  dd   1-    ;a       -          ;a            la            d          
#-----------------------------------------------------------------------
# n    n-1   a[n-1]   n-a[n-1]   a[n-a[n-1]]   n             n          
# n    n     n        n          n             a[n-a[n-1]]   n          
# n    n     n                                 n             a[n-a[n-1]]
#                                                            n          
#                                                                       

  2-            ;a            -             ;a            +      r    :a
#-----------------------------------------------------------------------
# n-2           a[n-2]        n-a[n-2]      a[n-a[n-2]]   a[n]   n      
# n             n             a[n-a[n-1]]   a[n-a[n-1]]   n      a[n]   
# a[n-a[n-1]]   a[n-a[n-1]]   n             n                           
# n             n                                                       

 li;a        # Load index of target element, and fetch that element's current value
             #    Uninitialised values are zero
 0=A         # If a[i]==0, execute A to compute next term
]dsAx        # Close macro definition, store on `A' and execute
li;a         # When we've got enough terms, load target index and push value
f            # Dump stack (a[i]) to stdout

Joe
quelle

dcLassen Sie es mich abschließend wissen , wenn jemand eine IDE für erstellt !

Joe

0

Erlang, 46 Bytes

f(N)when N<3->1;f(N)->f(N-f(N-1))+f(N-f(N-2)).

cPu1
quelle

0

Lua, 59 Bytes

function a(n)return n<3 and 1 or a(n-a(n-1))+a(n-a(n-2))end

brianush1
quelle

Hofstadter Q-Sequenz

Definition

Aufgabe

Testfälle

Referenz

Antworten:

Retina , 84 83 79 74 Bytes

Haskell, 35 33 Bytes

Julia, 29 Bytes

Wie es funktioniert

Sesos, 54 Bytes

Zerlegt

C 43 42 Bytes

Mathematica, 36 Bytes

Jelly , 15 bis 14 Bytes

Wie es funktioniert

Jelly , 14 12 11 Bytes

Wie es funktioniert

Python, 45 bis 40 Bytes

Haskell, 39 37 Bytes

R, 50 Bytes

CJam, 19 18 Bytes

C #, 51 44 Bytes

JavaScript (ES6), 45 Bytes 34 Bytes

Golfscript, 29 Bytes

05AB1E, 29 Bytes

APL, 20 Bytes

VBA Excel 87 Bytes

Ruby, 36 Bytes

Java 7, 68 61 51 Bytes

Oasis , 9 7 5 Bytes (nicht konkurrierend)

PowerShell v2 +, 85 79 69 Byte

Rekursive Lösung 78 76 Bytes

JavaScript (ES6), 66 Byte

Pyth, 16 Bytes

Viertens 76 Bytes

Ahorn, 43 41 Bytes

J 29 28 Bytes

Verwendung

Erläuterung

Gleichstrom, 62 Bytes

Erlang, 46 Bytes

Lua, 59 Bytes