Найти фиксированную точку

24

Дано целое число и некоторая функция черного ящика найти фиксированную точку в последовательности, определенной .x1 f: ℤ → ℤfxk+1 := f(xk)

Детали

  • Значение xназывается фиксированной точкой fif x = f(x).

    Например , если f(x) := round(x/pi)и мы отправная точка , то мы получаем , то , то , и , наконец , это означает , что представление должно вернуться .x1 = 10x2 = f(x1) = f(10) = 3x3 = f(x2) = f(3) = 1x4 = f(x3) = f(1) = 0x5 = f(x4) = f(0) = 00

  • Вы можете предположить, что сгенерированная последовательность фактически содержит фиксированную точку.
  • Вы можете использовать нативный тип для целых чисел вместо .
  • Вы можете использовать любой язык, для которого есть значения по умолчанию для функций черного ящика, вводимых в стандартную метапост IO . Если для вашего языка нет такого значения по умолчанию, не стесняйтесь добавлять его в смысле определения функций черного ящика и обязательно связывайте ваши предложения в этом определении. Также не забудьте проголосовать за них.

Примеры

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
flawr
источник
Обратите внимание, что хотя в деталях подразумевается, что функция черного ящика будет сходиться в фиксированной точке, последний пример говорит об обратном
phflack
1
@phflack Черный ящик должен сходиться только для данного ввода.
flawr
О, изначально я думал, что представление не дано x_0, что вызвало у меня некоторое замешательство. Я думал, что решение должно быть (Jelly) ~Nƭ⁻Ç$¿, что-то вроде (псевдокод) for x in [0, -1, 1, -2, 2, -3, 3, -4, 4, ...]: if (x == f(x)): break; print(x); . Это может стоить еще одной проблемы.
user202729
1
Примечание для будущих посетителей: Поиск любой фиксированной точки не работает, вы должны найти фиксированную точку, достижимую от x_0. Гарантируется, что он существует.
user202729
А если не существует фиксированной точки, для функции f и одного начального значения x0 ... Каким должно быть значение, которое она должна возвращать? И если x0 = 0 и f = int (9 / (x-1)) с for для x1 = x0 + 1 f (x1) = f (1) - это уже одна ошибка ... Что должен вернуть оператор для этого f, x0?
РосЛюП

Ответы:

16

На самом деле , 1 байт

Y

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

Yявляется функцией фиксированной точки на самом деле. В примере TIO функция показана в виде строки и £используется для преобразования ее в функцию в стеке. Также можно просто поместить функцию в стек, как показано ниже . Это только два способа получить вход функции в действительности.

Mego
источник
7
Вы просто знали, что когда-нибудь этот вызов будет опубликован, не так ли? : P
Эрик Outgolfer
2
@EriktheOutgolfer Я действительно использовал Yдля нескольких задач. Я , видимо , очень precognizant : P
Mego
11

APL (Дьялог) , 2 байта

⍣=

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

NB: Я определяю O←⍣=в разделе ввода из-за ошибки в том, что производные монадические операторы не могут быть определены так, как TIO любит определять вещи.

Является ли оператор, который может быть использован как (function⍣condition) ⍵

Он применяется function, fк до (f ⍵) condition ⍵возвращения верно.

⍣=является производным монадическим оператором, который принимает монадическую функцию в fкачестве левого аргумента и применяет ее к правому аргументу доf ⍵ = ⍵

H.PWiz
источник
Может быть, обратите внимание, что ⍣=это производный монадический оператор, который принимает функцию в качестве левого операнда и находит точку фиксации для данного начального значения. Я хотел бы использовать другую букву для ⍣=чем , fкак это о perator, а не е помазание.
Адам
Да. Я мог бы. Это сбивает с толку, что вы вызываете функцию «ввода» fв своем описании, но затем на TIO, fваш оператор решения. Вы также можете переместить стрелку O←⍣=вверх в поле «Код», чтобы подсчитать его и указать, что это фактическое решение, а остальное (вход) просто его тестирует.
Адам
Похоже, ошибка для меня. Я поговорю с соответствующим коллегой завтра.
Адам
@ Adám Обновлено. Дайте мне знать, если ошибка будет исправлена
H.PWiz
10

Haskell, 17 байт

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

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

Ними
источник
3
В случае, если кому-то интересно: вот объяснение, почему until=<<((==)=<<) находит точку привязки для данной функции.
Лайкони
9

MATLAB , 41 байт

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

Существует также эта красота , которая не нуждается в функциональных файлах. К сожалению, это немного дольше:

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)

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

flawr
источник
7
Этот ответ был задуман как пример и не мешает никому отвечать.
flawr
Конечно, если бы вы назвали эту Октаву, вы могли бы удалить два ;с. Попробуйте онлайн! ,
Санчиз
А в вашей анонимной функции вы можете удалить значение @()before xдля 50 байтов. Слава также за то, как вы оборачиваете свою вспомогательную функцию ( g(g)в конце), мне удалось сделать только 51 байт @(g,x)(f=@(r,z){@()r(r,m),z}{(m=g(z)==z)+1}())(f,x). Мне интересно, есть ли комбинация обоих подходов, которая еще короче.
Санчиз
6

Стандартный ML (MLton) , 30 байтов

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

Попробуйте онлайн! Использовать как& n blackbox .

Функции черного ящика определены следующим образом:

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

Безголовая версия:

fun fixpoint n g = if n = g n then n else fixpoint (g n) g
Laikoni
источник
1
Приятно видеть SML в дикой природе! Мы используем его для нашего класса функционального программирования в нашем университете.
Виджрокс
4

Python 2 , 39 37 33 байта

спасибо @ Mr.Xcoder за -2 байта

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

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

предполагает, что функция черного ящика будет названа f

овс
источник
Разве функция не должна передаваться как параметр? Я не думаю, что предопределенные переменные являются приемлемым методом ввода.
mbomb007
Я не уверен, что вам разрешено предполагать, что функция есть f, разве это не форма предположения, что входные данные находятся в переменной? (редактировать: ninja'd от mbomb)
FlipTack
4

JavaScript (Node.js) , 25 22 21 байт

спасибо Герману Лауэнштейну за то, что он показал мне это согласие
благодаря @ l4m2 за -1 байт

Предполагается, что функция черного ящика будет названа f.

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

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

овс
источник
4

Желе , 3 байта

vÐL

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

Принимает левый аргумент в виде строки, представляющей ссылку Jelly (2_ например), а правый аргумент как целое число

Как это работает

 ÐL - While the output is unique...
v   -   Evaluate the function with the argument given
Caird Coneheringaahing
источник
4

Brain-Flak , 24 байта

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

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

(для функции черного ящика x -> 2-xв примере ниже)

Предоставленная функция черного ящика должна быть программой, которая задана xна вершине стека, pop xи push f(x)- другими словами, она должна оценивать функцию fпо значению на вершине стека.

Эквивалентный мини-флак составляет 26 байтов (спасибо Wheat Wizard за сохранение 2 байта):

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

(не считая комментариев и пробелов)

Возьмите функцию (внутри <>) и число от ввода. (обратите внимание, что Brain-Flak является эзотерическим языком и не может принимать функциональные аргументы в качестве входных данных)x0


Пример функций черного ящика:

x -> 2-x: Попробуйте онлайн!


Объяснение:


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

user202729
источник
3

Swift , 47 42 байта

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

Наивный подход, предполагает, что функция черного ящика названа f

Герман Л
источник
Я сомневаюсь относительно вашей второй попытки, потому что это сложное замыкание и его тип неоднозначен, если вы явно не применили его {...}as(<parameter types>)-><return type>. Если вы не укажете тип возвращаемого значения, он выдаст ошибки времени сборки, поэтому я не думаю, что он действителен на данный момент (обратите внимание, что приведение должно быть включено в число байтов). Впрочем, ваше первое представление в порядке.
г-н Xcoder
2

C (gcc) , 40 байт

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

Попробуйте онлайн! Обратите внимание, что флаги не нужны, они есть, чтобы помочь с тестированием функции Fixpoint, определенной выше.

Это функция, которая принимает int nи указатель на функцию b : int → int. Злоупотребление фактом, что запись в первый аргумент переменной устанавливает eaxрегистр, который эквивалентен возвращению . В остальном, это довольно стандартно для C Golf. n^b(n)проверяет на неравенство nи черный ящик применяется к n. Когда неравенство, он вызывает функцию Fixpointf снова рекурсивно с приложением и черным ящиком в качестве аргументов. В противном случае он возвращает точку фиксации.

† Требуется цитирование, я смутно помню, что где-то читал это, и Google, кажется, подтверждает мои подозрения

Он объявляет ввод с набором параметров в стиле K & R:

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

Тайный бит во второй строке выше объявляется bкак указатель на функцию, который принимает целочисленный параметр - тип по умолчанию _для целого числа. Аналогично, nпредполагается, что это целое число, и fпредполагается, что оно возвращает целое число. Ура для неявной типизации?

Конор О'Брайен
источник
2

Чисто , 46 байт

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

Предполагается, что функция определяется как f :: !Int -> Int

Это занимает голову бесконечного списка приложений, f f f ... xотфильтрованных для тех элементов, где f el == el.

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

Если вы хотите изменить функцию в TIO, лямбда-синтаксис Clean:

\argument = expression

(на самом деле это гораздо сложнее, но, к счастью, нам нужны только унарные функции)

Οurous
источник
2

APL (Dyalog Unicode) , 14 байтов

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

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

Функция в заголовке эквивалентна f(x) = floor(sqrt(abs(x)))

Спасибо @ Adám за указание на то, что первоначальный ответ был недействительным в соответствии с консенсусом PPCG.

Как это работает:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}  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⍵)} было бы хорошо для отделения анонимной функции от ее имени (n)
RosLuP
2
Это предполагает, что fэто предварительно назначено, что, я думаю, запрещено консенсусом PPCG. {⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}будет действительным операторским решением.
Адам
1

Forth (gforth), 36 байтов

Эта версия предполагает, что fона предопределена. Это не так круто, как решение под ним. Обе программы выходят с переполнением стека, если не найдено, или с переполнением стека, если найдено (после печати результата).

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

: g dup f over = IF . THEN recurse ;

Forth (gforth), 52 байта

Это позволяет передавать маркер выполнения функции в качестве параметра и, безусловно, является более подходящим решением.

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

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

Объяснение:

: 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
mbomb007
источник
1

тинилисп репл , 28 байт

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

Предполагается, что функция f предопределена.

Попробуйте онлайн! (Пример функции f(x) = (x*2) mod 10.)

Ungolfed

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

Если f(x)равно x, то xявляется фиксированной точкой; верни это. В противном случае, рекурсивно искать неподвижную точку , начиная с f(x)вместо x.

DLosc
источник
1

APL NARS 65 символов

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 будет возвращать ∞ (или, возможно, -oo или Nan) для ошибки, иначе одно значение x с x = f (x). В тесте f = floor (sqrt (abs (x))), f1 = 2-x, f2 = c (c (c (x))) с 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
RosLuP
источник
1

Clojure, 45 43 байта

Ну, это самое короткое и самое уродливое

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

+есть вместо числа, так что оно не равно ни одному значению x0.

55 байт и функционал:

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

Пример:

(def f #(...))
(defn collaz [x] (if (even? x) (-> x (/ 2)) (-> x (* 3) (+ 1))))
(f (->> collaz (repeat 3) (apply comp)) 125)
; 1
NikoNyrh
источник
1

код операции x86, 8 байт

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

Взять входные данные: ecx(значение ), (адрес функции, получить входные данные , записать результат без изменения значения и )x0edxecxeaxecxedx

8086 код операции, 7 байт (но медленно)

    xor     cx,     cx
    call    dx
    loop    $-2
    ret

Если существует фиксированная точка, то ее повторяют в цикле 65536 раз.
Взять входные данные: ax(начальное значение ), (адрес функции, получить входные данные , записать выходные данные без изменения значения и ). Вывести фиксированную точку в регистр .x0dxaxaxcxdx
ax

l4m2
источник
Это, безусловно, поможет, если вы сделаете ответ более читабельным.
user202729
больше правки, чтобы исправить
l4m2
0

Java 8, 42 байта

Это берет Function<Integer, Integer>или или IntFunction<Integer>и intили Integer(карри) и возвращает фиксированную точку.

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

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

Использует тот факт, что Java оценивает подвыражения слева направо (поэтому старое iсравнивается с новым), свойство, о котором я не знал, когда писал это!

Jakob
источник