我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
我有另一个解决方案,它可以在一半时间内工作:
def f(x):
if random.randrange(0, 2):
return -x
return x
其他回答
这里有一个解决方案,其灵感来自于不能使用复数来解决这个问题的要求或声明。
乘以-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位整数。
C++解决方案;
long long f(int n){return static_cast <long long> (n);}
int f(long long n){return -static_cast <int> (n);}
int n = 777;
assert(f(f(n)) == -n);
C#重载:
string f(int i) {
return i.ToString();
}
int f(string s) {
return Int32.Parse(s) * -1;
}
Or
object f(object o) {
if (o.ToString.StartsWith("s"))
return Int32.Parse(s.Substring(1)) * -1;
return "s" + i.ToString();
}
怎么样:
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));
}
这个怎么样(C语言):
int f(int n)
{
static int t = 1;
return (t = t ? 0 : 1) ? -n : n;
}
刚刚试过,而且
f(f(1000))
回报-1000
f(f(-1000))
返回1000
这是正确的还是我没有抓住重点?