Bei einer gegebenen Ganzzahl und einer gewissen Black-Box-Funktion finden Sie einen festen Punkt in der durch definierten Reihenfolge .x1 f: ℤ → ℤfxk+1 := f(xk)

Einzelheiten

• Ein Wert xist ein Fixpunkt von fif x = f(x).

  Zum Beispiel, wenn f(x) := round(x/pi)und wir einen Ausgangspunkt haben, dann bekommen wir , dann , dann und schließlich, was bedeutet, dass die Einreichung zurückkehren sollte .x1 = 10x2 = f(x1) = f(10) = 3x3 = f(x2) = f(3) = 1x4 = f(x3) = f(1) = 0x5 = f(x4) = f(0) = 00

• Sie können davon ausgehen, dass die generierte Sequenz tatsächlich einen festen Punkt enthält.
• Sie können den nativen Typ für Ganzzahlen anstelle von verwenden ℤ.
• Sie können jede Sprache verwenden, für die Standardeinstellungen für Black-Box-Funktionen in der Standard-E / A-Metapost eingegeben wurden . Wenn es für Ihre Sprache keine solche Standardeinstellung gibt, können Sie eine im Sinne der Definition von Black-Box-Funktionen hinzufügen und Ihre Vorschläge in dieser Definition verknüpfen. Vergiss auch nicht, darüber abzustimmen.

Beispiele

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

Eigentlich 1 Byte

Y

Probieren Sie es online!

Yist die Fixpunktfunktion in Tatsächlich. Im TIO-Beispiel wird die Funktion als Zeichenfolge dargestellt und £verwendet, um sie in eine Funktion auf dem Stapel umzuwandeln. Es ist auch möglich, die Funktion einfach so auf den Stack zu schieben . Dies sind die einzigen beiden Möglichkeiten, um eine Funktionseingabe in Actually zu erhalten.

APL (Dyalog) , 2 Bytes

⍣=

Probieren Sie es online!

NB: Ich definiere O←⍣=im Eingabeabschnitt, weil es einen Fehler gibt, dass abgeleitete monadische Operatoren nicht so definiert werden können, wie TIO es mag, Dinge zu definieren.

⍣ Ist ein Operator, der gerne verwendet werden kann (function⍣condition) ⍵

Es gilt das function, fauf ⍵bis (f ⍵) condition ⍵true zurück.

⍣=ist ein abgeleiteter monadischer Operator, der eine monadische Funktion fals linkes Argument übernimmt und auf das rechte Argument anwendet ⍵, bisf ⍵ = ⍵

Haskell, 17 Bytes

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

Probieren Sie es online!

MATLAB , 41 Bytes

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

Es gibt auch diese Schönheit , die keine Funktionsdateien benötigt. Leider ist es etwas länger:

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)

Probieren Sie es online!

Standard-ML (MLton) , 30 Bytes

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

Probieren Sie es online! Verwenden Sie als & n blackbox.

Die Black-Box-Funktionen sind wie folgt definiert:

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

Ungolfed-Version:

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

R , 36-35 Bytes

Vielen Dank an JayCe für das Abschlagen eines Bytes

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

Probieren Sie es online!

Überprüfen Sie die Beispielfunktionen!

R port der Lösung von flawr.

Mathematica, 11 Bytes

#2//.x_:>#&

Probieren Sie es online!

Mathematica, 10 Bytes

FixedPoint

Probieren Sie es online!

Python 2 , 39 37 33 Bytes

danke an @ Mr.Xcoder für -2 bytes

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

Probieren Sie es online!

nimmt an, dass die Black-Box-Funktion f heißt

JavaScript (Node.js) , 25 22 21 Bytes

Dank Herman Lauen für mich zeigt dieser Konsens
dank @ l4m2 für -1 Byte

Übernimmt die zu benennende Black-Box-Funktion f.

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

Probieren Sie es online!

Gelee , 3 Bytes

vÐL

Probieren Sie es online!

Nimmt das linke Argument als Zeichenfolge, die beispielsweise eine Jelly-Verknüpfung darstellt 2_, und das rechte Argument als Ganzzahl

Wie es funktioniert

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

Brain-Flak , 24 Bytes

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

Probieren Sie es online!

(für die Black-Box-Funktion x -> 2-xim folgenden Beispiel)

Die bereitgestellte Black-Box-Funktion sollte ein Programm sein, xdas oben auf dem Stapel angegeben ist, pop xund push f(x)- mit anderen Worten, es sollte die Funktion fauf den Wert oben auf dem Stapel auswerten .

Der äquivalente Mini-Flak-Wert beträgt 26 Byte (dank des Weizen-Assistenten zum Speichern von 2 Byte):

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

(ohne Kommentare und Leerzeichen)

Nimm die Funktion (innerhalb der <>) und eine Zahl aus der Eingabe. (Beachten Sie, dass Brain-Flak eine esoterische Sprache ist und kein funktionales Argument als Eingabe verwenden kann.)x0

Beispiel Blackbox-Funktionen:

x -> 2-x: Online ausprobieren!

Erläuterung:

(()){{}(({})<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.

Schnell , 47 42 Bytes

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

Naiver Ansatz, setzt voraus, dass die Black-Box-Funktion benannt ist f

C (gcc) , 40 Bytes

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

Probieren Sie es online! Beachten Sie, dass die Flags nicht erforderlich sind. Sie dienen dazu, die oben definierte Fixpoint-Funktion zu testen.

Dies ist eine Funktion, die einen int nund einen Funktionszeiger benötigt b : int → int. Wird die Tatsache missbraucht, dass das Schreiben in das erste Variablenargument das eaxRegister setzt, was der Rückgabe von ^{† entspricht} . Ansonsten ist dies ziemlich normal, was C-Golf angeht. n^b(n)prüft auf die Ungleichung von nund die Blackbox, auf die angewendet wird n. Bei Ungleichheit wird die Fixpoint-Funktion ferneut rekursiv mit der Anwendung und der Blackbox als Argumente aufgerufen . Andernfalls wird der Fixpunkt zurückgegeben.

^{† Zitat erforderlich, ich erinnere mich vage daran, dies irgendwo gelesen zu haben, und Google scheint meinen Verdacht zu bestätigen}

Es deklariert die Eingabe mit der Parametertypisierung nach K & R:

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

Das arkane Bit in der zweiten Zeile oben gibt an b, dass es sich um einen Funktionszeiger handelt, der einen ganzzahligen Parameter akzeptiert. Der Standardtyp von _wird als Ganzzahl angenommen. Ebenso nwird angenommen, dass es sich um eine Ganzzahl handelt, und es fwird angenommen, dass eine Ganzzahl zurückgegeben wird. Hurra für implizites Tippen?

Sauber , 46 Bytes

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

Angenommen, die Funktion ist definiert als f :: !Int -> Int

Es nimmt den Kopf der unendlichen Liste der Anwendungen von f f f ... xgefilterten für diejenigen Elemente, wo f el == el.

Probieren Sie es online!

Wenn Sie die Funktion im TIO ändern möchten, lautet die Lambda-Syntax von Clean:

\argument = expression

(Eigentlich ist es viel komplizierter, aber zum Glück brauchen wir nur unäre Funktionen)

APL (Dyalog Unicode) , 14 Byte

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

Probieren Sie es online!

Die Funktion am Header entspricht f(x) = floor(sqrt(abs(x)))

Vielen Dank an @ Adám für den Hinweis, dass die ursprüngliche Antwort laut PPCG-Konsens nicht gültig war.

Wie es funktioniert:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} ⍝ 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(⍵)

Oktave , 37 Bytes

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

Probieren Sie es online!

Octave verfügt über eine Inline-Zuweisung, MATLAB jedoch nicht. Dies ist eine Golf-Octave-Portierung der Lösung von flawr .

Es ist auch Häfen schön zu R .

Kotlin , 50 Bytes

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

Probieren Sie es online!

Forth (gforth), 36 Bytes

Diese Version setzt lediglich voraus, dass sie fvordefiniert ist. Es ist nicht so cool wie die Lösung darunter. Beide Programme werden mit einem Stapelüberlauf beendet, wenn sie nicht gefunden wurden, oder mit einem Stapelunterlauf, wenn sie gefunden wurden (nach dem Drucken des Ergebnisses).

Probieren Sie es online aus

: g dup f over = IF . THEN recurse ;

Viertens (gviertens), 52 Bytes

Dadurch kann das Ausführungstoken einer Funktion als Parameter übergeben werden und ist definitiv die bessere Lösung.

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

Probieren Sie es online aus

Erläuterung:

: 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

Ruby , 31 28 Bytes

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

Probieren Sie es online!

tinylisp repl, 28 bytes

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

Angenommen, die Funktion fist vordefiniert.

Probieren Sie es online! (Die Beispielfunktion ist f(x) = (x*2) mod 10.)

Ungolfed

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

Wenn f(x)gleich ist x, xist dies ein fester Punkt. Gib es zurück. Suchen Sie andernfalls rekursiv nach einem festen Punkt, der von f(x)anstatt von beginnt x.

APL NARS 65 Zeichen

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

v Der Operator würde ∞ (oder möglicherweise -oo oder Nan) als Fehler zurückgeben, andernfalls einen Wert x mit x = f (x). Im Test f = Boden (Quadrat (abs (x))) ist f1 = 2-x, f2 = c (c (c (x))) mit 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 Bytes

Nun, das ist die kürzeste und hässlichste:

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

+Gibt es anstelle einer Zahl, so dass sie keinem Wert von entspricht x0.

55 Bytes und funktional:

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

Beispiel:

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

x86-Opcode, 8 Bytes

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

Eingaben übernehmen: ecx(Wert ), (Funktionsadresse, Eingaben übernehmen von , Ergebnis schreiben an, ohne den Wert von und zu ändern )x0edxecxeaxecxedx

8086 Opcode, 7 Bytes (aber langsam)

    xor     cx,     cx
    call    dx
    loop    $-2
    ret

Wenn ein fester Punkt vorhanden ist, fahren Sie ihn immer 65536-mal in einer Schleife dorthin.
Eingaben übernehmen: ax(Anfangswert ), (Funktionsadresse, Eingabe von übernehmen , Ausgabe auf schreiben, ohne den Wert von und zu ändern ). Den Fixpunkt im Register ausgeben .x0dxaxaxcxdx
ax

Perl 5, 18 + 1 ( -p)

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

versuche es online

Java 8, 42 Bytes

Dies nimmt ein Function<Integer, Integer>oder IntFunction<Integer>und ein intoder Integer(Curry) und gibt den Fixpunkt zurück.

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

Probieren Sie es online

Nutzt die Tatsache aus, dass Java Unterausdrücke von links nach rechts auswertet (also wird der alte imit dem neuen verglichen), eine Eigenschaft, die mir beim Schreiben dieses Dokuments unbekannt war!