Anzahl der geradkettigen Alkane der angegebenen Länge

28

Ein geradkettiges Alk * ne ist definiert als eine Folge von Kohlenstoffatomen, die durch Einfach- (Alkan), Doppel- (Alken) oder Dreifachbindungen (Alkin) verbunden sind (implizite Wasserstoffatome werden verwendet). Kohlenstoffatome können also nur 4 Bindungen bilden Kein Kohlenstoffatom darf gezwungen werden, mehr als vier Bindungen zu haben. Ein geradkettiges Alkohol kann als Liste seiner Kohlenstoff-Kohlenstoff-Bindungen dargestellt werden.

Dies sind einige Beispiele für gültige geradkettige Alkene:

[]       CH4              Methane
[1]      CH3-CH3          Ethane
[2]      CH2=CH2          Ethene
[3]      CH≡CH            Ethyne
[1,1]    CH3-CH2-CH3      Propane
[1,2]    CH3-CH=CH2       Propene
[1,3]    CH3-C≡CH         Propyne
[2,1]    CH2=CH-CH3       Propene
[2,2]    CH2=C=CH2        Allene (Propadiene)
[3,1]    CH≡C-CH3         Propyne 
[1,1,1]  CH3-CH2-CH2-CH3  Butane
...

Dies ist jedoch nicht der Fall, da mindestens ein Kohlenstoffatom mehr als 4 Bindungen aufweisen würde:

[2,3]
[3,2]
[3,3]
...

Ihre Aufgabe ist es, ein Programm / eine Funktion zu erstellen, das / die bei einer positiven ganzen Zahln die Anzahl der gültigen geradkettigen Alkene mit genau der nLänge der Kohlenstoffatome ausgibt / zurückgibt . Dies ist OEIS A077998 .

Spezifikationen / Erläuterungen

  • Sie müssen 1bei der Rücksendung korrekt vorgehen 1.
  • Alkene mögen [1,2]und [2,1]gelten als verschieden.
  • Die Ausgabe ist die Länge einer Liste aller möglichen Alkane einer bestimmten Länge.
  • Sie nicht haben 0 richtig zu handhaben .

Testfälle:

1 => 1
2 => 3
3 => 6
4 => 14

Dies ist Codegolf, also gewinnt die niedrigste Bytezahl !

Zacharý
quelle
Nur um zu verdeutlichen, eine Kette ist gültig, wenn alle aufeinander folgenden Paare zu summiert werden <=4, oder?
Maltysen
Fest. @Maltysen: ja.
Zacharý
4
Warum gibt es eine OEIS-Sequenz für alles? : P
HyperNeutrino
2
@ZacharyT, es gibt genau einen Kohlenwasserstoff mit null Kohlenstoffatomen, und dieser enthält auch null Wasserstoffatome. Es ist genau das gleiche Argument wie für Pascals Dreieck mit einer 1 oben und nicht mit einer 0 oder für buchstäblich Hunderte anderer kombinatorischer Sequenzen.
Peter Taylor
1
@Emigna, das liegt daran, dass die falsche Reihenfolge verknüpft wurde. Ich werde es korrigieren.
Peter Taylor

Antworten:

7

Oasis , 9 7 Bytes

xcd-+3V

Probieren Sie es online!

Erläuterung

Dies verwendet die Wiederholungsbeziehung in OEIS :

a (n) = 2 * a (n-1) + a (n-2) - a (n-3)

x    Multiply a(n-1) by 2: gives 2*a(n-1)
c    Push a(n-2)
d    Push a(n-3)
-    Subtract: gives a(n-2) - a(n-3)
+    Add: gives 2*a(n-1) + a(n-2) - a(n-3)
3    Push 3: initial value for a(n-1)
V    Push 1, 1: initial values for a(n-2), a(n-3)
Luis Mendo
quelle
1
Gute Verwendung von Anfangswerten! Sie gewinnen dieses Mal;)
Emigna
Ja, es gibt wahrscheinlich keine Möglichkeit, dies zu übertreffen.
Zacharý
4
@ ZacharyT Nur wenn jemand einen Weg finden kann, das Programm darin zu haben xkcd.
hBy2Py
4
@ hBy2Py Nun, xkcd-+311funktioniert , weil kist derzeit ein No-Op ...
Luis Mendo
10

MATL , 10 Bytes

7K5vBiY^1)

Probieren Sie es online!

Erläuterung

Dies verwendet die in OEIS gefundene Charakterisierung

a (n) ist der linke obere Eintrag der n-ten Potenz der 3 × 3-Matrix [1, 1, 1; 100; 1, 0, 1]

7    % Push 7
K    % Push 4
5    % Push 5
v    % Concatenate all numbers into a column vector: [7; 4; 5]
B    % Convert to binary: gives 3×3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 1]
i    % Input n
Y^   % Matrix power
1)   % Take the first element of the resulting matrix, i.e. its upper-left corner.
     % Implicitly display
Luis Mendo
quelle
6

Oasis , 9 8 Bytes

Ein Byte dank Adnan gespeichert

xc+d-63T

Probieren Sie es online!

Erläuterung

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 6

a(n) = xc+d-

x         # calculate 2*a(n-1)
 c        # calculate a(n-2)
  +       # add: 2*a(n-1) + a(n-2)
   d      # calculate a(n-3)
    -     # subtract: 2*a(n-1) + a(n-2) - a(n-3)
Emigna
quelle
1
Nett! Auch xist kurz für 2*:).
Adnan
1
Beat ya :-P (Ich hatte nicht gesehen, dass es bereits eine OASIS-Antwort gab)
Luis Mendo
@Adnan Gibt es eine Möglichkeit, Oasis mitzuteilen, dass Sie den Ausgangssequenzindex um 1 verschieben möchten? Ich meine, subtrahiere 1 zum Eingabeargument (anstatt 0hier eine Initiale zu verwenden )
Luis Mendo
1
@ LuisMendo Ah, das ist noch nicht implementiert. Aber es ist eine gute Idee für die nächste Veröffentlichung :).
Adnan
Zum späteren Nachschlagen ist dies jetzt implementiert
Luis Mendo
4

Gelee, 10 Bytes

745DBæ*µḢḢ

Probieren Sie es online!

Verwendet den Algorithmus von Luis Mendo .

Erläuterung

745DBæ*µḢḢ    Main link. Argument: n
745D          Get the digits of 745
    B         Convert each to binary
     æ*       Matrix power
        ḢḢ    First element of first row

Gelee, 15 Bytes

3Rṗ’µ+2\<5PµÐfL

Probieren Sie es online!

Verwendet rohe Gewalt.

Erläuterung

3Rṗ’µ+2\<5PµÐfL    Main link. Argument: n
3R                 Start with [1, 2, 3]
   ’               Take the (n-1)'th
  ṗ                Cartesian power
            Ðf     Filter on:
     +2\             Sums of overlapping pairs
        <5           1 for sums < 5, 0 otherwise
          P          Product: 1 if all pairs < 5
              L    Length
PurkkaKoodari
quelle
4

MATL , 14 Bytes

q3:Z^TTZ+!5<As

Probieren Sie es online!

Erläuterung

Dies erzeugt die kartesische Potenz des [1 2 3]"Erhöhens" auf die Anzahl der Atome minus 1 und verwendet dann die Faltung, um zu überprüfen, ob keine zwei zusammenhängenden Zahlen in jedem kartesischen Tupel mehr als summieren 4.

q    % Take number of atoms n implicitly
3:   % Push [1 2 3]
Z^   % Cartesian power. Gives a matrix with each (n-1)-tuple on a row
TT   % Push [1 1]
Z+   % 2D convolution. For each tuple this gives the sum of contiguous numbers
5<   % For each entry, gives true if less than 5
!    % Transpose
A    % True if all elements of each column are true. Gives a row vector
s    % Sum of true results. Implicitly display
Luis Mendo
quelle
3

Mathematica, 48 Bytes

MatrixPower[{{1,1,1},{1,0,0},{1,0,1}},#][[1,1]]&

Wie Luis Mendo betonte, ist dies A006356 im OEIS. Hier sind meine ursprünglichen Versuche:

Count[Length@Split[#,+##<5&]&/@Tuples[{1,2,3},#-1],0|1]&

Für eine Eingabe n, Tuples[{1,2,3},n-1]die Liste aller (n-1)Tupel von Elementen , {1,2,3}die alle möglichen Sequenzen von Einzel-, Doppel- oder Dreifachbindungen zu nC - Atomen. +##<5&ist eine reine Funktion, die zurückgibt, ob die Summe ihrer Argumente kleiner als ist 5, also Split[#,+##<5&]&eine Liste in Unterlisten aufteilt, die aus aufeinanderfolgenden Elementen bestehen, deren paarweise Summen kleiner als sind 5. Das Beschreiben eines gültigen Alk * ns entspricht der Länge dieser Liste 0(in dem Fall, in dem n=1) oder 1, also nur Countder Anzahl der (n-1)Tupel, in denen die Länge dieser Liste übereinstimmt 0|1.

Count[Fold[If[+##>4,4,#2]&]/@Tuples[{1,2,3},#-1],Except@4]&

If[+##>4,4,#2]&Gibt zurück, 4wenn die Summe der Argumente größer als ist, 4andernfalls wird das zweite Argument zurückgegeben. Macht mit dieser Funktion Fold[If[+##>4,4,#2]&]einen Link Foldvon seiner Eingabe. Hier gebe ich also Countdie Anzahl der (n-1)-tupel an, auf die das Anwenden dieses Operators nicht zutrifft 4. Der Fall, in dem n=1seit behandelt wird, Foldbleibt unbewertet, wenn das zweite Argument die leere Liste ist {}.

Genisis
quelle
1
Würde das funktionieren? (Art von direkt aus OEIS mit Anpassungen gerippt) LinearRecurrence[{2,1,-1},{1,3,6},#][[#]]&?
Zacharý
Ein Grund, warum ich diese Seite liebe, ist das Erlernen aller Funktionen, die Mathematica zu bieten hat :)
ngenisis
Mit dem this site, meinst du OEIS oder PPCG?
Zacharý
PPCG. Ich habe eine Menge Mathematica von den Vorschlägen der Leute aufgegriffen.
Genisis
3

Python, 51 Bytes

f=lambda n:n<4and(n*n+n)/2or 2*f(n-1)+f(n-2)-f(n-3)

Dies ist eine einfache Implementierung der Wiederholungsbeziehung. Danke an Tim Pederick für 3 Bytes. Die Ausgabe ist ein Float in Python 3 und eine Ganzzahl in Python 2.

Probieren Sie es online!

Mego
quelle
(n*n+n)/2ist kürzer als [1,3,6][n-1]. Und wenn Sie Python 3 verwenden und keine Gleitkomma-Ausgabe erhalten möchten, (n*n+n)//2ist dies immer noch kürzer.
Tim Pederick
2

Pyth - 16 Bytes

Verwendet rohe Gewalt.

lf.AgL4+VTtT^S3t

Test Suite .

Maltysen
quelle
1
Es wäre schön, eine Beschreibung für diejenigen von uns zu liefern, die Pyth nicht "groken".
Zacharý
2

Ruby, 62 Bytes

->n{c=0
(10**n/10).times{|i|"#{i}#{i*11}"=~/[3-9]/||c+=1}
c}

Schrecklich ineffizienter Base-10-Brute-Force-Ansatz. Könnte für zusätzliche Bytes auf Basis 5 verbessert werden.

Es werden Zahlen generiert, bei denen jede Ziffer eine Bindung darstellt (n-1 Ziffern). 0 Dies entspricht einer Bindungsreihenfolge von 1 und 2einer Bindungsreihenfolge von 3. Ziffern über 2 sind ungültig.

Wir multiplizieren dies mit 11, um benachbarte Ziffernpaare zu summieren. Wiederum sind Ziffern über 3 ungültig.

Wir kombinieren die beiden Zahlen in einer Zeichenkette und führen einen regulären Ausdruck durch, um nach ungültigen Ziffern zu suchen. Wenn keine gefunden werden, erhöhen wir den Zähler.

im Testprogramm

f=->n{c=0
(10**n/10).times{|i|"#{i}#{i*11}"=~/[3-9]/||c+=1}
c}

p f[gets.to_i]
Level River St
quelle
2

Ruby, 51 Bytes

->n{a=[1,1,3]
n.times{a<<2*a[-1]+a[-2]-a[-3]}
a[n]}

Basierend auf der Wiederholungsrelation gemäß OEIS A006356.

Beginnt mit einem Array für die Elemente 0,1 und 2 der Sequenz, die 1 (wie von mir berechnet, damit es funktioniert) bzw. 1 und 3 sind.

Fügt nder Sequenz iterativ weitere Elemente hinzu und gibt dann das Element zurück n. Es berechnet immer 2 Elemente mehr, als es tatsächlich benötigt, aber es ist immer noch eine lineare Zeit, die viel effizienter ist als meine vorherige Antwort.

im Testprogramm

f=->n{a=[1,1,3]
n.times{a<<2*a[-1]+a[-2]-a[-3]}
a[n]}

p f[gets.to_i]
Level River St
quelle
2

Mathematica, 42-40 Bytes

Die Byteanzahl setzt eine kompatible Einzelbyte-Codierung wie CP-1252 voraus (die Standardeinstellung bei Windows-Installationen).

±0=±1=1;±2=3;±n_:=±(n-1)2+±(n-2)-±(n-3);

Dies implementiert einfach die Wiederholung, die in OEIS als unärer Operator angegeben ist.

Martin Ender
quelle
2

CJam (19 Bytes)

{2,{__-2=+1b+}@*W=}

Online-Testsuite . Dies ist ein anonymer Block (eine Funktion), der einen Gegenstand auf dem Stapel nimmt und einen auf dem Stapel belässt. Beachten Sie, dass die Testsuite enthält a(0) = 1.

Die verwendete Wiederholung basiert auf der Beobachtung für die verwandte OEIS-Sequenz A006356 :

Entspricht der INVERT-Transformation von (1, 2, 1, 1, 1, ...) entsprechend a (n) = a (n-1) + 2 * a (n-2) + a (n-3) + a (n - 4) + ... + 1. a (6) = 70 = (31 + 2 · 14 + 6 + 3 + 1 + 1). - Gary W. Adamson, 27. April 2009

aber mit dem entsprechenden Versatz, der die Notwendigkeit für das Finale beseitigt, + 1wie es jetzt durch gedeckt ist a(0).

Präparation

{         e# Define a block
  2,      e#   Take starting sequence [0 1] (beginning at index -1 for golfiness)
  {       e#   Loop...
    _     e#     Copy sequence so far
    _-2=+ e#     Append an extra copy of a(n-2)
    1b    e#     Sum
    +     e#     Append
  }@*     e#   ...n times
  W=      e#   Take the final value from the sequence
}
Peter Taylor
quelle
2

Brain-Flak, 56 Bytes

Verwendet den im ersten Kommentar auf der OEIS-Seite beschriebenen Algorithmus.

Probieren Sie es online!

({}[()]<(((())))>){({}[()]<{({}<>({}))<>}<>>)}{}({}<>{})

Erläuterung

Die Reihenfolge kann wie folgt definiert werden:

For u(k), v(k), and w(k) such that
u(1) = v(1) = w(1) = 1
u(k+1) = u(k) + v(k) + w(k)
v(k+1) = u(k) + v(k)
w(k+1) = u(k)
u(k) is the number of straight-chain alk*nes with length k

Das Programm startet um 1und wendet diese Wiederholung wiederholt zur Berechnung anu(k)

Annotated Code (aktuelle Annotation in Kürze)

# Setup: decrement the input by one and push three 1's to the stack under it
({}[()]<(((())))>)

# Calculation:
{                          }           # While the input is not zero (main loop)
 ({}[()]                  )            # Pop the counter decrement it by one and push it
        <                >             # Before the counter gets pushed back to the stack...
         {            }                # Loop while the top of the stack is not zero (subloop)
          (        )                   # Push...
           {}                          # The top of the stack (popped)...
             <>                        # to the other stack...
               ({})                    # plus the top of the other stack (peeked)
                    <>                 # Switch back to the first stack.
                       <>              # Switch to the other stack
                            {}         # Pop the input (now zero)
                              (      ) # Push...
                               {}      # The top of the stack (u(k))...
                                 <>    # to the other stack...
                                   {}  # plus the top of the other stack (zero).

Visualisierung der Stapel

In einer Iteration der Hauptschleife geschieht Folgendes (beachten Sie, dass die Nullen vorhanden sein können oder nicht, aber es spielt keine Rolle, wie auch immer):

Start of main loop iteration/subloop first iteration:
A    B

u
v
w
0    0
^

After first subloop iteration:
A    B

v
w    u
0    0
^

After second subloop iteration:
A    B

    u+v
w    u
0    0
^

After third subloop iteration (top of stack is zero so subloop terminates):

A    B

   u+v+w
    u+v
     u
0    0
^

End of main loop iteration:
A    B

   u+v+w
    u+v
     u
0    0
     ^

Der Zustand des Stapels ist jetzt das gleiche , wie es am Anfang der Schleife wurde mit der Ausnahme , dass der aktuelle Stapel hat nun die nächsten Werte für u, vund wdarauf.

0 '
quelle
2

Perl 6, 48

{my @a=1,0,0;@a=reverse [\+] @a for 1..$_;@a[0]}

Ursprünglich

sub f {$_>2??2*f($_-1)+f($_-2)-f($_-3)!!(1,1,3)[$_]}

aber ich habe vergessen, dass ich das brauchte, sub fdamit die iterative Lösung siegt.

bb94
quelle
2

Dyalog APL, 30 Bytes

{⍵<3:⍵⌷1 3⋄+/∧/¨4≥2+/¨,⍳1↓⍵/3}

Verwendet rohe Gewalt. Erklärung (zumindest mein bester Versuch):

⍵<3:⍵⌷1 3 - if ⍵ (function arg) is 1 (case 1) or 2 (case 2), return 1 (case 1) or 3 (case 2)
⋄ - separate statements
⍵/3 - otherwise, 3 repeated ⍵ times
1↓ - without the first element
⍳ - the matrix of possible indices of a matrix of that size
,  - ravel, return a list of all the elements of the matrix
2+/¨ - sum of each contiguous pair on each element
4≥ - tests whether each element is less than or equal to 4
∧/¨ - all elements are true, applied to each item.
+/ - Sum.
Zacharý
quelle
1

Dyalog APL, 29 Bytes

{⍵<4:⍵⌷1 3 6⋄+/2 1 ¯1×∇¨⍵-⍳3}

Funktioniert unter Verwendung der rekursiven Definition der Ganzzahlsequenz OEIS A006356.

Zacharý
quelle
1

Python mit Numpy, 62 Bytes

Ich musste es versuchen, aber es scheint, als sei Python pur und die Rekursion kürzer als Numpy und die explizite, matrixbasierte Berechnung auf der OEIS-Seite.

from numpy import*
lambda n:(mat('1 1 1;1 0 0;1 0 1')**n)[0,0]
Tim Pederick
quelle
1

R 61 58 55 51 50 Bytes

Übernimmt die Eingabe von stdin und verwendet die Matrixexponentiation, um das genaue Ergebnis zu bestimmen.

el(expm::`%^%`(matrix(!-3:5%in%2^(0:2),3),scan()))

Wenn Sie eine rekursive Lösung bevorzugen, finden Sie hier eine einfache Implementierung der in OEIS aufgelisteten Wiederholungsrelation für 55 Byte .

f=function(n)`if`(n<4,(n*n+n)/2,2*f(n-1)+f(n-2)-f(n-3))
rturnbull
quelle
1

Excel, 123 Bytes

Implementiert die Formel von OEIS:

=4*(SIN(4*PI()/7)^2*(1+2*COS(2*PI()/7))^A1+SIN(8*PI()/7)^2*(1+2*COS(4*PI()/7))^A1+SIN(2*PI()/7)^2*(1+2*COS(8*PI()/7))^A1)/7

Geben Sie wie immer A1in eine beliebige andere Zelle eine Formel ein.

Habe alte Trig-Identitäten ausgegraben, um zu sehen, ob sie hilfreich sein könnten. Jetzt tut mir der Kopf weh.

Wernisch
quelle
0

Lithp , 79 Bytes

#N:(((if(< N 4)((/(+ N(* N N))2))((-(+(* 2(f(- N 1)))(f(- N 2)))(f(- N 3)))))))

Implementiert die in OEIS aufgelistete rekursive Ganzzahlsequenz.

Lesbare Implementierung und Testsuite.

% alkaline.lithp
% run with: ./run.js alkaline.lithp
(
    (def f #N : ((
        (if (< N 4) (
            (/ (+ N (* N N)) 2)
        ) (else (
            (- (+ (* 2 (f (- N 1))) (f (- N 2))) (f (- N 3)))
        )))
    )))

    % Test cases 1 to 4
    (import lists)
    (each (seq 1 4) #I :: ((print (f I))))
)
Andrakis
quelle