Вопрос интервью: f (f (x)) == 1 / x

Question

Разработайте функцию f так, чтобы:

f (f (x)) == 1 / x

Где x - 32-битное число с плавающей запятой

Или как насчет

По заданной функции f найти функцию g такой, что

f (x) == g (g (x))

<Ч />

См. Также

Вопрос для интервью: f (f (n)) == -n

Answer 1

Для первой части: эта более тривиальна, чем f (f (x)) = -x, IMO:

float f(float x)
{
    return x >= 0 ? -1.0/x : -x;
}

Вторая часть - интересный вопрос и очевидное обобщение исходного вопроса , на котором был основан этот вопрос. Есть два основных подхода:

• численный метод, такой, что x ≠ f (x) ≠ f (f (x)), который, я считаю, больше соответствовал духу исходного вопроса, но я не думаю, что это возможно в общем случае 1009 *
• метод, включающий g (g (x)), вызывающий f ровно один раз

Answer 2

Ну, вот быстрый взлом C:

extern double f(double x);
double g(double x)
{
  static int parity = 0;
  parity ^= 1;
  return (parity ? x : f(x));
}

Однако, это сломается, если вы сделаете:

a = g(4.0); // => a = 4.0, parity = 1
b = g(2.0); // => b = f(2.0), parity = 0
c = g(a);   // => c = 4.0, parity = 1
d = g(b);   // => d = f(f(2.0)), parity = 0

В общем случае, если f - биекция f: D & rarr; D, вам нужна функция & sigma; который разделяет домен D на A и B так, что:

1. D = A & cup; Б (раздел тотальный)
2. & пусто; = A & cap; B (раздел не пересекается)
3. & sigma; (a) & isin; B, f (a) & isin; A & forall; & isin; A
4. & sigma; b) & isin; A, f (b) & isin; B & Forall; b & isin; B
5. & Sigma; имеет обратную & sigma; ^-1 s.t. & sigma; (& sigma; ^-1 (d)) = & sigma; ^-1 (& sigma; (d)) = d & forall; д & исин; D.
6. & sigma; (f (d)) = f (& sigma; (d)) & forall; д & исин; D

Затем вы можете определить g следующим образом:

• g (a) = & sigma; (f (a)) & forall; & isin; A
• g (b) = & sigma; ^-1 (b) & forall; b & isin; B

Это работает б / с

• & FORALL; & isin; A, g (g (a)) = g (& sigma; (f (a)). Согласно (3), f (a) & isin; A so & sigma; (f (a)) & isin; B so g (& sigma; (f (a)) = & sigma; ^-1 (& sigma; (f (a))) = f (a).

Из ответа Майлза видно, что если мы игнорируем 0, то операция & sigma; (x) = -x работает для f (x) = 1 / x. Вы можете проверить 1-6 (для D = ненулевые вещественные числа), где A - положительные числа, а B - отрицательные числа. В стандарте двойной точности есть +0, -0, a +inf и -inf, и они могут быть использованы для получения общего значения домена (применимо ко всем числам двойной точности, а не только к ненулевым ).

Тот же самый метод может быть применен к проблеме f (x) = -1 - принятое решение там разделяет пространство на оставшуюся часть mod 2, используя & sigma; (x) = (x - 1), обрабатывая нулевой случай специально.

Answer 3

Мне нравится предложение javascript / lambda из предыдущей ветки:

function f(x)
{
   if (typeof x == "function")
       return x();
   else
       return function () {return 1/x;}
}

Answer 4

Другие решения намекают на необходимость дополнительного состояния. Вот более математическое обоснование этого:

let f(x) = 1/(x^i)= x^-i

(где ^ обозначает показатель степени, а i - мнимая постоянная sqrt (-1))

f(f(x)) = (x^-i)^-i) = x^(-i*-i) = x^(-1) = 1/x

Таким образом, решение существует для комплексных чисел. Я не знаю, есть ли общее решение, строго придерживающееся Реальных чисел.

Answer 5

Если f(x) == g(g(x)), то g известен как функциональный квадратный корень из f. Я не думаю, что в общем случае есть закрытая форма, даже если вы позволите x быть сложным (вы можете перейти к mathoverflow, чтобы обсудить :)).

Answer 6

решение C ++ для g(g(x)) == f(x):

struct X{
    double val;
};

X g(double x){
    X ret = {x};
    return ret;
}

double g(X x){
    return f(x.val);
}

вот одна более короткая версия (мне она больше нравится :-))

struct X{
    X(double){}
    bool operator==(double) const{
        return true
    }
};

X g(X x){
    return X();
}

Answer 7

Существует еще один способ решения этой проблемы, в котором используется концепция дробных линейных преобразований. Это функции, которые отправляют x -> (ax + b) / (cx + d), где a, b, c, d - действительные числа.

Например, вы можете доказать с помощью некоторой алгебры, что если f определяется как f (x) = (ax + 1) (- x + d), где a ^ 2 = d ^ 2 = 1 и a + d <> 0 тогда f (f (x)) = 1 / x для всех вещественных x. Выбор a = 1, d = 1, это дает решение проблемы в C ++:

float f(float x)
{
    return (x+1)/(-x+1);
}

Доказательство f (f (x)) = f ((x + 1) / (- x + 1)) = ((x + 1) / (- x + 1) +1) / (- ( х + 1) / (- х + 1) + 1) = (2 / (1-x)) / (2x / (1-x)) = 1 / x при отмене (1-x).

Это не работает для x = 1 или x = 0, если только мы не позволим определить «бесконечное» значение, которое удовлетворяет 1 / inf = 0, 1/0 = inf.

Answer 8

Опять же, это указано как 32-битное число. Сделайте так, чтобы в возвращении было больше битов, используйте их для передачи информации о вашем состоянии между вызовами.

Const
    Flag = $100000000;

Function F(X : 32bit) : 64bit;

Begin
    If (64BitInt(X) And Flag) > 0 then
        Result := g(32bit(X))
    Else
        Result := 32BitInt(X) Or Flag;
End;

для любой функции g и любого 32-битного типа данных 32 бит.

Answer 9

попробуйте

MessageBox.Show( "x = " + x );
MessageBox.Show( "value of x + x is " + ( x + x ) );
MessageBox.Show( "x =" );
MessageBox.Show( ( x + y ) + " = " + ( y + x ) );

Answer 10

На основании этого ответа , решение обобщенной версии (в виде однострочного Perl):

sub g { $_[0] > 0 ? -f($_[0]) : -$_[0] }

Всегда должен дважды поменять знак переменной (состояние a.k.a.) и всегда вызывать f() только один раз. Для тех языков, которым не повезло для неявных возвращений Perl, просто вставьте return перед {, и все хорошо.

Это решение работает, пока f() не меняет знак переменной. В этом случае он возвращает исходный результат (для отрицательных чисел) или результат f(f()) (для положительных чисел). Альтернатива может хранить состояние переменной в четном / нечетном виде, как ответы на предыдущий вопрос, но затем она прерывается, если f() изменяет (или может изменять) значение переменной. Лучшим ответом, как уже было сказано, является лямбда-решение. Вот похожее, но другое решение в Perl (использует ссылки, но та же концепция):

sub g {
  if(ref $_[0]) {
    return ${$_[0]};
  } else {
    local $var = f($_[0]);
    return \$var;
  }
}

Примечание: это проверено, и не работает. Он всегда возвращает ссылку на скаляр (и это всегда одна и та же ссылка). Я попробовал несколько вещей, но этот код показывает общую идею , и, хотя моя реализация неверна и подход может даже быть ошибочным, это шаг в правильном направлении. С помощью нескольких трюков вы можете даже использовать строку:

use String::Util qw(looks_like_number);

sub g {
  return "s" . f($_[0]) if looks_like_number $_[0];
  return substr $_[0], 1;
}