Последовательность SUDSI ( су м, д ifference, ˙s WAP, я ncrement) представляет собой целое число , любопытная последовательность , которая , как представляется , обладает довольно хаотическим поведением. Это может быть сгенерировано следующим образом:

Пусть S бесконечный список натуральных чисел: 1 2 3 4 5 6 .... Пусть S _я обозначаю один индексированный я й элемент S . Итак, изначально S ₁ равно 1, S ₂ равно 2 и т. Д. ( S _{0 отсутствует} ).

Начиная с S ₁ и S ₂ ...

• Подсчитайте их сумму: sum = S1 + S2
• Вычислите их абсолютную разницу (чем больше, тем меньше): diff = |S1 - S2|

• Поменяйте местами два значения в S по индексам суммы и разности:swap(Ssum, Sdiff)

• Увеличьте показатели S, с которыми вы работаете. Поэтому в следующий раз вы будете вычислять сумму и разность S ₂ и S ₃ , а время после этого будет S ₃ и S ₄ и т. Д.

• Повторите этот процесс до бесконечности.

Вот первые несколько этапов S, как этот процесс применяется. Квадратные скобки []окружают два значения, которые будут суммироваться и различаться.

Оригинал S :

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

После того, как S ₃ ( 3 = 1 + 2) и S ₁ ( 1 = |1 - 2|) поменялись местами:

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

После того, как S ₃ и S ₁ поменялись местами:

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

После того, как S ₇ и S ₁ поменялись местами:

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

После того, как S ₉ и S ₁ поменялись местами:

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

После того, как S ₁₁ и S ₁ поменялись местами:

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

После того, как S ₇ и S ₅ поменялись местами:

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

и т.п.

Последовательность SUDSI определяется как последовательность первых элементов в каждом из этих списков. Итак, первые несколько терминов последовательности SUDSI 1 3 1 7 9 11 11.

Вот первые 200 членов последовательности SUDSI (20 на строку):

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

Неясно (по крайней мере мне), как можно предсказать будущие условия. Можно только с уверенностью сказать, что эти термины всегда нечетные, неубывающие (после второго слагаемого) и что некоторые числа повторяются много раз.

Вызов

Напишите программу или функцию, которая принимает положительное целое число n и печатает или возвращает n- й член последовательности SUDSI. Например, если n равно 1, вывод равен 1, если n равен 2, вывод равен 3, если n равно 200, вывод равен 363.

Возьмите ввод любым обычным способом (стандартная строка / командная строка / функция arg).
Самый короткий ответ в байтах побеждает.
(Этот сайт кодирует вещи в UTF-8, но вы можете использовать любую чертову существующую кодировку, какую захотите.)

Бонус Мати: (потенциально имеет право на награду)

• Расскажите мне больше о последовательности SUDSI. Каков базовый шаблон того, какие числа являются его частью и сколько их (и тому подобное)? (Кстати, я не смог найти SUDSI в OEIS .)

Pyth, 45 41 40 38 байт

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

Я заметил (как и Мартин Бюттнер), что максимальное количество влияющих на шаг перестановки kравно 2k + 1. Но так как у нас есть только n - 1шаги, нам нужен только список чисел до 2n - 1.

Попробуйте онлайн: демонстрация

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 байт

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

Это полная программа, считывающая ввод из приглашения. Это очень прямая реализация определения, где я отслеживаю текущую последовательность вf (значения которой по f[n]умолчанию равныn ).

Вот немного более читаемая версия:

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

Некоторый анализ

Я подготовил первые 2000 элементов последовательности (потом это не очень интересно):

Таким образом, последовательность по существу линейна с наклоном 2 и всегда имеет несколько таких шагов. Кажется, что шаги растут сублинейно (если они даже не ограничены), так как они становятся едва заметными, когда вы увеличиваете количество точек, которые вы строите.

Мы можем обосновать линейный рост довольно легко (это немного сложновато, но я думаю, что оно выдержит строгие доказательства по индукции): изначально максимальное затронутое число шага перестановки nравно n + (n+1) = 2n + 1. Также обратите внимание , что эти цифры будут всегда быть перемещены 1, так как |n - (n+1)| = 1. Поэтому неудивительно, что мы получаем числа, которые находятся приблизительно 2nв последовательности. Тем не менее, мы можем также отметить , что для шагов до п , S _{п + 1} всегда ограничена п + 1 , что означает , что ни один шаг подкачка не может поменять два номера , которые являются одновременно больше , чем п . Следовательно, числа, которые еще нужно обработать, будут меньше или равны их первоначальному значению. Следовательно, является также оценка для самой последовательности.2n + 1

Я думаю, что найти аргумент в пользу длины шагов будет сложнее.

CJam, 45 40 39 байт

Просто наивный подход. Можно играть в гольф дальше. Слишком много отсутствует функция подкачки массива.

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

Как это устроено:

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";

Попробуйте онлайн здесь

Haskell, 95 байт

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

Пример использования: p 70->139

Я не храню последовательность в списке или массиве. Я неоднократно обновляю функцию тождества до функции с заменой двух элементов текущего шага. После nшагов вызываю результирующую функцию с параметром 1.

J, 63 байта

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

Использование и тесты:

   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

Попробуйте это онлайн здесь.

Pyth, 55 53 51

Может быть, можно играть в гольф дальше. Возможно, получится очень медленно для большого размера, так nкак мне было лень выяснить, какой размер массива мне понадобится, и просто использовал n^nодин.

Спасибо Волатильности и Мартину Бюттнеру за указание, что я могу использовать максимум 3n.

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

объяснение

                   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]

Использует dict(карту), чтобы сохранить значения для использования произвольных индексов. g(n)является функцией, возвращающей nэлемент th Затем просто повторяет input-1время и выводит первый элемент.

Оказывается, короче, используя методы из моего ответа Pyth.

Спасибо xnor за сохранение 5 байтов.

Go 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])}

Не обманутый, ничего хитрого, в основном украденного у @ 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

Ява, 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];}

объяснение

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];
}

Округ Колумбия, 134 132 131 байт

[_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

Используйте echo $n $code | dc, где $nесть п и $code... код ( задыхаться ). Цитата по вкусу.

Изменить: Если вы не приставать ко мне для объяснения, я никогда не буду обойти это.

Perl 5, 131

Наивное решение (то есть прямая реализация определения). Подпрограмма, она принимает входные данные в виде списка 1s желаемой длины.

{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]}

Визуализируйте его вывод, например print sub...->(1,1,1,1,1).

Объяснение:

map$a[$_]=$_,1..3*@_строит массив @a, индексируя каждое целое число в 1–3 раза больше размера @_(входного).

($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_повторяет переключатель многократно (один раз меньше, чем размер @_), переключение$a[$a[$_-1]+$a[$_]] с $a[abs($a[$_-1]-$a[$_])]в $_диапазоне от 2 до размера @_.

И тогда подпрограмма возвращается $a[1].

Perl 5 , 90 + 1 (-p) = 91 байт

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

Попробуйте онлайн!