我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
MIN_INT不会失败:
int f(n) { return n < 0 ? -abs(n + 1) : -(abs(n) + 1); }
其他回答
MIN_INT不会失败:
int f(n) { return n < 0 ? -abs(n + 1) : -(abs(n) + 1); }
这是一个C/C++解决方案,它不使用任何按位运算符,也不需要任何数学库,尽管这有点作弊。。。
double f(double n)
{
if (n == (double)(int)n)
return n + 0.5;
else
return -(n - 0.5);
}
这适用于所有32位整数,只有一个异常0x80000000(因为它的相反值不能存储在32位整数系统中)。f(f(n))==-n将始终为真,除非在这种情况下。
不过,我相信有一种更简单、更快的方法来实现它。这只是我第一个想到的。
这里有一个解决方案,其灵感来自于不能使用复数来解决这个问题的要求或声明。
乘以-1的平方根是一个想法,但似乎失败了,因为-1没有整数的平方根。但是,使用mathematica这样的程序可以得出如下公式
(18494364652+1)模(232-3)=0。
这几乎和平方根为-1一样好。函数的结果必须是有符号整数。因此,我将使用一个修改的模运算mods(x,n),它返回与x模n最接近0的整数y。只有极少数编程语言能够成功地进行模运算,但它很容易被定义。例如,在python中,它是:
def mods(x, n):
y = x % n
if y > n/2: y-= n
return y
使用上面的公式,问题现在可以解决为
def f(x):
return mods(x*1849436465, 2**32-3)
对于[-231-2231-2]范围内的所有整数,这满足f(f(x))=-x。f(x)的结果也在这个范围内,但当然计算需要64位整数。
这个问题并没有说明函数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将为真。
显然,这种方法可以扩展到更大范围的数字。。。
记住你的上一个状态不是一个足够好的答案吗?
int f (int n)
{
//if count
static int count = 0;
if (count == 0)
{
count = 1;
return n;
}
if (n == 0)
return 0;
else if (n > 0)
{
count = 0;
return abs(n)*(-1);
}
else
{
count = 0;
return abs(n);
}
}
int main()
{
int n = 42;
std::cout << f(f(n))
}