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

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

有什么想法吗?


当前回答

我不知道这是否完全正确,但一个简单的标志不起作用吗?在C语言中,使用静态局部变量,我成功地做到了这一点:

int main()
{
    int n = -256; // 32-bit signed integer
    printf("%d", f(f(n)));
}

int f(int n){
    static int x = 0; // not returning negative;
    switch(x){
        case 0:
            x = 1;
            return n;
            break;

        case 1:
            x = 0;
            return -n;
            break;
        default:
            return -999;
            break;
    }
}

其他回答

这里有一个证明,如果不使用额外信息(除了32位的int),那么对于所有数字,这样的函数都不可能存在:

我们必须使f(0)=0。(证明:假设f(0)=x,则f(x)=f(f(0))=-0=0。现在,-x=f(f(x))=f(0)=x,这意味着x=0。)

此外,对于任何x和y,假设f(x)=y。那么我们希望f(y)=-x。并且f(f(y))=-y=>f(-x)=-y。总结一下:如果f(x)=y,那么f(-x)=-y,f(y)=-x,f(-y)=x。

因此,我们需要将除0之外的所有整数分成4个集合,但我们有奇数个这样的整数;不仅如此,如果我们去掉没有正对应的整数,我们仍然有2(mod4)个数。

如果我们去掉剩下的2个最大数(通过abs值),我们可以得到函数:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}   

当然,另一种选择是不遵守0,并获得我们删除的2个数字作为奖励。(但这只是一个愚蠢的假设。)

使用循环置换方法来实现这一点。

-b a b-a

a b-a-b

在微不足道的情况下f(0)返回0

对不起,我的电话回答很粗糙,28日后我将发布完整版本(现在正在检查…)简单地说,假设f(n)是一个循环排列,问题是如何构造它。

定义fk=f(f(f)f(…f(n))))(k fs)情况k=20.微不足道的情况f(0)返回01.分组,在情况k=2时,分组:{0} {1,2} {3,4} ... {n,n+1 |(n+1)%2=0}注意:我只使用Z+,因为结构不需要使用负数。2.构造排列:如果n%2=0,那么a=n-1 b=n如果n%2=1,则a=n b=n+1

这将产生相同的排列,因为n和f(n)在同一组中。

注意排列为P返回P(n)

对于k=2t,只做上面相同的事情,只做MOD k。对于k=2t-1,虽然该方法有效,但毫无意义,啊?(f(n)=-n正常)

f(n) { return IsWholeNumber(n)? 1/n : -1/n }

你没说他们期望什么样的语言。。。这是一个静态解决方案(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()

适用于n=[0..2^31-1]

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}