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

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

有什么想法吗?


当前回答

嗯,我既不是数学,也不是编程高手,但这不是很容易吗?

int f(int i) {
    static bool b;
    if (b) {
        b = !b;
        return i;
    } else {
        b = !b;
        return -i;
    }
}

用大小正值和负值INT_MIN、INT_MAX进行测试,似乎可以。。。如果这是一个问题,可以使线程安全,但这不是任务的一部分。

或者我错过了什么?

其他回答

下面是一个简短的Python答案:

def f(n):
  m = -n if n % 2 == 0 else n
  return m + sign(n)

一般情况

稍微调整一下上面的内容就可以处理我们希望k个自调用否定输入的情况——例如,如果k=3,这意味着g(g(g)n))=-n:

def g(n):
  if n % k: return n + sign(n)
  return -n + (k - 1) * sign(n)

这是通过将0保留在适当位置并创建长度为2*k的循环来实现的,因此,在任何循环中,n和-n之间的距离为k。具体来说,每个周期如下:

N * k + 1, N * k + 2, ... , N * k + (k - 1), - N * k - 1, ... , - N * k - (k - 1)

或者,为了更容易理解,这里是k=3的示例循环:

1, 2, 3, -1, -2, -3
4, 5, 6, -4, -5, -6

这组循环最大化了在任何以零为中心的机器类型(如有符号int32或有符号int64类型)内工作的输入范围。

兼容范围分析

映射x->f(x)实际上必须形成长度为2*k的循环,其中x=0是特殊情况下的1-长度循环,因为-0=0。因此,一般k的问题是可解的,当且仅当输入-1(补偿0)的范围是2*k的倍数,并且正负范围是相反的。

对于有符号整数表示,我们总是有一个最小的负数,在该范围内没有正的对应项,因此该问题在整个范围内变得不可解决。例如,有符号字符的范围为[-128127],因此在给定范围内f(f(-128))=128是不可能的。

有些类似,但我只是想写下我的第一个想法(用C++)

#include <vector>

vector<int>* f(int n)
{
  returnVector = new vector<int>();
  returnVector->push_back(n);
  return returnVector;
}

int f(vector<int>* n) { return -(n->at(0)); }

仅使用重载使f(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()

由于C++中的重载:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}