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

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

有什么想法吗?


当前回答

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]仍然没有赋值。

其他回答

本质上,函数必须将可用范围划分为大小为4的循环,其中-n位于n循环的另一端。但是,0必须是大小为1的循环的一部分,否则0->x->0->x!=-x.因为0是单独的,所以在我们的范围内必须有3个其他值(其大小是4的倍数)不在具有4个元素的正确循环中。

我选择这些额外的奇怪值为MIN_INT、MAX_INT和MIN_INT+1。此外,MIN_INT+1将正确映射到MAX_INT,但会被卡在那里而不能映射回来。我认为这是最好的妥协,因为它有一个很好的特性,即只有极端值不能正常工作。此外,这意味着它将适用于所有BigInt。

int f(int n):
    if n == 0 or n == MIN_INT or n == MAX_INT: return n
    return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)

这里有一个解决方案,其灵感来自于不能使用复数来解决这个问题的要求或声明。

乘以-1的平方根是一个想法,但似乎失败了,因为-1没有整数的平方根。但是,使用mathematica这样的程序可以得出如下公式

(18494364652+1)模(232-3)=0。

这几乎和平方根为-1一样好。函数的结果必须是有符号整数。因此,我将使用一个修改的模运算mods(x,n),它返回与x模n最接近0的整数y。只有极少数编程语言能够成功地进行模运算,但它很容易被定义。例如,在python中,它是:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n
    return y

使用上面的公式,问题现在可以解决为

def f(x):
    return mods(x*1849436465, 2**32-3)

对于[-231-2231-2]范围内的所有整数,这满足f(f(x))=-x。f(x)的结果也在这个范围内,但当然计算需要64位整数。

事实上,我并没有试图给出问题本身的解决方案,但我有几点意见,因为问题表明,提出这个问题是(工作?)面试的一部分:

我会先问“为什么需要这样的函数?这是什么更大的问题?”而不是试图当场解决实际提出的问题。这表明了我是如何思考和解决这样的问题的。谁知道?这甚至可能是在一次采访中首先提出这个问题的真正原因。如果答案是“没关系,假设它是需要的,并告诉我如何设计这个功能。”我会继续这样做。然后,我将编写我将使用的C#测试用例代码(显而易见:从int.MinValue到int.MaxValue的循环,对于该范围内的每个n调用f(f(n)),并检查结果是-n),告诉我将使用测试驱动开发来获得这样的函数。只有当面试官继续要求我解决所提出的问题时,我才真正开始在面试过程中胡乱写下伪代码,试图得到某种答案。然而,如果面试官能说明公司的情况,我真的不认为我会跳下去接受这份工作。。。

哦,这个答案假设面试是针对一个与C#编程相关的职位。如果面试的是与数学相关的职位,那当然是一个愚蠢的答案

另一种方法是将状态保持在一位,并在负数的情况下翻转它,注意二进制表示。。。限制为2^29

整数ffn(整数n){

    n = n ^ (1 << 30); //flip the bit
    if (n>0)// if negative then there's a two's complement
    {
        if (n & (1<<30))
        {
            return n;
        }
        else
        {
            return -n;
        }
    }
    else
    {
        if (n & (1<<30))
        {
            return -n;
        }
        else
        {
            return n;
        }
    }


}
int f(const int n)  {
    static int last_n;

    if (n == 0)
        return 0;
    else if (n == last_n)
        return -n;
    else
    {
        last_n = n;
        return n;
    }
}

哈克,但正确。