我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
F#
let f n =
match n with
| n when n % 2 = 0 -> -n + System.Math.Sign n
| _ -> n - System.Math.Sign -n
其中n使得System.Int32.MinValue<n<System.Int32.MaxValue。
其他回答
上述问题不要求函数只能接受32位整数,只要求给定的n是32位整数。
红宝石:
def f( n )
return 0 unless n != 0
( n == n.to_i ) ? 1.0 / n : -(n**-1).to_i
end
使用全局。。。但事实如此?
bool done = false
f(int n)
{
int out = n;
if(!done)
{
out = n * -1;
done = true;
}
return out;
}
创建许多解的一种方法是注意,如果我们将整数划分为两个集合S和R
那么我们可以如下创建f:
如果x在R中,则f(x)=g(x)
如果x在S中,则f(x)=-invg(x)
其中invg(g(x))=x,所以invg是g的逆函数。
上面提到的第一个解决方案是分区R=偶数,R=奇数,g(x)=x+1。
我们可以取任意两个无限集合T,P s.T T+U=整数集合,取s=T+(-T),R=U+(-U)。
然后-S=S和-R=R通过它们的定义,我们可以将g取为从S到R的任何1-1对应关系,这必须存在,因为这两个集合都是无限的和可数的。
因此,这将为我们提供许多解决方案,但并非所有解决方案都可以编程,因为它们不会被有限地定义。
例如:
R=可被3整除的数字,S=不可被3除的数字。
然后我们取g(6r)=3r+1,g(6r+3)=3r+2。
这个问题并没有说明函数f的输入类型和返回值必须是什么(至少不是你给出的方式)。。。
…只是当n是32位整数时,f(f(n))=-n
那么,怎么样
Int64 f(Int64 n)
{
return(n > Int32.MaxValue ?
-(n - 4L * Int32.MaxValue):
n + 4L * Int32.MaxValue);
}
如果n是32位整数,则语句f(f(n))==-n将为真。
显然,这种方法可以扩展到更大范围的数字。。。
作为一名数学家,我想分享我对这个有趣问题的看法。我认为我有最有效的解决方案。
如果我没记错的话,只需翻转第一位,就可以将有符号的32位整数取反。例如,如果n=1001 1101 1110 1011 1110 0000 1110 1010,则-n=0001 1101 11101 1011 11100 0000 1110 010。
那么,我们如何定义一个函数f,它接受一个带符号的32位整数,并返回另一个有符号的32位数整数,该函数的属性是:接受两次f与翻转第一位相同?
让我重新表述这个问题,而不提整数之类的算术概念。
我们如何定义一个函数f,它接受长度为32的一系列0和1,并返回长度相同的一系列零和1,同时具有两次接受f与翻转第一位相同的性质?
观察:如果你能回答32位情况的上述问题,那么你也可以回答64位情况、100位情况等。你只需将f应用于前32位。
现在,如果你能回答2位案例的问题,哇!
是的,改变前2位就足够了。
这是伪代码
1. take n, which is a signed 32-bit integer.
2. swap the first bit and the second bit.
3. flip the first bit.
4. return the result.
备注:步骤2和步骤3可以概括为(a,b)-->(-b,a)。看起来很眼熟?这应该会让你想起平面的90度旋转以及乘以-1的平方根。
如果我只是单独展示了伪代码,而没有冗长的前奏,那么它看起来就像脱口而出的兔子,我想解释一下我是如何得到解决方案的。