面试问题: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)),我认为这更符合原问题的精神,但我认为在一般情况下是不可能的
• 涉及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→D,你需要的是一个函数σ,它将域D划分为A和B,这样:

1. D =A∪B,(分区是总的)
2. ∅=A∩B(分区不相交)
3. σ(a)∈B,f(a)∈A∀a∈A,
4. σ(b)∈A,f(b)∈B∀b∈B,
5. σ具有逆σ ^- 1σ(σ ^-1(d))=σ ^-1(σ(d))=d∀d∈D.
6. σ(f(d))= f(σ(d))∀d∈D

然后,你可以这样定义g:

• g(a)=σ(f(a))∀a∈A
• g(b)=σ ^-1(b)∀b∈B

这适用于b/c

• ∀a∈A,g(g(a))= g(σ(f(a)).由(3),f(a)∈A所以σ(f(a))∈B所以g(σ(f) (a))=σ ^-1(σ(f(a)))= f(a).
• ∀b∈B,g(g(b))= g(σ ^-1(b)).由(4),σ ^-1(b)∈A所以g(σ ^-1(b))=σ(f(σ ^-1(b)))= f(σ(σ ^-1(b)))= F(b).

你可以从Miles回答看,如果我们忽略0,那么操作σ(x)= -x适用于f(x)= 1/x.您可以检查1-6(对于D =非零实数),A为正数,B为负数.使用双精度标准,有a +0,a -0,a +inf和a -inf,这些可用于使域总数(适用于所有双精度数,而不仅仅是非零).

同样的方法可以应用于f(x)= -1问题 - 使用σ(x)=(x - 1),通过余数mod 2对空间进行分区的接受解决方案,特别处理零情况.

Answer 3

我喜欢早期帖子中的javascript/lambda建议:

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