我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
:D
boolean inner = true;
int f(int input) {
if(inner) {
inner = false;
return input;
} else {
inner = true;
return -input;
}
}
其他回答
使用复数,您可以有效地将否定数字的任务分为两个步骤:
将n乘以i,得到n*i,n逆时针旋转90°再乘以i,得到-n
最棒的是,您不需要任何特殊的处理代码。只要乘以i就可以了。
但不允许使用复数。因此,您必须使用部分数据范围创建自己的虚拟轴。由于需要的虚(中间)值与初始值一样多,因此只剩下一半的数据范围。
我试图在下图中显示这一点,假设有符号的8位数据。您必须将其缩放为32位整数。初始n的允许范围为-64到+63。下面是函数对正n的作用:
如果n在0..63(初始范围)内,函数调用将添加64,将n映射到范围64..127(中间范围)如果n在64..127(中间范围)内,则函数从64中减去n,将n映射到范围0..-63
对于负n,函数使用中间范围-65..-128。
嗯,我既不是数学,也不是编程高手,但这不是很容易吗?
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):
if isinstance(n, list):
return -n[0]
else:
return [n,0]
n = 4
print f(f(n))
--output--
-4
本质上,函数必须将可用范围划分为大小为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)
另一个作弊解决方案。我们使用允许运算符重载的语言。然后我们让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