Sekwencja SUDSI ( su m, d ifference, s wap, i ncrement) to ciekawa sekwencja liczb całkowitych, która wydaje się wykazywać raczej chaotyczne zachowanie. Można go wygenerować w następujący sposób:

Niech S będzie nieskończona lista liczb naturalnych: 1 2 3 4 5 6 .... Niech S _i oznaczają jeden indeksowane i ty element S . Tak więc początkowo S ₁ to 1, S ₂ to 2 itd. (Nie ma S ₀ ).

Począwszy od S ₁ i S ₂ ...

• Oblicz ich sumę: sum = S1 + S2
• Oblicz ich różnicę bezwzględną (większy minus minus mniejszy): diff = |S1 - S2|

• Zamień dwie wartości w S na wskaźniki sumy i różnicy:swap(Ssum, Sdiff)

• Zwiększ wskaźniki S, z którym pracujesz. Więc następnym razem obliczysz sumę i różnicę S ₂ i S ₃ , a następnym razem będzie S ₃ i S ₄ itd.

• Powtórz ten proces w nieskończoność.

Oto kilka pierwszych etapów S po zastosowaniu tego procesu. Nawiasy kwadratowe []otaczają dwie wartości, które mają zostać zsumowane i zróżnicowane.

Oryginalny S :

[1 2] 3 4 5 6 7 8 9 10 11 12 ...

Po zamianie S ₃ ( 3 = 1 + 2) i S ₁ ( 1 = |1 - 2|):

3 [2 1] 4 5 6 7 8 9 10 11 12 ...

Po zamianie S ₃ i S ₁ :

1 2 [3 4] 5 6 7 8 9 10 11 12 ...

Po zamianie S ₇ i S ₁ :

7 2 3 [4 5] 6 1 8 9 10 11 12 ...

Po zamianie S ₉ i S ₁ :

9 2 3 4 [5 6] 1 8 7 10 11 12 ...

Po zamianie S ₁₁ i S ₁ :

11 2 3 4 5 [6 1] 8 7 10 9 12 ...

Po zamianie S ₇ i S ₅ :

11 2 3 4 1 6 [5 8] 7 10 9 12 ...

itp.

Sekwencja SUDSI jest zdefiniowana jako sekwencja pierwszych elementów na każdej z tych list. Tak więc kilka pierwszych warunków sekwencji SUDSI to 1 3 1 7 9 11 11.

Oto pierwsze 200 terminów sekwencji SUDSI (20 na linię):

1 3 1 7 9 11 11 11 15 15 19 19 19 19 19 19 19 19 19 19 
19 19 19 19 19 19 19 19 57 59 59 59 59 59 59 59 59 59 77 79 
81 83 85 87 89 91 91 91 91 91 91 91 91 91 91 91 91 91 115 115 
121 123 125 127 127 127 127 127 137 139 141 143 145 147 147 147 147 147 147 147 
147 147 147 147 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 
167 167 167 167 209 211 211 211 211 211 221 223 223 223 223 223 223 223 223 223 
223 223 243 243 243 243 243 243 257 259 261 263 263 263 263 263 263 263 263 263 
263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 
263 263 325 327 329 331 331 331 331 331 331 331 331 331 349 351 351 351 351 351 
361 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363

Nie jest (przynajmniej dla mnie) niejasne, jak można przewidzieć przyszłe warunki. Można jedynie bezpiecznie powiedzieć, że warunki są zawsze nieparzyste, nie maleją (po drugim semestrze) i że niektóre liczby są powtarzane wiele razy.

Wyzwanie

Napisz program lub funkcję, która przyjmuje dodatnią liczbę całkowitą n i wypisuje lub zwraca n- ty ciąg sekwencji SUDSI. Na przykład, jeśli n wynosi 1, wynikiem jest 1, jeśli n wynosi 2, wynikiem jest3 , jeśli n wynosi 200, wynikiem jest 363.

Weź dane w jakikolwiek zwykły sposób (stdin / linia poleceń / funkcja arg).
Najkrótsza odpowiedź w bajtach wygrywa.
(Ta strona koduje rzeczy w UTF-8, ale możesz użyć dowolnego istniejącego kodowania).

Premia matematyczna: (potencjalnie kwalifikująca się do nagrody)

• Opowiedz mi więcej o sekwencji SUDSI. Jaki jest podstawowy wzór tego, jakie są jego liczby i ile ich jest (i tym podobne)? (Nawiasem mówiąc, nie mogłem znaleźć SUDSI na OEIS .)

Pyth, 45 41 40 38 bajtów

MXGH_HhugGm@Gtd,s<>GH2.a-@GH@GhHtQr1yQ

Zauważyłem (podobnie jak Martin Büttner), że maksymalna zmieniona liczba kroków permutacji kwynosi 2k + 1. Ale ponieważ mamy tylko n - 1kroki, potrzebujemy tylko listy liczb do 2n - 1.

Wypróbuj online: demonstracja

M                       define a function g(G, H): return
                        (G is the list of numbers, H is a tuple)
 XGH_H                     a translation of G
                           (replaces the elements in H with the elements in reversed H)
                           in this application it swaps two values in the list G


                        implicit: Q = input()
 u     tQr1yQ           reduce, G = [1, 2, ..., 2*Q-1]
                        for each H in [0, 1, ..., Q - 2]:
                           G = 
  gG...                        g(G, ...)
h                       print the first element of the resulting list

And the second argument ... of the function call g is:

     ,                  create the tuple (
      s<>GH2               sum(G[H:][:2]), 
            .a-@GH@GhH     abs(G[H],G[H+1])
                        )
m@Gtd                   and map each value d to G[d - 1]

Mathematica, 88 bajtów

Last[f@n_:=n;(r=f@1;{f@a,f@b}={f[b=+##],f[a=Abs[#-#2]]};r)&@@f/@{#,#+1}&/@Range@Input[]]

Jest to pełny program, który odczytuje dane wejściowe z monitu. Jest to bardzo bezpośrednia implementacja definicji, w której śledzę bieżącą sekwencję f(której wartości f[n]domyślnie to n).

Oto nieco bardziej czytelna wersja:

Last[
  f@n_ := n;
  (
    r = f@1;
    {f@a,f@b} = {f[b=+##],f[a=Abs[#-#2]]};
    r
  ) & @@ f /@ {#,#+1} & /@ Range @ Input[]
]

Trochę analizy

Nakreśliłem pierwsze 2000 elementów sekwencji (potem tak naprawdę nie robi się to bardziej interesujące):

Zatem sekwencja jest zasadniczo liniowa ze spadkiem 2 i zawsze ma kilka z tych kroków. Wygląda na to, że kroki rosną subliniowo (jeśli nawet nie są ograniczone), ponieważ stają się ledwo zauważalne w miarę zwiększania liczby rysowanych punktów.

Możemy dość łatwo uzasadnić wzrost liniowy (jest to trochę skomplikowane, ale myślę, że wytrzymałoby rygorystyczny dowód przez indukcję): początkowo maksymalna wpływana liczba kroków permutacji nwynosi n + (n+1) = 2n + 1. Pamiętaj też, że liczby te będą zawsze przenoszone do 1, ponieważ |n - (n+1)| = 1. Nic więc dziwnego, że otrzymujemy liczby, które są w przybliżeniu 2nw sekwencji. Możemy jednak również zauważyć, że dla kroków do n , S _{n + 1} jest zawsze ograniczone przez n + 1 , co oznacza, że ​​żaden krok zamiany nie może zamienić dwóch liczb, które są większe niż jest to również związane z samą sekwencją. n . Dlatego liczby, które nadal wymagają przetworzenia, będą mniejsze lub równe ich wartości początkowej. W związku z tym,2n + 1

Myślę, że znalezienie argumentu za długością kroków będzie trudniejsze.

CJam, 45 40 39 bajtów

Po prostu naiwne podejście. Można dalej grać w golfa. Za bardzo brakuje funkcji zamiany tablic.

ri_K*,\{\:L>2<L1$:+:S@:-z:DL=tDSL=t}/1=

Jak to działa:

ri_                             "Read the input, convert to integer and copy it";
   K*,                          "Multiply the copy by 20 and get 0 to 20*input-1 array";
      \{ ... }/1=               "Swap and put input on stack and run the loop that many";
                                "times. After the loop, take the second element as";
                                "we have a 0 based array while series is 1 based";
{\:L>2<L1$:+:S@:-z:DL=tDSL=t}
 \:L                            "Swap to put iteration index behind the array";
                                "and store array in L";
    >2<                         "In each loop, the iteration index will be on stack";
                                "Get the two elements from the array starting at that";
       L1$                      "Put the array on stack and copy the tuple";
          :+:S                  "Get the sum and store it in S";
              @:-z:D            "Get the absolute difference of the tuple and store in D";
                    L=t         "Put the element at S diff at sum index";
                       DSL=t    "Put the element at S sum at diff index";

Wypróbuj online tutaj

Haskell, 95 bajtów

f#n=let b=f$n+1;l=f n+b;r=abs$f n-b;y x|x==l=f r|x==r=f l|1<2=f x in y
p n=foldl(#)id[1..n-1]$1

Przykład użycia: p 70->139

Nie przechowuję sekwencji na liście ani w tablicy. Wielokrotnie aktualizuję funkcję tożsamości do funkcji z zamienionymi dwoma elementami bieżącego kroku. Po nkrokach wywołuję wynikową funkcję z parametrem 1.

J, 63 bajty

3 :'{.>((1-~{(+,|@-)]{~1+[)|.@:{`[`]}])&.>/(<"*i.1-y),<>:i.3*y'

Zastosowanie i testy:

   f=.3 :'{.>((1-~{(+,|@-)]{~1+[)|.@:{`[`]}])&.>/(<"*i.1-y),<>:i.3*y'

   f 5
9
   f every 1+i.20
1 3 1 7 9 11 11 11 15 15 19 19 19 19 19 19 19 19 19 19

Wypróbuj online tutaj.

Pyth 55 53 51

Prawdopodobnie może być dalej golfa. Może być bardzo powolny dla dużych, nponieważ byłem leniwy, aby dowiedzieć się, ile długości tablicy potrzebuję i po prostu użyłem n^njednego.

Dzięki Volatility i Martinowi Büttnerowi za wskazanie, że mogę użyć maksymalnie 3n.

KU*3QFNr1QJ@KN=G@tKNAJG,+JG.a-JG=Y@KJ XXKJ@KGGY)@K1

Wyjaśnienie

                   Q = input (implicit)
KU*3Q              K = range(3 * Q)
FNr1Q              for N in range(1, Q):
 J@KN               J = K[N]
 =G@tKN             G = K[1:][N]
 AJG,+JG.a-JG       J, G = J + G, abs(J - G)
 =Y@KJ              Y = K[J]
 XXKJ@KGGY          K[J], K[G] = K[G], Y
)
@K1                print K[1]

Python 2, 117 106 101

j=input();a=range(3*j)
for i in range(1,j):b,c=a[i:i+2];d=abs(b-c);a[b+c],a[d]=a[d],a[b+c]
print a[1]

Używa dict(mapy) do zapisywania wartości w celu użycia dowolnych indeksów. g(n)jest funkcją zwracającą nth pozycję. Następnie tylko iteruje input-1czasy i wyświetla pierwszy element.

Okazuje się, że jest krótszy przy użyciu metod z mojej odpowiedzi w Pythonie.

Dzięki xnor za oszczędność 5 bajtów.

Idź 150

func f(j int){a:=make([]int,j*2);for i:=range a{a[i]=i};for i:=1;i<j;i++{b,c:=a[i],a[i+1];v:=b-c;if v<0{v*=-1};a[b+c],a[v]=a[v],a[b+c]};println(a[1])}

Bez golfa, nic trudnego, głównie skradziony z @ Pietu1998

func f(j int) {
    a := make([]int, j*2) // Build the array we will be working on
    for i := range a {
        a[i] = i
    }
    for i := 1; i < j; i++ {
        b, c := a[i], a[i+1]
        v := b - c
        if v < 0 {
            v *= -1
        }
        a[b+c], a[v] = a[v], a[b+c]
    }
    println(a[1])
}

http://play.golang.org/p/IWkT0c4Ev5

Java, 162

int f(int n){int a[]=new int[2*n],s,d,x,t;for(x=0;x<2*n;)a[x]=++x;for(x=0;++x<n;){s=a[x]+a[x-1]-1;d=Math.abs(a[x]-a[x-1])-1;t=a[s];a[s]=a[d];a[d]=t;}return a[0];}

Wyjaśnienie

int f(int n) {
    int a[] = new int[2 * n], sum, diff, x, temp;
    for (x = 0; x < 2 * n;) {
        a[x] = ++x;  // set initial array
    }
    for (x = 0; ++x < n;) {
        sum = a[x] + a[x - 1] - 1;
        diff = Math.abs(a[x] - a[x - 1]) - 1;
        temp = a[sum];
        a[sum] = a[diff];
        a[diff] = temp;
    }
    return a[0];
}

dc 134 132 131 bajtów

[_1*]sOdsn2*ddslsSsa[ladd:S1-dsa0<P]dsPx1d0rsN:N[la1+dsad;SdS@r1+;SdS@rL@L@r+Ss-d0>Od;SrLsdSsrLs;Sr:S:S1;SladsN:Nlaln>G]dsGxln1-;Nf

Użyj echo $n $code | dc, gdzie $njest n i $codejest ... kodem ( westchnienie ). Cytat do smaku.

Edycja: Dopóki nie przeprosisz mnie za wyjaśnienie, nigdy się do tego nie przejdę.

Perl 5, 131

Naiwne rozwiązanie (tj. Bezpośrednie wdrożenie definicji). Podprogram, przyjmuje dane wejściowe jako listę1 s żądanej długości.

{map$a[$_]=$_,1..3*@_;($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_;$a[1]}

Wizualizuj jego wynik, np print sub...->(1,1,1,1,1) .

Wyjaśnienie:

map$a[$_]=$_,1..3*@_buduje tablicę @a, indeksując każdą liczbę całkowitą od 1 do 3 razy większą niż@_ (wejściowa).

($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_powtarza wielokrotnie switcheroo (jeden raz mniej niż rozmiar @_), przełączając za $a[$a[$_-1]+$a[$_]]pomocą $a[abs($a[$_-1]-$a[$_])]as$_ wynosi od 2 do rozmiaru @_.

A potem podprogram wraca $a[1].

Perl 5 , 90 + 1 (-p) = 91 bajtów

@a=0..3*$_;$_=(map{@a[$d,$s]=@a[$s=$a[$_]+$a[$_-1],$d=abs$a[$_]-$a[$_-1]];$a[1]}1..$_)[-1]

Wypróbuj online!