Znajdź punkt stały


24

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

Zauważ, że chociaż w szczegółach sugeruje się, że funkcja czarnej skrzynki zbiega się w ustalonym punkcie, ostatni przykład mówi inaczej
phflack

1
@phflack Blackbox musi zbiegać się tylko dla danych wejściowych.
flawr

Och, początkowo myślałem, że poddanie się nie otrzymało x_0, co spowodowało pewne zamieszanie. Pomyślałem, że rozwiązaniem powinno być (Jelly) ~Nƭ⁻Ç$¿, co jest jak (pseudo kod) for x in [0, -1, 1, -2, 2, -3, 3, -4, 4, ...]: if (x == f(x)): break; print(x); . To może być warte kolejnego wyzwania.
user202729,

1
Uwaga dla przyszłych gości: Znalezienie dowolnego stałego punktu nie działa, musisz znaleźć stały punkt osiągalny od x_0. Jest pewne, że istnieje.
user202729,

A jeśli nie istnieje punkt stały dla funkcji f i jednej wartości początkowej x0 ... Jaka powinna być wartość, którą musi zwrócić? A jeśli x0 = 0 if = int (9 / (x-1)) z dla x1 = x0 + 1 f (x1) = f (1) jest już jednym błędem ... Co powinno zwrócić operator dla tego f, x0?
RosLuP,

Odpowiedzi:


16

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.


7
Po prostu wiedziałeś, że któregoś dnia to wyzwanie zostanie opublikowane, prawda? : P
Erik the Outgolfer,

2
@EriktheOutgolfer Właściwie użyłem Ykilku wyzwań. Jestem najwyraźniej wyjątkowo wcześnie rozpoznany : P
Mego

11

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 ⍵ = ⍵


Być może należy zauważyć, że ⍣=jest pochodnym operatorem monadycznym, który przyjmuje funkcję jako lewy operand i znajduje punkt stałej na podanej wartości początkowej. Chciałbym skorzystać z inną literę na ⍣=niż f, jak to jest o perator, a nie f namaszczenie.
Adám

Tak. Ja bym. To mylące, że wywołujesz funkcję „wprowadzania” fw swoim opisie, ale następnie w TIO fjest operatorem rozwiązania. Możesz także przesunąć pole w O←⍣=górę w polu Kod, aby umożliwić policzenie i wskazać, że to jest rzeczywiste rozwiązanie, a reszta (dane wejściowe) po prostu go testuje.
Adám,

Wygląda mi na błąd. Porozmawiam jutro z odpowiednim kolegą.
Adám

@ Adám Zaktualizowano. Daj mi znać, jeśli błąd zostanie naprawiony
H.PWiz 12.12.17


9

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!


7
Ta odpowiedź była pomyślana jako przykład i nie uniemożliwia nikomu odpowiedzi.
flawr

Oczywiście, jeśli nazwiesz to Octave, możesz usunąć dwa ;s. Wypróbuj online! .
Sanchises

W swojej anonimowej funkcji możesz usunąć @()wcześniej xza 50 bajtów. Uznanie za sposób, w jaki zawijasz funkcję pomocnika ( g(g)na końcu), udało mi się zrobić tylko 51 bajtów @(g,x)(f=@(r,z){@()r(r,m),z}{(m=g(z)==z)+1}())(f,x). Zastanawiam się, czy istnieje jakakolwiek kombinacja obu podejść, która jest jeszcze krótsza.
Sanchises

6

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

1
Dobrze widzieć SML na wolności! Używamy go do naszych zajęć z programowania funkcjonalnego na naszej uczelni.
vijrox,



4

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


Czy funkcja nie musi być przekazywana jako parametr? Nie sądzę, aby wstępnie zdefiniowane zmienne były akceptowaną metodą wprowadzania.
mbomb007,

Nie jestem pewien, czy wolno ci zakładać, że funkcja jest taka f, czy nie jest to forma zakładania, że ​​dane wejściowe są w zmiennej? (edytuj: ninja'd autor: mbomb)
FlipTack,



4

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

4

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.


3

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


Mam wątpliwości co do twojej drugiej próby, ponieważ jest to złożone zamknięcie, a jego typ jest dwuznaczny, chyba że wyraźnie go rzucisz {...}as(<parameter types>)-><return type>. Jeśli nie określisz jego typu zwracania, spowoduje to wygenerowanie błędów podczas kompilacji, więc nie sądzę, aby był poprawny na chwilę obecną (zwróć uwagę, że rzutowanie musi być uwzględnione w liczbie bajtów). Twoje pierwsze zgłoszenie jest jednak w porządku.
Pan Xcoder,

2

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?


2

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)


2

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(⍵)

{⍵ = f⍵: ⍵⋄∇ (f⍵)} będzie w porządku dla oddzielnej funkcji anonimowej od jej nazwy (n)
RosLuP

2
Zakłada się, że fjest to wstępnie przypisane, co moim zdaniem jest zabronione przez konsensus PPCG. {⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}byłoby poprawnym rozwiązaniem dla operatora.
Adám



1

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


1

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.


1

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

1

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

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


Z pewnością pomogłoby to uczynić odpowiedź bardziej czytelną.
user202729,

więcej edycji, aby poprawić
l4m2


0

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!

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.