Prostołańcuchowy alk * ne jest zdefiniowany jako sekwencja atomów węgla połączonych wiązaniami pojedynczymi (alkan), podwójnymi (alken) lub potrójnymi (alkin), (stosowane są ukryte atomy wodoru). Atomy węgla mogą tworzyć tylko 4 wiązania, więc żaden atom węgla nie może być zmuszony do posiadania więcej niż czterech wiązań. Prostołańcuchowy alk * ne może być reprezentowany jako lista jego wiązań węgiel-węgiel.
Oto kilka przykładów prawidłowych alk * nów o łańcuchach prostych:
[] 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
...
Chociaż tak nie jest, ponieważ co najmniej jeden atom węgla miałby więcej niż 4 wiązania:
[2,3]
[3,2]
[3,3]
...
Twoim zadaniem jest stworzenie programu / funkcji, która przy dodatniej liczbie całkowitej n
wyprowadza / zwraca liczbę prawidłowych alkinów o łańcuchach prostych o długości dokładnie n
atomów węgla. To jest OEIS A077998 .
Dane techniczne / Wyjaśnienia
- Musisz
1
poprawnie postępować , zwracając1
. - Alk * nes lubią
[1,2]
i[2,1]
są uważane za odrębne. - Dane wyjściowe to długość listy wszystkich możliwych alk * nów o danej długości.
- Zdajesz nie muszą obsługiwać 0 poprawnie.
Przypadki testowe:
1 => 1
2 => 3
3 => 6
4 => 14
To jest golf golfowy, więc wygrywa najmniej bajtów !
źródło
<=4
, prawda?Odpowiedzi:
Oaza ,
97 bajtówWypróbuj online!
Wyjaśnienie
Wykorzystuje to relację powtarzalności w OEIS :
źródło
xkcd
w tym udział.xkcd-+311
działa , ponieważk
obecnie nie można tego zrobić ...MATL , 10 bajtów
Wypróbuj online!
Wyjaśnienie
Wykorzystuje to charakterystykę znalezioną w OEIS
źródło
Oaza ,
98 bajtówOszczędność bajtu dzięki Adnanowi
Wypróbuj online!
Wyjaśnienie
źródło
x
jest skrótem od2*
:).0
tu inicjału )Galaretka, 10 bajtów
Wypróbuj online!
Wykorzystuje algorytm Luisa Mendo .
Wyjaśnienie
Galaretka, 15 bajtów
Wypróbuj online!
Używa brutalnej siły.
Wyjaśnienie
źródło
MATL , 14 bajtów
Wypróbuj online!
Wyjaśnienie
Generuje to kartezjańską moc
[1 2 3]
„podniesionej” do liczby atomów minus 1, a następnie używa splotu, aby sprawdzić, czy nie ma więcej niż dwóch sąsiadujących liczb w każdej krotce kartezjańskiej więcej niż4
.źródło
Mathematica, 48 bajtów
Jak zauważył Luis Mendo , jest to A006356 w OEIS. Oto moje oryginalne próby:
Na wejściu
n
,Tuples[{1,2,3},n-1]
to wykaz wszystkich(n-1)
-tuples elementów w{1,2,3}
reprezentujące wszystkie możliwe sekwencje pojedyncze, podwójne lub potrójne wiązania don
atomów węgla.+##<5&
jest funkcją czystą, która zwraca, czy suma jej argumentów jest mniejsza niż5
, więcSplit[#,+##<5&]&
dzieli listę na podlisty składające się z kolejnych elementów, których sumy par są mniejsze niż5
. Opisanie prawidłowej alk * ne jest równoważne długości tej listy0
(w przypadku, gdyn=1
)1
, a więc po prostuCount
liczbie(n-1)
-tuli, w których długość tej listy jest zgodna0|1
.If[+##>4,4,#2]&
zwraca,4
jeśli suma jego argumentów jest większa niż,4
i zwraca drugi argument w przeciwnym razie.Fold[If[+##>4,4,#2]&]
wykonuje leweFold
wejście od tej funkcji. Więc tutaj ICount
-liczba,(n-1)
której nie stosuje ten operator4
. Przypadek, w którymn=1
jest to uwzględnione,Fold
pozostaje nieoceniony, gdy jego drugim argumentem jest pusta lista{}
.źródło
LinearRecurrence[{2,1,-1},{1,3,6},#][[#]]&
?this site
, to znaczy OEIS lub PPCG?Python, 51 bajtów
Jest to prosta implementacja relacji powtarzalności. Dzięki Tim Pederick za 3 bajty. Dane wyjściowe to liczba zmiennoprzecinkowa w Pythonie 3 i liczba całkowita w Pythonie 2.
Wypróbuj online!
źródło
(n*n+n)/2
jest krótszy niż[1,3,6][n-1]
. A jeśli używasz Pythona 3 i nie lubisz kończyć się liczbami zmiennoprzecinkowymi,(n*n+n)//2
jest jeszcze krótszy.Pyth - 16 bajtów
Używa brutalnej siły.
Pakiet testowy .
źródło
Rubin, 62 bajty
Okropnie nieefektywne podejście 10 brutalnej siły. Można ulepszyć do podstawy 5 dla dodatkowych bajtów.
Liczby są generowane, gdy każda cyfra reprezentuje wiązanie (n-1 cyfr.)
0
Reprezentuje rząd wiązania 1,2
reprezentuje rząd wiązania 3. Cyfry powyżej 2 są nieprawidłowe.Mnożymy to przez 11, aby zsumować sąsiednią parę cyfr. Znów cyfry powyżej 3 są nieprawidłowe.
Łączymy dwie liczby w ciągu i wykonujemy wyrażenie regularne, aby wyszukać nieprawidłowe cyfry. Jeśli nie zostaną znalezione, zwiększamy licznik.
w programie testowym
źródło
Rubinowy, 51 bajtów
Na podstawie relacji powtarzalności według OEIS A006356.
Zaczyna się od tablicy dla elementów 0,1 i 2 sekwencji, które są 1 (obliczone przeze mnie, aby działało), odpowiednio 1 i 3.
Iteracyjnie dodaje
n
więcej elementów do sekwencji, a następnie zwraca elementn
. Zawsze oblicza 2 elementy więcej, niż faktycznie potrzebuje, ale wciąż jest to czas liniowy, który jest znacznie wydajniejszy niż moja poprzednia odpowiedź.w programie testowym
źródło
Mathematica,
4240 bajtówLiczba bajtów zakłada kompatybilne kodowanie jednobajtowe, takie jak CP-1252 (domyślne w instalacjach Windows).
To po prostu implementuje powtarzalność podaną w OEIS jako jednoargumentowy operator.
źródło
CJam (19 bajtów)
Zestaw testów online . Jest to anonimowy blok (funkcja), który bierze jeden przedmiot ze stosu i pozostawia jeden na stosie. Pamiętaj, że pakiet testowy obejmuje
a(0) = 1
.Zastosowany wzorzec opiera się na obserwacji powiązanej sekwencji OEIS A006356 :
ale z odpowiednim przesunięciem, co eliminuje potrzebę finału,
+ 1
jak teraz objętya(0)
.Sekcja
źródło
Brain-Flak, 56 bajtów
Wykorzystuje algorytm wyszczególniony w pierwszym komentarzu na stronie OEIS.
Wypróbuj online!
Wyjaśnienie
Sekwencję można zdefiniować jako taką:
Program rozpoczyna się od
1
i wielokrotnie stosuje tę rekurencję do obliczeńu(k)
Kod z adnotacjami (faktyczna adnotacja, która ma nadejść)
Wizualizacja stosów
W jednej iteracji głównej pętli dzieje się tak (zwróć uwagę, że zera mogą być obecne lub nie, ale nie ma to żadnego znaczenia):
Stan stosów jest teraz tak samo jak to było na początku pętli, z wyjątkiem, że obecny stos ma teraz kolejne wartości
u
,v
iw
na nim.źródło
Perl 6, 48
Pierwotnie
ale zapomniałem, że potrzebowałem
sub f
takiego rozwiązania iteracyjnego.źródło
Dyalog APL, 30 bajtów
Używa brutalnej siły. Objaśnienie (przynajmniej moja najlepsza próba):
źródło
Dyalog APL, 29 bajtów
Działa przy użyciu rekurencyjnej definicji sekwencji liczb całkowitych OEIS A006356.
źródło
Python z Numpy, 62 bajty
Musiałem to wypróbować, ale wydaje się, że czysty Python, a rekurencja jest krótsza niż numpy, a wyraźne, oparte na macierzy obliczenia na stronie OEIS.
źródło
R,
6158555150 bajtówPobiera dane wejściowe ze standardowego wejścia, używa potęgowania macierzowego w celu ustalenia dokładnego wyniku.
Jeśli wolisz rozwiązanie rekurencyjne, oto prosta implementacja relacji rekurencji wymienionej w OEIS dla 55 bajtów .
źródło
Excel, 123 bajty
Implementuje formułę z OEIS:
Jak zawsze, wprowadź
A1
formułę w dowolnej innej komórce.Wykopali stare tożsamości Trig, aby sprawdzić, czy mogą być pomocne. Teraz boli mnie głowa.
źródło
Lithp , 79 bajtów
Implementuje rekurencyjną sekwencję liczb całkowitych wymienionych w OEIS.
Czytelny pakiet implementacyjny i testowy.
źródło