Арифметический цикл

13

Входные данные:

Целое число, nкоторое является >=0или >=1( f(0)необязательно)

Выход:

n«Й номер в следующей последовательности, или последовательность вплоть до и включая n» го числа.

Последовательность:

(0),1,-1,-3,0,5,-1,-7,0,9,-1,-11,0,13,-1,-15,0,17,-1,-19,0,21,-1,-23,0,25,-1,-27,0,29,-1,-31,0,33,-1,-35,0,37,-1,-39,0,41,-1,-43,0,45,-1,-47,0,49,-1,-51,0,53,-1,-55,0,57,-1,-59,0,61,-1,-63,0,65,-1,-67,0,69,-1,-71,0,73,-1,-75,0,77,-1,-79,0,81,-1,-83,0,85,-1,-87,0,89,-1,-91,0,93,-1,-95,0,97,-1,-99

Как строится эта последовательность?

f(n=0) = 0(необязательно)
f(n=1) = f(0) + nили f(n=1) = 1
f(n=2) = f(1) - n
f(n=3) = f(2) * n
f(n=4) = f(3) / n
f(n=5) = f(4) + n
т. д.

Или в псевдокоде:

function f(integer n){
  Integer result = 0
  Integer i = 1
  Loop as long as i is smaller than or equal to n
  {
    if i modulo-4 is 1:
      result = result plus i
    if i modulo-4 is 2 instead:
      result = result minus i
    if i modulo-4 is 3 instead:
      result = result multiplied with i
    if i modulo-4 is 0 instead:
      result = result integer/floor-divided with i
    i = i plus 1
  }
  return result
}

Но, как вы могли заметить, в последовательности есть два шаблона:

0, ,-1,  ,0, ,-1,  ,0, ,-1,   ,0,  ,-1,   ,0,  ,-1,   ,...
 ,1,  ,-3, ,5,  ,-7, ,9,  ,-11, ,13,  ,-15, ,17,  ,-19,...

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

Правила вызова:

  • 0-индексированные и 1-индексированные входы приведут к одному и тому же результату (поэтому f(0)необязательно для 0-индексированных входов, если вы хотите включить его).
  • Вам разрешено вывести nый номер этой последовательности. Или всю последовательность вверх и включая nномер. (Так f(5)может привести либо либо, 5либо 0,1,-1,-3,0,5.)
    • Если вы решите вывести последовательность вплоть до nчисла с номером, формат вывода будет гибким. Может быть списком / массивом, строкой с разделителями-запятыми / пробелами / новой строкой или напечатанной в STDOUT и т. Д.
  • Divide ( /) - это целочисленное / минимальное деление, которое округляется до 0 (не до отрицательной бесконечности, как в некоторых языках).

Основные правила:

  • Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
    Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте найти как можно более короткий ответ для «любого» языка программирования.
  • К вашему ответу применяются стандартные правила , поэтому вы можете использовать STDIN / STDOUT, функции / метод с правильными параметрами и типом возврата, полные программы. Ваш звонок.
  • По умолчанию лазейки запрещены.
  • Если возможно, добавьте ссылку с тестом для вашего кода.
  • Также, пожалуйста, добавьте объяснение, если это необходимо.

Дополнительные тестовые примеры выше n=100:

Input     Output

1000      0
100000    0
123       -123
1234      -1
12345     12345
123456    0
code-golf number sequence arithmetic integer Кевин Круйссен
источник
1
Я не смог найти это на oeis.org, поэтому вы можете отправить его туда. Это интересная последовательность, я удивлен, что никто не зарегистрировал ее.
труба
1
@pipe это выглядит довольно произвольно
qwr

Ответы:

20

JavaScript (ES6), 19 байт

n=>[0,n,-1,-n][n&3]

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

доказательство

Предположим, что мы имеем следующие отношения для некоторого n, кратного 4. Эти отношения тривиально проверяются для первых членов последовательности.

f(n)   = 0
f(n+1) = n+1
f(n+2) = -1
f(n+3) = -(n+3)

И пусть N = n + 4 . Тогда по определению:

f(N)   = f(n+4) = f(n+3) // (n+4) = -(n+3) // (n+4) = 0
f(N+1) = f(n+5) = f(n+4) + (n+5)  = 0 + (n+5)       = N+1
f(N+2) = f(n+6) = f(n+5) - (n+6)  = (n+5) - (n+6)   = -1
f(N+3) = f(n+7) = f(n+6) * (n+7)  = -1 * (n+7)      = -(N+3)

Что в силу математической индукции доказывает, что соотношения верны для любого N, кратного 4 .

Arnauld
источник
2
Поскольку большинство ответов являются портами этого решения, я хочу добавить, что я проверил, что оно доказуемо.
Эрик Outgolfer
У меня есть альтернативное доказательство.
Эрик Outgolfer
Ах, чокнутый, отвлекся на работу, работая над чем-то очень похожим. +1
лохматый
Из любопытства, есть ли причина предпочитать "n & 3" перед "n% 4"?
IanF1
2
@ IanF1 Полагаю, это просто привычка программирования низкого уровня (вычисление побитового И в сборке проще и быстрее, чем вычисление по модулю). Но в этом нет особого смысла, и я на самом деле наполовину испытывал желание изменить его на n%4потом, чтобы он работал с числами больше 32-битных.
Арно
4

05AB1E , 8 байтов

Выводит nthчисло

ÎD(®s)sè

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

05AB1E , 14 байтов

Выводит список чисел до N, используя шаблоны в последовательности

ÅÉāÉ·<*āÉ<‚øí˜

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

объяснение

Пример использования N = 7

ÅÉ               # List of odd numbers upto N
                 # STACK: [1,3,5,7]
  ā              # Enumerate 1-based
   É             # is odd?
                 # STACK: [1,3,5,7],[1,0,1,0]
    ·<           # double and decrement
                 # STACK: [1,3,5,7],[1,-1,1,-1]
      *          # multiply
                 # STACK: [1,-3,5,-7]
       āÉ<       # enumerate, isOdd, decrement
                 # STACK: [1,-3,5,-7],[0,-1,0,-1]
          ‚ø     # zip
                 # STACK: [[1, 0], [-3, -1], [5, 0], [-7, -1]]
            í    # reverse each
             ˜   # flatten
                 # RESULT: [0, 1, -1, -3, 0, 5, -1, -7]
Emigna
источник
4

Python 2 , 25 байт

Порт Арнаулда ответ:

lambda n:[0,n,-1,-n][n%4]

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

Наивные решения:

Python 3 , 50 49 байтов

lambda n:n and eval('int(f(n-1)%sn)'%'/+-*'[n%4])

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

Python 2 , 78 77 76 58 57 53 52 байта

lambda n:n and eval('int(1.*f(n-1)%sn)'%'/+-*'[n%4])

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

Используется куча байтов int, потому что пол питона делится, а не навстречу 0, как в вопросе.

TFeld
источник
@KevinCruijssen Да, спасибо :)
TFeld
3

TIS -n 2 1 , 123 байта

Выводится nчисло для 0 <= n <= 999. (Верхний предел обусловлен языковыми ограничениями).

@0
MOV UP ACC
MOV ACC ANY
L:SUB 4
JGZ L
JEZ L
ADD 5
JRO -5
@1
MOV UP ACC
JRO UP
SUB ACC
JRO 3
MOV 1 ACC
NEG
MOV ACC ANY
HCF

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

TIS -n 2 1 , 124 байта

Выводится nчисло для 0 <= n <= 999. (Верхний предел обусловлен языковыми ограничениями). nМожно указать несколько , разделенных пробелами.

@0
MOV UP ACC
MOV ACC ANY
L:SUB 4
JGZ L
JEZ L
ADD 5
MOV ACC ANY
@1
MOV UP ACC
JRO UP
SUB ACC
JRO 3
MOV 1 ACC
NEG
MOV ACC ANY

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

TIS -n 3 1 , 192 байта

Выводит значения 0..nдля 0 <= n <= 999. (Верхний предел обусловлен языковыми ограничениями).

@0
MOV UP ACC
ADD 1
MOV ACC ANY
JRO -1
@1
SUB UP
JLZ C
HCF
C:ADD UP
MOV ACC ANY
ADD 1
SWP
ADD 1
MOV ACC ANY
SUB 4
JEZ W
ADD 4
W:SWP
@2
MOV UP ACC
JRO UP
SUB ACC
JRO 3
MOV 1 ACC
NEG
MOV ACC ANY

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

Все используют числовой ввод / вывод ( -nфлаг). Первые два решения используют два вычислительных узла, один из которых расположен над другим. Третий имеет стек из трех узлов.

Для первых двух решений верхний узел считывает ввод, отправляет исходное число, затем многократно вычитает 4 до отрицательного значения, а затем добавляет 5 к индексу для нашей таблицы переходов. Это эквивалентно (n % 4) + 1.

Третье решение разделило эту задачу на два узла; верхний просто повторяет ограничение до конца времени, а средний узел параллельно подсчитывает индекс (по сравнению с этим пределом) и по модулю, как указано выше.

Нижний узел всех трех решений одинаков; у него есть таблица прыжков, и здесь происходит волшебство. Мы хранить исходное число в ACC, то JRO(вероятно , J UMP R elative O ffset) вперед 1,2 , 3, или 4, в зависимости от того, что выше говорит узел.

Работа в обратном направлении:

  • 4будет а ) NEGсъел ACC, а б ) двигаться ACCвниз для выхода.
  • 3поместит 1в ACC, а затем выполнить шаги и44 б .
  • 2прыгнет прямо к шагу 4б .
  • 1будет SUBтянуть ACCсебя (фактически обнуление ACC), затем делать шаг 2, который переходит на 4b .
Phlarx
источник
2

C (gcc) , 62 байта

f(n,k){k=~-n;n=n?n%4?k%4?n-2&3?f(k)*n:f(k)-n:f(k)+n:f(k)/n:0;}

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

Джонатан Фрех
источник
Вы можете в два раза сократить количество байтов (31 байт), создав порт ответа OlivierGrégoire на Java : f(n){n=n%2>0?n*(2-n%4):n%4/-2;}я бы добавил его в качестве второго ответа, поскольку мне также нравится ваш рекурсивный подход. :)
Кевин Круйссен
@KevinCruijssen Я видел их решение Java 10 и заметил его краткость, хотя я не хотел просто копировать их решение, так как арифметические синтаксисы двух языков слишком похожи.
Джонатан Фрех
1

Сетчатка , 46 байт

.+
*
r`(____)*$
_$.=
____
-
___.*
-1
__

_.*
0

Попробуйте онлайн! Объяснение:

.+
*

Преобразовать в одинарный.

r`(____)*$
_$.=

Преобразовать обратно в десятичную, но оставить n%4+1подчеркивания.

____
-

В случае, если это 4, то результат -n.

___.*
-1

Случай 3: -1

__

Случай 2: n

_.*
0

Дело 1: 0

Нил
источник
1

APL (Dyalog Classic) , 22 12 байт

Массивные 10 байтов сохранены благодаря замечаниям Эрика Аутгольфера. Спасибо!

4∘|⊃0,⊢,¯1,-

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

Выводит n-е число

Я не знаю APL, я просто пытался заставить мой J-порт решения Арно работать в Dyalog APL.

Гален Иванов
источник
2
Хорошая попытка! Несколько замечаний: 1) Вы можете заменить (0,⍵,¯1,-⍵)на (0⍵¯1,-⍵). 2) Вы можете удалить 1+, предполагая, что ⎕IOсистемная переменная назначена 0(да, это разрешено). 3) Обычно мы не учитываем f←роль при отправке функций. 4) Вы можете использовать ⊃функцию вместо []индексации. Все вместе они формируют это: ⎕IO←0(не {(4|⍵)⊃0⍵¯1,-⍵}
считайте
@ Эрик Outgolfer Спасибо!
Гален Иванов
2
Более продвинутая игра в гольф на основе этого подхода: 4∘|⊃0,⊢,¯1,-.
Эрик Outgolfer
1
@ Эрик Outgolfer - Да, действительно! Я думаю 4∘|⊃0,⊢,¯1,- , что именно так 4&|{0,],_1,-будет выглядеть мое решение J в APL. Еще раз спасибо!
Гален Иванов
1
На самом деле J - это вариант APL, хотя и более отдаленный, чем другие, более похожие на APL, такие как Dyalog и NARS2000.
Эрик Outgolfer
1

Cubix , 20 19 байтов

Iun:^>s1ns:u@Ota3s0

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

Порты аналогичны подходу к cubix.

На кубе:

    I u
    n :
^ > s 1 n s : u
@ O t a 3 s 0 .
    . .
    . .

Первый бит ^Iu:n>s1ns:u0sсоздает стек, а затем 3atкопирует соответствующий элемент в TOS, затем Oвыводит и @завершает программу.

Giuseppe
источник
0

Пробел, 84 83 байта

[S S S N
_Push_0][S N
S _Duplicate_0][T   T   S _Store][S S S T   S N
_Push_2][S S T  T   N
_Push_-1][T T   S _Store][S S S T   N
_Push_1][S N
S _Duplicate_1][T   N
T   T   _Read_STDIN_as_integer][S S S T T   N
_Push_3][S S S T    N
_Push_1][T  T   T   ][S S T T   N
_Push_-1][T S S N
_Multiply][T    T   S _Store][T T   T   _Retrieve_input][S S S T    S S N
_Push_4][T  S T T   _Modulo][T  T   T   _Retrieve_result][T N
S T _Print_as_integer]

Буквы S(пробел), T(табуляция) и N(новая строка) добавляются только как подсветка.
[..._some_action]добавлено только в качестве объяснения.

Попробуйте онлайн (только с пробелами, вкладками и новыми строками).

Порт ответа @Arnauld на JavaScript .

Пояснение (пример ввода n=7):

Command   Explanation         Stack        Heap                  STDIN   STDOUT   STDERR

SSSN      Push 0              [0]
SNS       Duplicate top (0)   [0,0]
TTS       Store               []           {0:0}
SSSTSN    Push 2              [2]          {0:0}
SSTTN     Push -1             [2,-1]       {0:0}
TTS       Store               []           {0:0,2:-1}
SSSTN     Push 1              [1]          {0:0,2:-1}
SNS       Duplicate top (1)   [1,1]        {0:0,2:-1}
TNTT      Read STDIN as nr    [1]          {0:0,1:7,2:-1}        7
SSSTTN    Push 3              [1,3]        {0:0,1:7,2:-1}
SSSTN     Push 1              [1,3,1]      {0:0,1:7,2:-1}
TTT       Retrieve input      [1,3,7]      {0:0,1:7,2:-1}
SSTTN     Push -1             [1,3,7,-1]   {0:0,1:7,2:-1}
TSSN      Multiply (-1*7)     [1,3,-7]     {0:0,1:7,2:-1}
TTS       Store               [1]          {0:0,1:7,2:-1,3:-7}
TTT       Retrieve input      [7]          {0:0,1:7,2:-1,3:-7}
SSSTSSN   Push 4              [7,4]        {0:0,1:7,2:-1,3:-7}
TSST      Modulo (7%4)        [3]          {0:0,1:7,2:-1,3:-7}
TTT       Retrieve            [-7]         {0:0,1:7,2:-1,3:-7}
TNST      Print as integer    []           {0:0,1:7,2:-1,3:-7}           -7
                                                                                  error

Останавливается с ошибкой: выход не определен.

Кевин Круйссен
источник