Biorąc pod uwagę liczbę całkowitą i funkcję czarnej skrzynki, znajdź stały punkt w sekwencji zdefiniowanej przez .x1 f: ℤ → ℤfxk+1 := f(xk)

Detale

• xMówi się, że wartość jest stałym punktem fif x = f(x).

  Na przykład, jeśli f(x) := round(x/pi)mamy punkt początkowy , otrzymujemy wtedy , a następnie , co oznacza, że ​​przesłanie powinno wrócić .x1 = 10x2 = f(x1) = f(10) = 3x3 = f(x2) = f(3) = 1x4 = f(x3) = f(1) = 0x5 = f(x4) = f(0) = 00

• Możesz założyć, że wygenerowana sekwencja faktycznie zawiera stały punkt.
• Możesz użyć rodzimego typu dla liczb całkowitych zamiast ℤ.
• Możesz użyć dowolnego języka, dla którego istnieją domyślne ustawienia funkcji czarnej skrzynki wprowadzane w standardowym wpisie meta we / wy . Jeśli nie ma takich domyślnych ustawień dla twojego języka, możesz dodać jeden w sensie definicji funkcji czarnej skrzynki i upewnij się, że łączysz swoje propozycje w tej definicji. Nie zapomnij także głosować na nich.

Przykłady

f(x) = floor(sqrt(abs(x)))
0 -> 0,  all other numbers -> 1

f(x) = c(c(c(x))) where c(x) = x/2 if x is even; 3*x+1 otherwise
all positive numbers should result in 1,2 or 4 (Collatz conjecture)

f(x) = -42
all numbers -> -42

f(x) = 2 - x
1 -> 1

Właściwie 1 bajt

Y

Wypróbuj online!

Yjest funkcją punktu stałego w rzeczywistości. W przykładzie TIO funkcja pokazana jest jako ciąg i £służy do przekształcenia jej w funkcję na stosie. Możliwe jest również, aby po prostu wcisnąć funkcję stosie jak tak . Są to jedyne dwa sposoby uzyskania wejścia funkcji w rzeczywistości.

APL (Dyalog) , 2 bajty

⍣=

Wypróbuj online!

NB: Definiuję O←⍣=w sekcji wprowadzania z powodu błędu w tym, że pochodnych operatorów monadycznych nie można zdefiniować w sposób, w jaki TIO lubi definiować rzeczy.

⍣ Jest operatorem, z którego można korzystać jak (function⍣condition) ⍵

To zastosowanie function, fdo ⍵momentu (f ⍵) condition ⍵zwrotu prawdziwe.

⍣=jest pochodnym operatorem monadycznym, który przyjmuje funkcję monadyczną fjako lewy argument i stosuje ją do prawego argumentu ⍵, dopókif ⍵ = ⍵

Haskell, 17 bajtów

until=<<((==)=<<)

Wypróbuj online!

MATLAB , 41 bajtów

function x=g(f,x);while f(x)-x;x=f(x);end

Jest też to piękno, które nie potrzebuje plików funkcyjnych. Niestety jest trochę dłużej:

i=@(p,c)c{2-p}();g=@(g,f,x)i(f(x)==x,{@()x,@()g(g,f,f(x))});q=@(f,x)g(g,f,x)

Wypróbuj online!

Standardowy ML (MLton) , 30 bajtów

fun& $g=if$ =g$then$else&(g$)g

Wypróbuj online! Użyj jako & n blackbox.

Funkcje czarnej skrzynki są zdefiniowane następująco:

fun blackbox1 x = floor(Math.sqrt(Real.fromInt(abs x)))

fun blackbox2 x = c(c(c(x))) 
and c x = if x mod 2 = 0 then x div 2 else 3*x+1

fun blackbox3 _ = ~42

fun blackbox4 x = 2-x

Wersja bez golfa:

fun fixpoint n g = if n = g n then n else fixpoint (g n) g

R , 36 35 bajtów

dzięki JayCe za grę w golfa

function(f,x){while(x-(x=f(x)))0;x}

Wypróbuj online!

Sprawdź przykładowe funkcje!

Port R rozwiązania Flawr.

Mathematica, 11 bajtów

#2//.x_:>#&

Wypróbuj online!

Mathematica, 10 bajtów

FixedPoint

Wypróbuj online!

Python 2 , 39 37 33 bajtów

dzięki @ Mr.Xcoder za -2 bajty

s=lambda k:s(f(k))if k-f(k)else k

Wypróbuj online!

zakłada, że ​​funkcja czarnej skrzynki ma być nazwana f

JavaScript (Node.js) , 25 22 21 bajtów

dziękuję Hermanowi Lauensteinowi za pokazanie mi tego konsensusu
dzięki @ l4m2 za -1 bajt

Przyjmuje nazwę funkcji czarnej skrzynki f.

g=k=>f(k)-k?g(f(k)):k

Wypróbuj online!

Galaretka , 3 bajty

vÐL

Wypróbuj online!

Bierze lewy argument jako ciąg znaków reprezentujący odsyłacz Jelly ( 2_na przykład), a prawy argument jako liczbę całkowitą

Jak to działa

 ÐL - While the output is unique...
v   -   Evaluate the function with the argument given

Brain-Flak , 24 bajty

(()){{}(({})<>[({})])}{}

Wypróbuj online!

(dla funkcji czarnej skrzynki x -> 2-xw poniższym przykładzie)

Dostarczoną funkcją czarnej skrzynki powinien być program, który podany xna górze stosu, pop xi push f(x)- innymi słowy, powinien oceniać funkcję fna wartości na górze stosu.

Odpowiednik Mini-Flak to 26 bajtów (dzięki Kreatorowi pszenicy za oszczędność 2 bajtów):

(()){{}(({})( )[{}({})])}{}
             ^ put the function f here

(nie licząc komentarzy i spacji)

Weź funkcję (wewnątrz <>) i liczbę z wejścia. (zauważ, że Brain-Flak jest językiem ezoterycznym i nie może przyjmować argumentów funkcjonalnych jako danych wejściowych)x0

Przykładowe funkcje czarnej skrzynki:

x -> 2-x: Wypróbuj online!

Wyjaśnienie:

(()){{}(({})<f>[({})])}{}   Main program.
                            Implicit input from stdin to stack.
(  )                        Push
 ()                         literal number 1.
                            Now the content of the stack: [1, x0]
    {                 }     While stack top ≠ 0:
                            current stack content: [something ≠ 0, x]
     {}                       Pop stack top (something). stack = [x]
       (             )        Push
        ({})                    Stack top = x. Current stack = [x]
             f                  Evaluate f. Current stack = [f(x)]
            < >                   (suppress the value of f(x), avoid adding it)
               [    ]           plus the negative of
                ({})            the top of the stack ( = -f(x) )
                              In conclusion, this change (x) on the stack to
                              (f(x)), and then push (x + -f(x))
                            If it's 0, break loop, else continue.
                       {}   Pop the redundant 0 on the top.
                            Implicit output stack value to stdout.

Szybki , 47 42 bajtów

func h(_ n:Int){f(n)==n ?print(n):h(f(n))}

Naiwne podejście zakłada, że funkcja czarnej skrzynki jest nazwana f

C (gcc) , 40 bajtów

f(n,b)int(*b)(_);{n=n^b(n)?f(b(n),b):n;}

Wypróbuj online! Zauważ, że flagi nie są konieczne, służą one pomocą w testowaniu funkcji punktu stałego zdefiniowanej powyżej.

Jest to funkcja, która pobiera int ni wskaźnik funkcji b : int → int. Nadużywanie faktu, że zapis do pierwszego argumentu zmiennej ustawia eaxrejestr, co jest równoważne zwracaniu ^† . W przeciwnym razie jest to dość standardowy, jeśli chodzi o C golf. n^b(n)sprawdza nierówność ni stosuje się do czarnej skrzynki n. Gdy jest nierówny, wywołuje funkcję punktu stałegof rekurencyjnie z argumentami aplikacji i czarnej skrzynki. W przeciwnym razie zwraca punkt stały.

^{† Potrzebne cytowanie, niejasno pamiętam gdzieś to przeczytałem, a Google wydaje się potwierdzać moje podejrzenia}

Deklaruje dane wejściowe za pomocą typowania parametrów w stylu K&R:

f(n, b)
int(*b)(_);
{
    n=n^b(n)?f(b(n),b):n;
}

Tajemny bit w drugim wierszu powyżej deklaruje, bże jest wskaźnikiem funkcji, który przyjmuje parametr liczby całkowitej - przyjmuje się, że domyślnym typem _jest liczba całkowita. Podobnie nzakłada się, że jest liczbą całkowitą i fprzyjmuje się, że zwraca liczbę całkowitą. Brawo dla niejawnego pisania?

Czysty , 46 bajtów

import StdEnv
p x=hd[n\\n<-iterate f x|f n==n]

Zakłada, że ​​funkcja jest zdefiniowana jako f :: !Int -> Int

Zajmuje on czoło nieskończonej listy aplikacji f f f ... x filtrowanych dla tych elementów, w których f el == el.

Wypróbuj online!

Jeśli chcesz zmienić funkcję w TIO, składnia lambda Clean'a to:

\argument = expression

(w rzeczywistości jest to o wiele bardziej skomplikowane, ale na szczęście potrzebujemy tylko jednoargumentowych funkcji)

APL (Dyalog Unicode) , 14 bajtów

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}

Wypróbuj online!

Funkcja w nagłówku jest równoważna z f(x) = floor(sqrt(abs(x)))

Dzięki @ Adám za zwrócenie uwagi, że pierwotna odpowiedź była nieprawidłowa zgodnie z konsensusem PPCG.

Jak to działa:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} ⍝ Main 'function' (this is actually an operator)
      :         ⍝ if
 ⍵=⍺⍺⍵          ⍝ the right argument (⍵) = the left function (⍺⍺, which is f) of ⍵
       ⍵        ⍝ return ⍵
        ⋄       ⍝ else
         ∇⍺⍺⍵   ⍝ return this function (∇) with argument f(⍵)

Oktawa , 37 bajtów

function x=g(f,x);while x-(x=f(x))end

Wypróbuj online!

Oktawa ma przypisanie wbudowane, ale MATLAB nie, więc jest to golfowy port rozwiązania flawr .

To także porty ładnie do R .

Kotlin , 50 bajtów

{f,k->var a=k;var b=a+1;while(b!=a){b=a;a=f(a)};a}

Wypróbuj online!

Czwarty (gforth), 36 bajtów

Ta wersja zakłada, że fjest predefiniowana. To nie jest tak fajne, jak rozwiązanie poniżej. Oba programy wychodzą z przepełnieniem stosu, jeśli nie został znaleziony, lub niedopełnieniem stosu, jeśli został znaleziony (po wydrukowaniu wyniku).

Wypróbuj online

: g dup f over = IF . THEN recurse ;

Dalej (gforth), 52 bajty

Pozwala to na przekazanie tokena wykonania funkcji jako parametru i jest zdecydowanie lepszym rozwiązaniem.

: g 2dup execute rot over = IF . THEN swap recurse ;

Wypróbuj online

Wyjaśnienie:

: g             \ x1 f          Define g. Params on the stack. f is on top
2dup execute    \ x1 f x2       duplicate both params, execute f(x1)
rot over        \ f x2 x1 x2    move x1 to top and copy x2 to top
= IF . THEN                     compare, if equal, print
swap recurse ;                  otherwise, recurse

Rubin , 31 28 bajtów

->x,f{x=f[x]until x==f[x];x}

Wypróbuj online!

tinylisp repl, 28 bajtów

(d P(q((x)(i(e(f x)x)x(P(f x

Zakłada, że ​​funkcja fjest predefiniowana.

Wypróbuj online!(Przykładowa funkcja to f(x) = (x*2) mod 10.)

Bez golfa

(load library)
(def P
 (lambda (x)
  (if (equal? (f x) x)
   x
   (P (f x)))))

Jeśli f(x)jest równy x, to xjest punktem stałym; zwróc to. W przeciwnym razie rekurencyjnie szukaj stałego punktu zaczynając od f(x)zamiast x.

APL NARS 65 znaków

r←(f v)n;c
   c←0⋄→B
E: r←∞⋄→0
A: n←r
B: r←f n⋄c+←1⋄→E×⍳c>1e3⋄→A×⍳r≠n

Operator v zwróciłby error (lub ewentualnie -oo lub Nan) za błąd, w przeciwnym razie jedna wartość x z x = f (x). W teście f = floor (sqrt (abs (x))), f1 = 2-x, f2 = c (c (c (x))) przy c = x% 2 == 0? X / 2: 3 * x +1

  f←⌊∘√∘|
  f v 0
0
  f v 9
1
  f1←{2-⍵}
  f1 v 1
1
  f1 v ¯10
∞
  f1 v 2
∞
  c1←{0=2∣⍵:⍵÷2⋄1+3×⍵}
  f2←c1∘c1∘c1
  f2 v 1
1
  f2 v 2
2
  f2 v 7
2
  f2 v 82
4

Clojure, 45 43 bajtów

To jest najkrótszy i najbrzydszy:

#(loop[a + b %2](if(= a b)a(recur b(% b))))

+jest tam zamiast liczby, więc nie jest równa żadnej wartości x0.

55 bajtów i funkcjonalne:

#(reduce(fn[a b](if(= a b)(reduced a)b))(iterate % %2))

Przykład:

(def f #(...))
(defn collaz [x] (if (even? x) (-> x (/ 2)) (-> x (* 3) (+ 1))))
(f (->> collaz (repeat 3) (apply comp)) 125)
; 1

x86 opcode, 8 bajtów

fun:
        call    edx          ; 2B
        cmpxchg eax,    ecx  ; 3B, on 8086 use xchg and cmp instead
        jnz     fun          ; 2B
        ret                  ; 1B

Zapisz dane wejściowe: ecx(wartość ), (adres funkcji, pobierz dane wejściowe , zapisz wynik bez modyfikowania wartości ix0edxecxeaxecxedx )

8086 opcode, 7 bajtów (ale wolno)

    xor     cx,     cx
    call    dx
    loop    $-2
    ret

Jeśli istnieje punkt stały, zapętlenie 65536 razy zawsze prowadzi go tam.
Weź dane wejściowe: ax(wartość początkowa ), (adres funkcji, pobierz dane wejściowe , zapisz dane wyjściowe bez modyfikowania wartości i ). Wypisuje stały punkt w rejestrze .x0dxaxaxcxdx
ax

Perl 5, 18 + 1 ( -p)

$_=f$_ while$_^f$_

spróbuj online

Java 8, 42 bajty

To wymaga Function<Integer, Integer>lub IntFunction<Integer>i intlub Integer(zmiękczana) i zwraca do stałego punktu.

f->i->{while(i!=(i=f.apply(i)));return i;}

Wypróbuj online

Wykorzystuje fakt, że Java ocenia podwyrażenia od lewej do prawej (więc stary ijest porównywany z nowym), właściwość, o której nie wiedziałem pisząc to!