我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这将在非常广泛的数字范围内发挥作用:
static int f(int n)
{
int lastBit = int.MaxValue;
lastBit++;
int secondLastBit = lastBit >> 1;
int tuple = lastBit | secondLastBit;
if ((n & tuple) == tuple)
return n + lastBit;
if ((n & tuple) == 0)
return n + lastBit;
return -(n + lastBit);
}
我最初的方法是使用最后一位作为检查位,以了解我们在第一次或第二次调用中的位置。基本上,我会在第一次调用后将此位设置为1,以向第二次调用发出第一次调用已经通过的信号。但是,这种方法被负数所击败,负数的最后一位在第一次调用期间已经到达1。
同样的理论适用于大多数负数的倒数第二位。但是,通常发生的情况是,大多数情况下,最后一位和第二位是相同的。它们要么都是负数的1,要么都是正数的0。
所以我的最后一个方法是检查它们是否都是1或都是0,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。
其他回答
类似于python中的函数重载解决方案:
def f(number):
if type(number) != type([]):
return [].append(number)
else:
return -1*number[0]
备选方案:静态数据成员
f#中的简单解决方案(不使用“技巧”)
let rec f n =
if n = 0 then 0
elif n > 0 then
if (f (n - 1) <> n) then n + 1
else -(n - 1)
else
if (f (-(n - 1)) = n) then n - 1
else -(n + 1)
嗯,我既不是数学,也不是编程高手,但这不是很容易吗?
int f(int i) {
static bool b;
if (b) {
b = !b;
return i;
} else {
b = !b;
return -i;
}
}
用大小正值和负值INT_MIN、INT_MAX进行测试,似乎可以。。。如果这是一个问题,可以使线程安全,但这不是任务的一部分。
或者我错过了什么?
怎么样:
f(n) = sign(n) - (-1)ⁿ * n
在Python中:
def f(n):
if n == 0: return 0
if n >= 0:
if n % 2 == 1:
return n + 1
else:
return -1 * (n - 1)
else:
if n % 2 == 1:
return n - 1
else:
return -1 * (n + 1)
Python自动将整数提升为任意长度的longs。在其他语言中,最大的正整数将溢出,因此它将适用于除该整数之外的所有整数。
为了使其适用于实数,您需要替换(-1)中的nⁿ 如果n>0,则为{上限(n);如果n<0},则为下限(n)。
在C#中(适用于任何双精度,溢出情况除外):
static double F(double n)
{
if (n == 0) return 0;
if (n < 0)
return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
else
return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}
下面是一个简短的Python答案:
def f(n):
m = -n if n % 2 == 0 else n
return m + sign(n)
一般情况
稍微调整一下上面的内容就可以处理我们希望k个自调用否定输入的情况——例如,如果k=3,这意味着g(g(g)n))=-n:
def g(n):
if n % k: return n + sign(n)
return -n + (k - 1) * sign(n)
这是通过将0保留在适当位置并创建长度为2*k的循环来实现的,因此,在任何循环中,n和-n之间的距离为k。具体来说,每个周期如下:
N * k + 1, N * k + 2, ... , N * k + (k - 1), - N * k - 1, ... , - N * k - (k - 1)
或者,为了更容易理解,这里是k=3的示例循环:
1, 2, 3, -1, -2, -3
4, 5, 6, -4, -5, -6
这组循环最大化了在任何以零为中心的机器类型(如有符号int32或有符号int64类型)内工作的输入范围。
兼容范围分析
映射x->f(x)实际上必须形成长度为2*k的循环,其中x=0是特殊情况下的1-长度循环,因为-0=0。因此,一般k的问题是可解的,当且仅当输入-1(补偿0)的范围是2*k的倍数,并且正负范围是相反的。
对于有符号整数表示,我们总是有一个最小的负数,在该范围内没有正的对应项,因此该问题在整个范围内变得不可解决。例如,有符号字符的范围为[-128127],因此在给定范围内f(f(-128))=128是不可能的。