我在上次面试中遇到的一个问题是:

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

这适用于1073741823至1073741822范围:

int F(int n)
{
    if(n < 0)
    {
        if(n > -1073741824)
            n = -1073741824 + n;
        else n = -(n + 1073741824);
    }
    else
    {
        if(n < 1073741823)
            n = 1073741823 + n;
        else n = -(n - 1073741823);
    }
    return n;
}

它的工作原理是获取32位有符号整数的可用范围并将其一分为二。函数的第一次迭代将n自身置于该范围之外。第二次迭代检查它是否在该范围之外-如果是,则将其放回该范围内,但使其为负值。

这实际上是一种保留关于值n的额外“位”信息的方法。

其他回答

怎么样

int f(int n)
{
    return -abs(n);
}

Wolfram语言的解决方案:

f[f[n_]] := -n

应用程序:

In[2]:= f[f[10]]                                                                                                                                                                                                                                                                              
Out[2]= -10
In[3]:= f[10]                                                                                                                                                                                                                                                                                 
Out[3]= f[10]

因为这个问题没有说明f(n)的值,所以f[n]仍然没有赋值。

另一个作弊解决方案。我们使用允许运算符重载的语言。然后我们让f(x)返回重载==的值,以始终返回true。这似乎与问题描述相符,但显然违背了谜题的精神。

Ruby示例:

class Cheat
  def ==(n)
     true
  end
end

def f(n)
  Cheat.new
end

这给了我们:

>> f(f(1)) == -1
=> true

而且(不太令人惊讶)

>> f(f(1)) == "hello world"
=> true

你没说他们期望什么样的语言。。。这是一个静态解决方案(Haskell)。这基本上是在搞乱两个最重要的比特:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

在动态语言(Python)中要容易得多。只需检查参数是否为数字X,并返回返回-X的lambda:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

PHP,不使用全局变量:

function f($num) {
  static $mem;

  $answer = $num-$mem;

  if ($mem == 0) {
    $mem = $num*2;
  } else {
    $mem = 0;
  }

  return $answer;
}

适用于整数、浮点数和数字字符串!

只是意识到这会做一些不必要的工作,但是,不管怎样