Interview question: 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

- Unknown

---

我感觉这些会接踵而至... - matt b

是面试周吗？还是有人在审核面试问题？ - i_am_jorf

“受到启发”？这就像是同一个问题！ - Chuck

哇，我感受到了所有的仇恨。将其关闭为与编程无关，并说这是相同的问题？现在SO自卫者删除了6个答案中的5个。 - Unknown

面试者的问题是：“那这怎么证明你作为一名专业开发人员的技能呢？” - Euro Micelli

Answer 1

对于第一部分：在我看来，这比f(f(x)) = -x要更平凡：

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

第二部分是一个有趣的问题，也是原始问题的明显推广。有两种基本方法：

• 一种是数值方法，使得x ≠ f(x) ≠ f(f(x))，我认为这更符合原始问题的精神，但我认为在一般情况下不可能实现。
• 一种是涉及到g(g(x))正好调用f一次的方法。

- Miles

---

好的解决方案 - 值得注意的是，当然不能对0起作用 ;) - markt

使用符号来存储状态的想法很棒。它的缺点（对于0无效）是普遍存在的，不需要在这里提到。 - Chris Lutz

如果你将0传递给这个函数，你会得到一个除以0的错误。我认为值得一提。 - markt

实际上，在C/C++/Java中，这不会导致除以零的错误，它将给出“inf”，这是正确的答案。它对于“-0.0f”失败，因为它被认为等于0。它可以处理“-inf”作为输入，但对于“+inf”则失败。如果您将条件更改为“x> 0 || x为+0.0f（但不是-0.0f！）”，它将起作用，但遗憾的是我不知道如何实际编写它。 :-( - Kip

为了区分IEEE 754数值x的+0和-0，您可以使用表达式x > 0.0 || (x == 0.0 && 1.0 / x > 0.0)。后面的表达式将把+0映射到+Inf，将-0映射到-Inf。 - Roland Illig

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 s.t. σ（σ^-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

这个方法有效是因为：

• 对于所有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）。

可以看出，如果我们忽略0，则操作σ（x）= -x适用于f（x）= 1 / x。你可以自己检查1-6（对于D = 非零实数），其中A是正数，B是负数。使用双精度标准，有一个+0，一个-0，一个+inf和一个-inf，这些可以用于使定义域总体（应用于所有双精度数字，而不仅仅是非零数字）。

相同的方法也可应用于f（x）= -1问题-其中被接受的解决方案通过使用σ（x）=（x-1）将空间划分为模2的余数，并特殊处理零的情况。

- rampion

---

其实，这相当狡猾（在单线程的情况下）:-)。 - paxdiablo

是的，但如果我执行x = g(3.0)，y = g(4.0)，z = g(x)，a = g(y)，它仍然会出错 => z = 3.0，a = 4.0。我需要一个更好的数据结构来处理多个值。 - rampion

我从未想过，我再次看到一阶逻辑的时候会在一个社区网站上。 - Unknown

Answer 3

我喜欢之前帖子中提到的 JavaScript/lambda 建议：

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

- Joel Coehoorn

---

我认为这是一个优雅的解决方案。不过，我想知道是否有任何数学/语言专家能告诉我们一个神奇的算法来分解这样的函数。 - Unknown

这真的有效吗？它似乎取决于语言的评估规则。通常，我会假设所有参数都先进行评估，然后只传递它们的返回值给外部函数调用。 - Svante

Svante：内部f(x)调用的返回值是一个函数。 - Miles

Answer 4

如果f(x) == g(g(x))，那么g被称为f的函数平方根。即使允许x是复数，我认为通常情况下没有闭合形式（你可能想去mathoverflow讨论：)）。请注意保留HTML标签。

- kennytm

Answer 5

其他解决方案暗示需要额外的状态。这里有一个更数学化的理论基础：

让 f(x) = 1/(x^i)= x^-i (其中 ^ 表示指数，i 是虚数常量 sqrt(-1))

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

因此，对于复数存在解决方案。我不知道是否有一个严格依据实数的通用解决方案。

- MadCoder

Answer 6

一个关于 g(g(x)) == f(x) 的 C++ 解决方案：

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();
}

- cube

Answer 7

再次强调，它被指定为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 位数据类型 32bit。

- Loren Pechtel

Answer 8

有另一种解决方法，它使用分数线性变换的概念。这些是将x发送到(ax+b)/(cx+d)的函数，其中a、b、c、d是实数。

例如，您可以使用一些代数证明如果f由f(x)=(ax+1)(-x+d)定义，其中a^2=d^2=1且a+d<>0，则对于所有实数x，f(f(x))=1/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)/(-(x+1)/(-x+1)+1) = (2/(1-x))/(2x/(1-x))=1/x，消去(1-x)。

除非我们允许定义一个“无限”的值满足1/inf = 0，1/0 = inf，否则此公式对于x=1或x=0不起作用。

- Ivan

---

其实是一个非常不错的尝试。然而，我得到了f(f(x)) = -1/x，不幸的是，解出一些正确的a、b、c、d总是会得到一些复数值。 - Accipitridae

真的很抱歉！我应该意识到这些变换的组合是2x2矩阵的矩阵乘法，因此f(f(x))=1/x意味着存在一个2x2实矩阵A，使得A^2 = {{0,1},{1,0}}。通过求行列式，我们得到(det A)^2 = -1，因此没有实数解！ - Ivan

Answer 9

基于这个答案，一个通用版本的解决方案（作为Perl一行代码）：

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

应该始终两次翻转变量的符号（也称为状态），并且应该始终仅调用f()一次。对于那些没有Perl隐式返回的语言，只需在{之前插入return即可。

只要f()不改变变量的符号，此解决方案就有效。在这种情况下，它返回原始结果（对于负数）或f(f())的结果（对于正数）。另一种选择是像上一个问题的答案一样将变量的状态存储为偶数/奇数，但如果f()更改（或可以更改）变量的值，则会出现问题。更好的答案，正如已经说过的，是lambda解决方案。这里是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;
}

- Chris Lutz

Answer 10

试一下这个

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

- labi

---

这个答案在当前版本中缺少描述和代码缩进（在每行代码前添加四个空格）。请考虑编辑它。 - Matthias