我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
另一个作弊解决方案。我们使用允许运算符重载的语言。然后我们让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
其他回答
从来没有人说过f(x)必须是同一类型。
def f(x):
if type(x) == list:
return -x[0]
return [x]
f(2) => [2]
f(f(2)) => -2
我认为最大的可能范围是暗示模块化算术解决方案。在一些模基M中,有一个数,当平方等于M-1(等于-1)。例如,如果M=13,5*5=25,25 mod 13=12(=-1)总之,这里有一些M=2**32-3的python代码。
def f(x):
m=2**32-3;
halfm=m//2;
i_mod_m=1849436465
if abs( x ) >halfm:
raise "too big"
if x<0:
x+=m
x=(i_mod_m*x) % m
if (x>halfm):
x-=m
return x;
注意,有3个值不适用于2**31-1、-(2**31-1)和-(2*#31)
本质上,函数必须将可用范围划分为大小为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
这适用于除“-1”以外的所有数字。
如果要从使用int转换为使用NSInt,那么可以将-1值设置为NULL,然后第二次将它们转换为+1,但我觉得NSInt欺骗了询问者的意图。
f(n):
-(int)f:(int)n {
if (abs(n)==1) {
n = -1;
} else {
if (abs(n)%2) {//o
if (n>0) {//+
n--;
n*=+1;
} else if (n<0) {//-
n++;
n*=+1;
}
} else {//e
if (n>0) {//+
n++;
n*=-1;
} else if (n<0) {//-
n--;
n*=-1;
}
}
}
return n;
}
当然,这一切都可以缩短为一行,但其他人可能无法阅读。。。
无论如何,我将BOOLEAN逻辑存储为奇数或偶数的状态。