我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
以下情况如何:
int f (int n)
{
static bool pass = false;
pass = !pass;
return pass? n : -n;
}
其他回答
这个问题并没有说明函数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将为真。
显然,这种方法可以扩展到更大范围的数字。。。
我认为最大的可能范围是暗示模块化算术解决方案。在一些模基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)
int f( int n ){
return n==0?0:(n&1?n:-n)+(n<0?-1:1);
}
怎么样:
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));
}
另一个作弊解决方案。我们使用允许运算符重载的语言。然后我们让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