我在上次面试中遇到的一个问题是:
设计函数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++中想出一些邪恶的东西,希望不会上当受骗:
struct ImplicitlyConvertibleToInt
{
operator int () const { return 0; }
};
int f(const ImplicitlyConvertibleToInt &) { return 0; }
ImplicitlyConvertibleToInt f(int & n)
{
n = 0; // The problem specification didn't say n was const
return ImplicitlyConvertibleToInt();
}
整个ImplicitlyConvertableToInt类型和重载是必需的,因为临时变量不能绑定到非常量引用。
当然,现在来看它,f(n)是否在-n之前执行是不确定的。
对于这种程度的邪恶,也许一个更好的解决方案是:
struct ComparesTrueToInt
{
ComparesTrueToInt(int) { } // implicit construction from int
};
bool operator == (ComparesTrueToInt, int) const { return true; }
ComparesTrueToInt f(ComparesTrueToInt ct) { return ComparesTrueToInt(); }
创建许多解的一种方法是注意,如果我们将整数划分为两个集合S和R
那么我们可以如下创建f:
如果x在R中,则f(x)=g(x)
如果x在S中,则f(x)=-invg(x)
其中invg(g(x))=x,所以invg是g的逆函数。
上面提到的第一个解决方案是分区R=偶数,R=奇数,g(x)=x+1。
我们可以取任意两个无限集合T,P s.T T+U=整数集合,取s=T+(-T),R=U+(-U)。
然后-S=S和-R=R通过它们的定义,我们可以将g取为从S到R的任何1-1对应关系,这必须存在,因为这两个集合都是无限的和可数的。
因此,这将为我们提供许多解决方案,但并非所有解决方案都可以编程,因为它们不会被有限地定义。
例如:
R=可被3整除的数字,S=不可被3除的数字。
然后我们取g(6r)=3r+1,g(6r+3)=3r+2。
JavaScript单行:
function f(n) { return ((f.f = !f.f) * 2 - 1) * n; }
没有人说它必须是无国籍的。
int32 f(int32 x) {
static bool idempotent = false;
if (!idempotent) {
idempotent = true;
return -x;
} else {
return x;
}
}
作弊,但不如很多例子。更糟糕的是,查看堆栈以查看调用者的地址是否为-f,但这将更具可移植性(虽然不是线程安全的……线程安全版本将使用TLS)。更邪恶的是:
int32 f (int32 x) {
static int32 answer = -x;
return answer;
}
当然,对于MIN_INT32的情况,这两种方法都不太有效,但除非允许返回更宽的类型,否则对此您几乎无能为力。