我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这适用于1073741823至1073741822范围:
int F(int n)
{
if(n < 0)
{
if(n > -1073741824)
n = -1073741824 + n;
else n = -(n + 1073741824);
}
else
{
if(n < 1073741823)
n = 1073741823 + n;
else n = -(n - 1073741823);
}
return n;
}
它的工作原理是获取32位有符号整数的可用范围并将其一分为二。函数的第一次迭代将n自身置于该范围之外。第二次迭代检查它是否在该范围之外-如果是,则将其放回该范围内,但使其为负值。
这实际上是一种保留关于值n的额外“位”信息的方法。
其他回答
对于javascript(或其他动态类型语言),可以让函数接受int或对象,并返回另一个。即
function f(n) {
if (n.passed) {
return -n.val;
} else {
return {val:n, passed:1};
}
}
给
js> f(f(10))
-10
js> f(f(-10))
10
或者,您可以在强类型语言中使用重载,尽管这可能会破坏规则
int f(long n) {
return n;
}
long f(int n) {
return -n;
}
很简单,只需让f返回看起来等于任何整数的值,并且可以从整数转换。
public class Agreeable
{
public static bool operator==(Agreeable c, int n)
{ return true; }
public static bool operator!=(Agreeable c, int n)
{ return false; }
public static implicit operator Agreeable(int n)
{ return new Agreeable(); }
}
class Program
{
public static Agreeable f(Agreeable c)
{ return c; }
static void Main(string[] args)
{
Debug.Assert(f(f(0)) == 0);
Debug.Assert(f(f(5)) == -5);
Debug.Assert(f(f(-5)) == 5);
Debug.Assert(f(f(int.MaxValue)) == -int.MaxValue);
}
}
或者,您可以滥用预处理器:
#define f(n) (f##n)
#define ff(n) -n
int main()
{
int n = -42;
cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}
由于C++中的重载:
double f(int var)
{
return double(var);
}
int f(double var)
{
return -int(var);
}
int main(){
int n(42);
std::cout<<f(f(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)