我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
在C中,
int
f(int n) {
static int r = 0;
if (r == 1) {r--; return -1 * n; };
r++;
return n;
}
知道这是为了什么语言会有帮助。我错过了什么吗?许多“解决方案”似乎过于复杂,坦率地说,并非如此工作(当我读到问题时)。
其他回答
int f(int n)
{
static long counter=0;
counter++;
if(counter%2==0)
return -n;
else
return n;
}
下面是一个简短的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是不可能的。
从来没有人说过f(x)必须是同一类型。
def f(x):
if type(x) == list:
return -x[0]
return [x]
f(2) => [2]
f(f(2)) => -2
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。
它通过保存状态来作弊,但它有效,将操作分成两部分:-n=(~n+1)对于整数
int f(int n) {
static int a = 1;
a = !a;
if (a) {
return (~n);
} else {
return (n+1);
}
}