Definicja

• a(0) = 0
• a(n) = n-a(a(a(n-1))) dla liczby całkowitej n > 0

Zadanie

Biorąc pod uwagę nieujemną liczbę całkowitą n, wyjście a(n).

Przypadki testowe

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

Bibliografia

• WolframMathWorld
• OEIS A005374

Haskell, 23 22 bajtów

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

Po prostu używa definicji sekwencji. f(f$f$n-1)jest równoważne z f (f (f (n-1))).

Test:

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]

Dzięki Andersowi Kaseorgowi za bajt!

Galaretka , 8 bajtów

’ßßßạµṠ¡

Wypróbuj online! lub zweryfikuj mniejsze przypadki testowe .

Jak to działa

’ßßßạµṠ¡  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.

Mathematica, 20 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1 (lub zgodne) i $CharacterEncodingustawia pasującą wartość, na przykład wartość domyślną systemu Windows WindowsANSI.

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

To definiuje jednoargumentowy operator ±.

JOT, 14 12 bajtów

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

Zaoszczędzono 2 bajty dzięki @ Leaky Nun .

Oblicza wynik, wywołując się rekurencyjnie, gdy n > 0 trzy razy na n -1 i odejmując wynik od n . Inna sytuacja występuje w przypadku podstawowym, gdy n = 0. Tam oblicza n - n, co jest równe 0.

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

Wypróbuj tutaj.

Wyjaśnienie

-$:^: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

Julia, 16 bajtów

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

Wypróbuj online!

Jak to działa

Przedefiniowujemy jednoargumentowego operatora ! do naszych celów.

Jeśli n = 0 , porównanie n>0zwraca false i tak też jest! .

W przeciwnym razie kod po &&zostanie wykonany. ~-njest równoważne (n-1)uzupełnieniu do dwóch, !!!rekurencyjnie wywołuje !trzykrotnie n - 1 , a wynikową wartość odejmuje się od n .

Python, 31 bajtów

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

Limit rekurencji i ograniczenia czasowe sprawiają, że powyższa funkcja jest niepraktyczna, ale teoretycznie powinna działać (i działa na małe n).

JavaScript (ES6), 52 bajty

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

Mogłem się nudzić i napisać wersję rekurencyjną, ale ta wersja jest znacznie szybsza (łatwo radzi sobie z ostatnim testem) i również używa, reducewięc to plus!

Siatkówka , 49 43 bajtów

.+
$*1:
{`^1(1*):
$1:::-1$1
}`^:*(1*)-\1

1

Wypróbuj online!

CJam, 13 12 bajtów

Dzięki Dennisowi za zaoszczędzenie 1 bajtu.

ri0{_(jjj-}j

Sprawdź to tutaj.

R 42 41 bajtów

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

Stosowanie:

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

To podejście rekurencyjne nie daje się dobrze skalować w przypadku większych wartości n.

Oaza , 6 bajtów

Kod:

nbaa-0

Wersja rozszerzona:

a(n) = nbaa-
a(0) = 0

Kod:

n      # Push n
 b     # Calculate a(n - 1)
  a    # Calculate a(a(n - 1))
   a   # Calculate a(a(a(n - 1)))
    -  # Subtract a(a(a(n - 1))) from n

Wypróbuj online!

Sesos , 58 55 bajtów

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..

Obsługuje dane wejściowe do 400Dobrze radzi , ale po tym czasie czas działania znacznie wzrasta.

Wypróbuj online! Sprawdź debugowanie opcję aby zobaczyć wygenerowany kod SBIN.

Montaż Sesos

Powyższy plik binarny został wygenerowany przez skompletowanie następującego kodu 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

LISP, 61 bajtów

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

Prawdopodobnie nie jest to optymalne rozwiązanie, ale działa.

Java 7, 42 bajty

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

Przypadki bez golfa i testy:

Wypróbuj tutaj.

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

Wynik:

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..)

Rubinowy, 27 bajtów

Oczywista implementacja.

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

Jest to dłuższa, szybsza odpowiedź, która buforuje poprzednie wpisy w sekwencji. Obie odpowiedzi działają tylko w wersjach po wersji 1.9, ponieważ wtedy ->Ruby wprowadziła mocną lambdę.

->n{r=[0];i=0;(i+=1;r<<i-r[r[r[i-1]]])while i<n;r[n]}

C #, 35 bajtów

int a(int n)=>n>0?n-a(a(a(n-1))):0;

Golfscript, 26 25 bajtów

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

Wypróbuj online!

Lokalnie 10000zajmuje mniej niż pół sekundy.

DO, 35 32 bajty

Zaoszczędź 3 bajty dzięki @PeterTaylor!

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

Wypróbuj na Ideone!

JavaScript ES6, 22 bajty

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

Będę się nudzić i wykonam wersję rekurencyjną: P

VBA, 69 bajtów

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

Działa w mgnieniu oka na zestawie testowym, zwalnia nieco powyżej n = 1000000, wpada w ścianę pamięci nieco powyżej n = 25 milionów.

Pyth, 10 bajtów

L-WbbyFtb3

Definiuje funkcję y. Wypróbuj online: demonstracja

Używa to względnie nowej funkcji Pytha. Możesz zastosować funkcję wiele razy, używając składni. W rzeczywistości nie oszczędza żadnych bajtów, użyłem go tylko do celów demonstracyjnych.

Wyjaśnienie:

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

Klon, 28 26 bajtów

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

Stosowanie:

> 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

dc, 34 bajty

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

Dane wejściowe są pobierane z góry stosu. To musi być jedyny element na stosie, ponieważ głębokość stosu jest używana jako licznik. Przykład użycia:

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

Jest to dość prosta implementacja definicji sekwencji:

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)

W każdym razie zaczęło się to od razu ... potem grało się w golfa.

Common Lisp , 44 bajty

(defun f(x)(if(= x 0)0(- x(f(f(f(1- x)))))))

Wypróbuj online!

C ++ (głównie MSVC)

Wersja normalna: 40 bajtów

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

Wersja meta programowania szablonu: 130 bajtów

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

Stosowanie :

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

Wersja szablonu jest najszybszym kodem, ponieważ nie ma nic szybszego niż przeniesienie wartości do rejestru => z optymalizacją, H<20>::a()kompiluj jako:

mov esi, 14

W przypadku wersji 10000 wersja rekurencyjna ulega awarii z powodu błędu przepełnienia stosu, a wersja szablonu ulega awarii podczas kompilacji z powodu głębokości tworzenia szablonów. GCC idzie do 900 (614)

D , 36 bajtów

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

Wypróbuj online!

APL (Dyalog Unicode) , 18 17 bajtów

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

Wypróbuj online!

O dziwo, nie ma odpowiedzi APL na to wyzwanie. Jest to dosłowna implementacja funkcji w PO.

Upłynął limit czasu TIO $n>90$.

Zapisano bajt dzięki @ Zacharý.

Python 3, 72 bajty

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

Ideone to!

PowerShell v2 +, 56 bajtów

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

Ekwiwalent PowerShell dla lambda w celu utworzenia definicji rekurencyjnej. Wykonaj go za pośrednictwem &operatora połączenia, np &$a(5). Trwa długo czasu - nawet50 na moim komputerze (najnowszy i5 z 8 GB pamięci RAM) zajmuje około 90 sekund.

Szybsze rozwiązanie iteracyjne, 59 bajtów

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

Dłuższy tylko dlatego, że musimy uwzględnić dane wejściowe 0(to *!!$nkoniec). W przeciwnym razie po prostu iteracyjnie konstruujemy tablicę $n, dodając za każdym razem nowy element, i wypisujemy ostatni na końcu $o[-1]. Superszybki - obliczenia 10000na moim komputerze trwają około 5 sekund.

> <> , 55 + 2 = 57 bajtów

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

Dane wejściowe powinny być obecne na stosie przy starcie programu, więc +2 bajty dla -vflagi. Wypróbuj online!

Jest to hecka wolna, ponieważ wykorzystuje rekurencję do obliczenia wyniku. Korzystanie z TIO h(50)zajmuje ponad minutę. Zwraca prawidłowe wyniki <= 30, więc jestem pewien, że to zadziała h(10000), po prostu nie uruchomiłem go, aby się dowiedzieć!