Inspirowany poprzednim pytaniem .

Samoopisująca się sekwencja g (n) Golomb jest sekwencją, w której dowolna liczba naturalna njest powtarzana w ciągu g (n) razy.

Pierwsze kilka liczb w sekwencji to:

n    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
g(n) 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

Widać, że g (4) = 3 i że „4” powtarza się 3 razy w sekwencji.

Biorąc pod uwagę wejście n, wyjście g(n).

Ograniczenia: n <100000.

Najmniejszy kod wygrywa.

GolfScript (31 znaków)

~([1 2.]2{.2$=[1$)]*@\+\)}3$*;=

Próbny

Galaretka , niekonkurująca

10 bajtów Ta odpowiedź nie konkuruje, ponieważ wyzwanie poprzedza powstanie galaretki.

’ßßạ¹ß‘µṖ¡

Wykorzystuje to wzór rekurencyjny a (1) = 1, a (n + 1) = 1 + a (n + 1 - a (a (n))) ze strony OEIS.

Wypróbuj online!

Jak to działa

’ßßạ¹ß‘µṖ¡ Main link. Input: n

’          Decrement; yield n - 1.
 ßß        Recursively call the main link twice, with argument n - 1.
   ạ¹      Take the absolute difference of a(a(n - 1)) and n.
     ß     Recursively call the main link, with argument n - a(a(n - 1)).
      ‘    Increment the result, yielding 1 + a(n - a(a(n - 1))).
       µ   Combine the chain to the left into a single link.
        Ṗ  Pop [1, ..., n]. This yields [] iff n == 1.
         ¡ Execute the chain iff Ṗ returned a non-empty array.

PHP - 63 znaki

function g($n){for(;++$i<=$n;){for(;++$j<=$i;){echo $i;}$j=0;}}

Szybko i krótko.

Wydaje mi się, że miałem na myśli niewłaściwą sekwencję. Derp.

To jest PRAWIDŁOWE, szybkie i krótkie.

function g($n){for(;++$i<$n;){echo round(1.201*pow($i,.618));}}

Dokładność może przekroczyć wymagany 100 000 znaków, ale w rzeczywistości osiągnąłem ten znak.

PHP

Ta wersja rekurencyjna jest krótsza (60), ale nieefektywna obliczeniowo:

function g($n){return$n==1?1:1+g($n-g(g($n-1)));}echo g($n);

Jest to znacznie szybsze, ale dłuższe (78):

$a=[1,2,2];for($i=3;$i<$n;$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Znacznie szybciej, ale przy 89 znakach byłoby:

$a=[1,2,2];for($i=3;!isset($a[$n-1]);$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Który jest O (n)

Haskell, 30 27 znaków

g 1=1
g n=1+(g$n-g(g$n-1))

Oaza , 7 bajtów (niekonkurująca)

Kod:

n<aae>T

Wypróbuj online!

Oasis to język zaprojektowany przez Adnana, który specjalizuje się w sekwencjach.

Obecnie ten język może wykonywać rekurencję i formę zamkniętą.

Na Tkońcu jest skrót 10, co oznacza, że a(0) = 0i a(1) = 1. Aby dodać więcej przypadków testowych, po prostu dodaj do listy na końcu.

n<aae>T
n<aae>10  expanded

       0  a(0) = 0
      1   a(1) = 1

n         push n (input)
 <        -1
  a       a(above)  [a is the sequence]
   a      a(above)
    e     a(n-above)
     >    +1

Teraz w zasadzie obliczyliśmy a(n-a(a(n-1))+1.

Perl, 48 znaków

(@a=(@a,($,)x($a[$,++]||$,)))<$_?redo:say$,for<>

Wejście na standardowe wejście, wyjście na standardowe wyjście. Potrzebuje Perla 5.10+ i -M5.010aby włączyć tę sayfunkcję. Zajmuje około O ( n ² ) czasu z powodu nieefektywnej manipulacji tablicą, ale wciąż jest wystarczająco szybki, aby łatwo obliczyć do 100 000. kadencji.

Julia - 28

Przez rekurencyjnego sposób:

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

Wynik:

[a(i) for i=1:20]'
1x20 Array{Int64,2}:
 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

Python - 64 znaki

n=input()
g=[1,2,2]
for i in range(3,n):g+=[i]*g[i-1]
print g[n]

JavaScript, 93 znaki

c=[,1],i=c.length;function g(n){for(i;i<n;i++) c[i]=g(i);return c[n]||(c[n]=1+g(n-g(g(n-1))))}

J, 43 znaki

f=:3 :'<.@:+&0.5(p^2-p)*y^p-1[p=:(+%)/20$1'

Definiuje funkcję za pomocą asymptotycznego wyrażenia podanego na stronie wikipedia.

   f 5
3
   f 20
8
   f 100000
1479

Irytujące jest 9 znaków zaokrąglających do najbliższej liczby całkowitej.

Preludium , 69 55 54 bajtów

?1-(v  #1)-
1   0v ^(#    0 (1+0)#)!
    (#)  ^#1-(0)#

Jeśli używany jest standardowy zgodny interpreter, przyjmuje on dane wejściowe i wyjściowe jako wartości bajtów . Aby właściwie używać liczb dziesiętnych na STDIN / STDOUT, że trzeba interpreter Pythona z NUMERIC_OUTPUT = Trueoraz dodatkową opcję NUMERIC_INPUT = True.

Wyjaśnienie

Szkielet programu to

?1-(    1 -
1                     )!

Czytamy dane wejściowe Nna pierwszym głosie i zmniejszamy je, aby uzyskać N-1. Inicjujemy również drugi głos na 1. Następnie zapętlamy N-1jeden raz, z których każda iteracja otrzymuje następną wartość sekwencji na drugim stosie. Na koniec wypisujemy Nnumer th.

Ideą programu jest umieszczenie każdego elementu sekwencji w kolejce na trzecim głosie i zmniejszenie nagłówka tej kolejki w każdej iteracji. Kiedy głowa osiągnie 0, zwiększamy wartość sekwencji i ją usuwamy 0.

Problem polega na tym, że Prelude używa stosów, a nie kolejek. Musimy więc trochę przesunąć ten stos, aby użyć go jak kolejki.

v  #
0v ^
(#)

Spowoduje to skopiowanie bieżącej wartości sekwencji do pierwszego głosu (jako kopia tymczasowa), wypycha a 0na drugi głos (aby zaznaczyć koniec kolejki). Następnie wykonuje pętlę, aby przesunąć (a tym samym odwrócić) trzeci stos na drugi. Po pętli umieszczamy kopię bieżącej wartości sekwencji na drugim stosie (który jest ogonem naszej kolejki).

 )
(#
 ^#1-

To wygląda trochę brzydko, ale w zasadzie jest to pętla, która przesuwa stos z powrotem na trzeci głos. Ponieważ )jest w tej samej kolumnie, co instrukcje dotyczące przesunięcia, wcześniej 0wstawiony drugi głos również skończy na trzecim, więc musimy go usunąć innym #. Następnie zmniejsz górną część trzeciego głosu, tj. Głowę kolejki.

Teraz robi się to trochę denerwujące - chcemy uruchomić kod, gdy ta wartość jest 0, ale jedyna struktura kontrolna Preludium (pętla) reaguje tylko na wartości niezerowe.

 0 (1+0)#
(0)#

Zauważ, że góra drugiego głosu jest prawdziwa (ponieważ sekwencja Golomb nie zawiera żadnych 0s). Obciążenie idzie więc w ten głos (druga para nawiasów). Musimy tylko temu zapobiec , jeśli szef kolejki 0jeszcze nie jest . Najpierw mamy „pętlę” na trzecim głosie, która przesuwa a 0na drugi głos, jeśli głowa kolejki jest wciąż niezerowa. Dajemy także 0trzeci głos, aby natychmiast opuścić pętlę. #Na trzecim głosem, który następnie albo usuwa 0lub usuwa głowę kolejce jeśli to już było zera. Teraz ta druga pętla jest wprowadzana tylko wtedy, gdy na początku kolejki było zero (i0na drugi głos nigdy nie został popchnięty). W takim przypadku zwiększamy bieżącą wartość sekwencji i wciskamy a, 0aby wyjść z pętli. Na koniec zawsze będzie 0stos na szczycie stosu, który musimy odrzucić.

Mówiłem, że logiczna negacja jest denerwująca w Preludium ...

Mathematica, 27 bajtów

f@1=1;f@n_:=1+f[n-f@f[n-1]]

Kolejne rozwiązanie rekurencyjne.

CJam, 14 bajtów

CJam jest znacznie młodszy od tego wyzwania, więc ta odpowiedź nie kwalifikuje się do zielonego znacznika wyboru. Jednak dość rzadko można jto dobrze wykorzystać , więc i tak chciałem to opublikować.

l~2,{_(jj-j)}j

Sprawdź to tutaj.

Wyjaśnienie

jjest w zasadzie „zapamiętanym operatorem rekurencyjnym”. Wymaga liczby całkowitej N, tablicy i bloku F. Tablica służy do inicjalizacji zapamiętywania: element o indeksie izostanie zwrócony F(i). jnastępnie oblicza F(N), sprawdzając go lub uruchamiając blok (z nna stosie), jeśli wartość nie została jeszcze zapamiętana. Naprawdę sprytną cechą jest to, że w bloku jprzyjmuje tylko liczbę całkowitą ii wywołuje F(i)rekurencyjnie. Oto kod:

l~             "Read and eval input.";
  2,           "Push a 2-range onto the stack, i.e. [0 1]. The first value is irrelevant
                but the second value is the base case of the recursion.";
    {       }j "Compute F(N).";
     _(        "Duplicate i and decrement to i-1.";
       jj      "Compute F(F(i-1)).";
         -     "Subtract from i.";
          j    "Compute F(n-F(F(i-1))).";
           )   "Increment the result.";

J, 16 bajtów

    <:{1($1+I.)^:[~]

    (<:{1($1+I.)^:[~]) every 1+i.20  NB. results for inputs 1..20
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8

To rozwiązanie jest w dużej mierze oparte na rozwiązaniu algorytmicznym podobnego problemu. Znajdziesz tam wyjaśnienie tej metody.

J, 33 bajty

W tym podejściu tworzę sekwencję h(k)z wartościami pierwszych indeksów, w iktórych g(i)=ktak h = 1 2 4 6 9 12 16.... Możemy uzyskać h(k)dość prosto h(1..k-1)z wyrażeniem, w ({:+1+[:+/#<:])którym znajduje się dane wejścioweh(1..k-1) .

Obliczenie wyniku z hjest proste.h ([:+/]>:[) input

[:+/]>:1 2(,{:+1+[:+/#<:])@]^:[~]

Brachylog , 13 bajtów (niekonkurencyjny)

1|-₁↰↰:?-ṅ↰+₁

Wypróbuj online!

Wyjaśnienie

1                Input = 1 = Output
 |               Or
  -₁↰            a(Input - 1)
     ↰           a(a(Input - 1))
      :?-ṅ       Input - a(a(Input - 1))
          ↰      a(Input - a(a(Input - 1))
           +₁    1 + a(Input - a(a(Input -1))

Python - 76 znaków

n=20;g=[1,2,2];[[g.append(i)for j in range(g[i-1])]for i in range(3,n)];g[n]

JavaScript - 48 znaków

for(g=[,i=j=k=1,2];i<1e5;k=--k?k:g[++j])g[i++]=j

Tworzy 1-indeksową tablicę gzawierającą wartości sekwencji.

Edycja - JavaScript - 46 znaków

v=[,1];for(x=2;x<1e5;)v[x]=1+v[x-v[v[x++-1]]]

Tworzy 1-indeksową tablicę vzawierającą wartości sekwencji.

Edycja 2 - ECMAScript 6 - 27 znaków

g=x=>x-1?1+g(x-g(g(x-1))):1

Pierwsze dwa są dość szybkie - trzecie jest bardzo wolne

Haskell, 63 bajty

f n|n<3=n|n<4=2|1>0=foldr1(++)[replicate(f m)m|m<-[1..]]!!(n-1)

Jest to naiwne podejście, nie byłem świadomy bardzo krótkiego ponownego wystąpienia, kiedy to napisałem, ale pomyślałem, że mimo to opublikuję, nawet jeśli jest on dłuższy niż wszystkie inne implementacje Haskell, jak np.

Oblicz n-ty termin samoopisującej sekwencji Golomba

i

https://codegolf.stackexchange.com/a/23979/24877