我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这里有一个证明,如果不使用额外信息(除了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个数字作为奖励。(但这只是一个愚蠢的假设。)
其他回答
int f(int n) {
return ((n>0)? -1 : 1) * abs(n);
}
除int.MaxValue和int.MinValue以外的工作
public static int f(int x)
{
if (x == 0) return 0;
if ((x % 2) != 0)
return x * -1 + (-1 *x) / (Math.Abs(x));
else
return x - x / (Math.Abs(x));
}
也许是作弊?(python)
def f(n):
if isinstance(n, list):
return -n[0]
else:
return [n,0]
n = 4
print f(f(n))
--output--
-4
C++中的另一个作弊解决方案是运算符重载。
struct func {
int n;
func operator()(int k) { n = -k; return *this; }
int operator()(const func &inst) { return inst.n; }
} f;
void f(int x)
{
Console.WriteLine(string.Format("f(f({0})) == -{0}",x));
}
抱歉,伙计们。。。这太诱人了;)