H-последовательность Хофштадтера

15

Определение

  • a(0) = 0
  • a(n) = n-a(a(a(n-1))) для целого числа n > 0

задача

Учитывая неотрицательное целое число n, выведите a(n).

Testcases

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

Ссылки

Дрянная Монахиня
источник
Связанные проблемы о последовательностях Хофштадтера: 1 , 2 , 3
Мартин Эндер
4
И я все еще думаю, что вы должны ссылаться на GEB ...
Мартин Эндер
1
Насколько здесь актуальна теория чисел ?
Flawr
1
@flawr facepalm Позвольте мне попробовать это снова: Гедель, Эшер, Бах: вечная золотая коса
Стиг Хеммер
1
@StigHemmer На самом деле у facepalm теперь есть свои Emoji: To
Тобиас Кинцлер

Ответы:

20

Haskell, 23 22 байта

f 0=0
f n=n-f(f$f$n-1)

Просто использует определение последовательности. f(f$f$n-1)эквивалентно f (f (f (n-1))).

Тестовое задание:

main = putStrLn . show $ map f [0..20]
-- => [0,1,1,2,3,4,4,5,5,6,7,7,8,9,10,10,11,12,13,13,14]

Спасибо Anders Kaseorg за байт!

Дверная ручка
источник
(f$f$f$n-1)= f(f$f$n-1)сохраняет байт.
Андерс Касеорг
9

Желе , 8 байт

’ßßßạµṠ¡

Попробуйте онлайн! или проверьте меньшие контрольные примеры .

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

’ßßßạµṠ¡  Main link. Argument: n

     µṠ¡  Execute the preceding chain sign(n) times.
’         Decrement n, yielding n - 1.
 ßßß      Recursively call the main link thrice.
    ạ     Take the absolute difference of n and the result.
Деннис
источник
9
Может ли анализатор Jelly обрабатывать программы размером более 10 байт?
Стинберг
9

Mathematica, 20 байтов

Число байтов предполагает кодирование ISO 8859-1 (или совместимое) и $CharacterEncoding устанавливает соответствующее значение, как в Windows по умолчанию WindowsANSI.

±0=0
±n_:=n-±±±(n-1)

Это определяет унарный оператор ±.

Мартин Эндер
источник
Не могли бы вы объяснить, что ± делает или как это работает? Кстати, поздравляю по 100к.
DavidC
1
@DavidC Спасибо. :) Это просто встроенный оператор, который является сокращением для неиспользуемой функции PlusMinus. Смотрите этот пост для деталей.
Мартин Эндер
1
Очень интересно. Обойтись без @или [ ]тоже.
DavidC
9

J, 14 12 байт

-$:^:3@<:^:*

Сохранено 2 байта благодаря @ Leaky Nun .

Вычисляет результат путем рекурсивного вызова самого себя, когда n > 0 три раза по n -1, и вычитания этого результата из n . Существует другая ситуация для базового случая, когда n = 0. Там он вычисляет n - n, что равно 0.

a(n) = n - n = 0           if n = 0
       n - a(a(a(n-1)))    if n > 0

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

объяснение

-$:^:3@<:^:*  Input: n
           *  Get the sign of n (n = 0 => 0, n > 0 => 1)
         ^:   Execute that many times
                (0 times means it will just be an identity function)
       <:       Decrement n
 $:             Call itself recursively
   ^:3          three times
      @         on n-1
-             Subtract that result from n and return
миль
источник
Я не думаю, что скобки нужны.
Утренняя монахиня
6

Юлия, 16 байт

!n=n>0&&n-!!!~-n

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

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

Мы переопределяем унарный оператор !для наших целей.

Если n = 0 , сравнение n>0возвращает ложь и так же !.

В противном случае код после &&выполняется. ~-nэквивалентно (n-1)дополнению до двух, !!!рекурсивно вызывает !трижды на n - 1 , и полученное значение вычитается из n .

Деннис
источник
Не могли бы вы добавить объяснение? Я понятия не имею, что происходит -!!~-.
Downgoat
1
Ничего фантастического. !это просто имя функции.
Деннис
5

Python, 31 байт

a=lambda n:n and n-a(a(a(n-1)))

Ограничение рекурсии и временные ограничения делают вышеупомянутую функцию непрактичной, но теоретически она должна работать (и работает для малых n).

orlp
источник
4

JavaScript (ES6), 52 байта

n=>[0,...Array(n)].reduce((p,_,i,a)=>a[i]=i-a[a[p]])

Я мог бы быть скучным и написать рекурсивную версию, но эта версия намного быстрее (легко справляется с последним тестовым примером), а также использует, reduceтак что это плюс!

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

CJam, 13 12 байт

Спасибо Деннису за сохранение 1 байта.

ri0{_(jjj-}j

Проверьте это здесь.

Мартин Эндер
источник
Это работает для удивительно высоких значений. Я думаю, что вам не нужно a.
Деннис
@ Денис О, это приятно знать, спасибо.
Мартин Эндер
3

Р, 42 42 байта

a=function(n)ifelse(n<1,0,n-a(a(a(n-1))))

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

> a(1)
1
> a(10)
7

Этот рекурсивный подход не подходит для больших значений n.

DSkoog
источник
Вы должны иметь возможность потерять байт (и ряд ошибок с ошибочными входами), если вы измените свое состояние на n<1. Поскольку это последовательность, она все равно действительно определена только для неотрицательных целых чисел.
user5957401
a=function(n)"if"(n,n-a(a(a(n-1))),0)будет работать на несколько байтов.
Джузеппе
2

Sesos , 58 55 байт

0000000: 16e0d7 bdcdf8 8cdf1b e6cfbb 840d3f bf659b 38e187  ..............?.e.8..
0000015: f8639b 39dc37 fc893f 666c05 7e7ed9 b88b3f ae0d3f  .c.9.7..?fl.~~...?..?
000002a: 676ed8 bd9940 7fdc3b 36619e f1                    gn...@..;6a..

Хорошо обрабатывает ввод до 400 , но после этого время выполнения значительно увеличивается.

Попробуйте онлайн! Проверьте Debug, чтобы увидеть сгенерированный код SBIN.

Сесос сборка

Бинарный файл выше был сгенерирован путем сборки следующего кода SASM.

set numin, set numout

get
jmp
    jmp
        rwd 3, add 1, rwd 1, add 1, fwd 4, sub 1
    jnz
    rwd 3, sub 1
jnz
rwd 3, add 1, fwd 2
jmp
    rwd 1, sub 1, fwd 3, sub 1, fwd 2, add 3
    jmp
        rwd 2
        jmp
            rwd 3
        jnz
        fwd 6, get, rwd 4, sub 1
        jmp
            fwd 1, sub 1
            jmp
                rwd 3
            jnz
            sub 1
            jmp
                fwd 3
            jnz
            rwd 4, sub 1
        jnz
        fwd 1
        jmp
            rwd 1, add 1, fwd 1, add 1
        jnz
        sub 1, fwd 3, sub 1
        jmp
            fwd 3
        jnz
        rwd 1, sub 1
    jnz
    rwd 2, get
    nop
        rwd 3
    jnz
    fwd 3, get, rwd 2
    jmp
        fwd 2, add 1
        jmp
            fwd 3
        jnz
        rwd 1, add 1, rwd 2
        jmp
            rwd 3
        jnz
        fwd 1, sub 1
    jnz
    fwd 2
    jmp
        rwd 2, add 1, fwd 2, sub 1
    jnz
    nop
        get, fwd 3
    jnz
    rwd 1, add 1, fwd 2
jnz
rwd 2, sub 1
jmp
    rwd 1, sub 1, fwd 1, sub 1
jnz
rwd 1, put
Деннис
источник
2

LISP, 61 байт

(defun H(N)(if(= N 0)(return-from H 0)(- N(H(H(H(- N 1)))))))

Вероятно, не оптимальное решение, но оно работает.

Эстет
источник
1

Java 7, 42 байта

int c(int n){return n>0?n-c(c(c(n-1))):0;}

Ungolfed и тестовые случаи:

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

class Main{
  static int c(int n){
    return n > 0
              ? n - c(c(c(n-1)))
              : 0;
  }

  public static void main(String[] a){
    for(int i = 0; i < 21; i++){
      System.out.println(i + ": " + c(i));
    }
    System.out.println("1000: " + c(1000));
  }
}

Выход:

0: 0
1: 1
2: 1
3: 2
4: 3
5: 4
6: 4
7: 5
8: 5
9: 6
10: 7
11: 7
12: 8
13: 9
14: 10
15: 10
16: 11
17: 12
18: 13
19: 13
20: 14
 (last case takes too long..)
Кевин Круйссен
источник
1

Рубин, 27 байт

Очевидная реализация.

a=->n{n<1?0:n-a[a[a[n-1]]]}

Это более длинный и быстрый ответ, который кэширует предыдущие записи в последовательности. Оба ответа работают только для версий после 1.9, как тогда ->, когда в Ruby была представлена ​​стабильная лямбда.

->n{r=[0];i=0;(i+=1;r<<i-r[r[r[i-1]]])while i<n;r[n]}
Sherlock9
источник
1

C #, 35 байт

int a(int n)=>n>0?n-a(a(a(n-1))):0;
TheLethalCoder
источник
1

Гольфскрипт, 26 25 байт

~ [0] {...., (=== \, @ - +.} @ *) \;
~ [0] {...) \; == \ @ - +.} @ *) \;

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

Локально 10000занимает не более полсекунды.

Дрянная Монахиня
источник
1

C, 35 32 байта

Сохранено 3 байта благодаря @PeterTaylor!

a(n){return n?n-a(a(a(n-1))):0;}

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

betseg
источник
2
В C вы можете использовать целое число непосредственно как условное, что дает трехбайтовую экономию:a(n){return n?n-a(a(a(n-1))):0;}
Питер Тейлор
1
@betseg - :в твоем коде тоже есть ошибки . Вы должны вынуть один после ?.
owacoder
1

Javascript ES6, 22 байта

a=n=>n&&n-a(a(a(n-1)))

Я буду скучным и сделаю рекурсивную версию: P

Mama Fun Roll
источник
1

VBA, 69 байт

Function H(N):ReDim G(N):For j=1To N:G(j)=j-G(G(G(j-1))):Next:H=G(N)

Работает в мгновение ока на тестовом наборе, замедляется чуть выше n = 1000000, наталкивается на стену памяти чуть выше n = 25 миллионов.

Joffan
источник
1

Pyth, 10 байт

L-WbbyFtb3

Определяет функцию y. Попробуйте онлайн: демонстрация

Это использует относительно новую особенность Pyth. Вы можете применить функцию несколько раз, используя сложный синтаксис. На самом деле он не сохраняет байты, я использовал его только для демонстрации.

Объяснение:

L-WbbyFtb3
L            define function y(b), that returns:
    b           b
 -Wb            and subtract the following if b>0
     yF  3      y applied three times to
       tb       b - 1
Jakube
источник
1

Клен, 28 26 байт

`if`(n=0,0,n-a(a(a(n-1))))

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

> a:=n->ifelse(n=0,0,n-a(a(a(n-1))));
> seq(a(i),i=0..10);
0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7
DSkoog
источник
1

постоянный ток, 34 байта

dsn[zdddd1-;a;a;a-r:aln!=L]dsLx;ap

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

$ dc
10000dsn[zdddd1-;a;a;a-r:aln!=L]dsLx;ap

Это довольно простая реализация определения последовательности:

dsn               # Store n as `n', and keep a copy as a depth buffer (see below)
[                 # Open loop definition
 z                # Push stack depth i for i-th term
 dddd             # Duplicate stack depth four times, for a total of five copies
 1-               # Get i-1 for use as index to previous term
                  #   Note that if we hadn't duplicated n above, or left something else
                  #   on the stack, 0-1 would be -1, which is not a valid array index
 ;a;a;a           # Fetch a(a(a(i-1)))
 -                # Calculate i-a(a(a(i-1)))
 r                # Arrange stack to store i-th term: TOS |  i  (i-a(a(a(i-1))))
 :a               # Store i-th term in array `a'
 ln!=L            # Load n. If n!=i, we're not done calculating terms yet, so execute loop
]                 # Close loop definition. Note that we started with five copies of i:
                  #   i-1 was used to get last term
                  #   i-a(...) was used to calculate current term
                  #   ... i :a was used to store current term
                  #   i ln !=L was used to check loop exit condition
                  # One copy of i is left on the stack to increment counter
dsLx              # Duplicate loop macro, store it, and execute copy
;a                # Last i stored on stack from loop will equal n, so use this to get a(n)
p                 # Print a(n)

Как бы то ни было, все началось просто ... а затем и игра в гольф.

Джо
источник
1

C ++ (MSVC, в основном)

Обычная версия: 40 байт

int a(int n){return n?n-a(a(a(n-1))):0;}

Версия метапрограммы шаблона: 130 байт

#define C {constexpr static int a(){return
template<int N>struct H C N-H<H<H<N-1>::a()>::a()>::a();}};template<>struct H<0>C 0;}};

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

std::cout << a(20) << '\n';       // Normal version
std::cout << H<20>::a() << '\n';  // Template version

Версия шаблона - самый быстрый код, так как нет ничего быстрее, чем переместить значение в регистр => с оптимизацией, H<20>::a()скомпилировать как:

mov esi, 14

Для 10000 рекурсивная версия падает из-за ошибки переполнения стека, а версия шаблона падает во время компиляции из-за глубины создания шаблона. GCC идет до 900 (614)

HatsuPointerKun
источник
Я думаю, вам не нужно пространство между Cи {в шаблонной версии
метапрограммирования
@ Zacharý MSVC отказывается компилировать без этого места
HatsuPointerKun
Ааа, теперь я понимаю, почему это, кажется, продолжает происходить
Захари
@ Zacharý Это зависит от типа макроса. Если у него есть параметры, то я могу удалить пробел, но здесь это не так
HatsuPointerKun
1

APL (Dyalog Unicode) , 18 17 байт

{⍵=0:0⋄⍵-∇⍣3⊢⍵-1}

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

Удивительно, но нет ответа APL на этот вызов. Это буквальная реализация функции в ОП.

Тайм-аут для TIO N>90,

Сохраненный байт благодаря @ Zacharý.

Ж. Салле
источник
1
{⍵=0:0⋄⍵-∇⍣3⊢⍵-1}
Захари
0

Python 3, 72 байта

def f(n):
    a=[0];i=0
    while n:i+=1;a+=[i-a[a[a[i-i]]]];n-=1
    return a[i]

Идео это!

Дрянная Монахиня
источник
0

PowerShell v2 +, 56 байт

$a={$n=$args[0];if($n){$n-(&$a(&$a(&$a($n-1))))}else{0}}

PowerShell эквивалент лямбды для формирования рекурсивного определения. Выполните его через &оператор вызова, например &$a(5). Выполнение занимает много времени - даже 50на моей машине (последняя версия i5 с 8 ГБ ОЗУ) занимает около 90 секунд.

Более быстрое итеративное решение, 59 байт

param($n)$o=,0;1..$n|%{$o+=$_-$o[$o[$o[$_-1]]]};$o[-1]*!!$n

Дольше только потому, что нам нужно учитывать вход 0 (это *!!$nв конце). В противном случае мы просто итеративно создаем массив до $n, добавляя новый элемент каждый раз, и выводим последний в конце $o[-1]. Суперскоростной - расчет 10000на моей машине занимает около 5 секунд.

AdmBorkBork
источник
0

> <> , 55 + 2 = 57 байт

^~n;
.~-]{:0$
v>1-}32[
v/  /:1-32[
>$:?/$~]{:0$.
/30@2[

Ожидается, что входные данные будут присутствовать в стеке при запуске программы, поэтому +2 байта для -v флага. Попробуйте онлайн!

Это очень медленно, так как он использует рекурсию для вычисления результата. Использование TIO h(50)занимает больше минуты. Он возвращает правильные результаты <= 30, так что я уверен, что это сработает h(10000), я просто не запустил его, чтобы узнать!

Sok
источник