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

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

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

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

пусть f (x) = 1 / (x ^ i) = x ^ -i

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

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

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

Опять же, он указан как 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 бит.

Ну, все вопросы были даны ответы, кроме последнего, на который ответ да. Для POST это разрешено, но вы вполне можете найти случаи, когда оно не работает. Я видел веб-серверы, которые допускают только строку запроса postdata или , поэтому она не надежна.

σ ^-1 (b) ∈ A so g (σ ^-1 (b)) = σ (f (σ ^-1 (b))) = f (σ (σ ^-1 (b))) = f (b).

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

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

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

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

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

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

где A - положительные числа, а B - отрицательные числа. В стандарте двойной точности есть +0 , a -0 , a + inf и -инф , и они может использоваться для того, чтобы сделать область общей (применимо ко всем числам двойной точности, а не только к ненулевым).

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

где A - положительные числа, а B - отрицательные числа. В стандарте двойной точности есть +0 , a -0 , a + inf и -инф , и они может использоваться для того, чтобы сделать область общей (применимо ко всем числам двойной точности, а не только к ненулевым).

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

Based on this answer, a solution to the generalized version (as a Perl one-liner):

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

Should always flip the variable's sign (a.k.a. state) twice, and should always call f() only once. For those languages not fortunate enough for Perl's implicit returns, just pop in a return before the { and you're good.

This solution works as long as f() does not change the variable's sign. In that case, it returns the original result (for negative numbers) or the result of f(f()) (for positive numbers). An alternative could store the variable's state in even/odd like the answers to the previous question, but then it breaks if f() changes (or can change) the variable's value. A better answer, as has been said, is the lambda solution. Here is a similar but different solution in Perl (uses references, but same concept):

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

Note: This is tested, and does not work. It always returns a reference to a scalar (and it's always the same reference). I've tried a few things, but this code shows the general idea, and though my implementation is wrong and the approach may even be flawed, it's a step in the right direction. With a few tricks, you could even use a string:

use String::Util qw(looks_like_number);

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

There is another way to solve this and it uses the concept of fractional linear transformations. These are functions that send x->(ax+b)/(cx+d) where a,b,c,d are real numbers.

For example you can prove using some algebra that if f is defined by f(x)=(ax+1)(-x+d) where a^2=d^2=1 and a+d<>0 then f(f(x))=1/x for all real x. Choosing a=1,d=1, this give a solution to the problem in C++:

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

The proof is f(f(x))=f((x+1)/(-x+1))=((x+1)/(-x+1)+1)/(-(x+1)/(-x+1)+1) = (2 / (1-x)) / (2x / (1-x)) = 1 / x при отмене (1-x).

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

решение 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();
}

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