我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这里有一个证明,如果不使用额外信息(除了32位的int),那么对于所有数字,这样的函数都不可能存在:
我们必须使f(0)=0。(证明:假设f(0)=x,则f(x)=f(f(0))=-0=0。现在,-x=f(f(x))=f(0)=x,这意味着x=0。)
此外,对于任何x和y,假设f(x)=y。那么我们希望f(y)=-x。并且f(f(y))=-y=>f(-x)=-y。总结一下:如果f(x)=y,那么f(-x)=-y,f(y)=-x,f(-y)=x。
因此,我们需要将除0之外的所有整数分成4个集合,但我们有奇数个这样的整数;不仅如此,如果我们去掉没有正对应的整数,我们仍然有2(mod4)个数。
如果我们去掉剩下的2个最大数(通过abs值),我们可以得到函数:
int sign(int n)
{
if(n>0)
return 1;
else
return -1;
}
int f(int n)
{
if(n==0) return 0;
switch(abs(n)%2)
{
case 1:
return sign(n)*(abs(n)+1);
case 0:
return -sign(n)*(abs(n)-1);
}
}
当然,另一种选择是不遵守0,并获得我们删除的2个数字作为奖励。(但这只是一个愚蠢的假设。)
其他回答
x86 asm(AT&T风格):
; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
testl %edi, %edi
je .zero
movl %edi, %eax
movl $1, %ecx
movl %edi, %edx
andl $1, %eax
addl %eax, %eax
subl %eax, %ecx
xorl %eax, %eax
testl %edi, %edi
setg %al
shrl $31, %edx
subl %edx, %eax
imull %ecx, %eax
subl %eax, %edi
movl %edi, %eax
imull %ecx, %eax
.zero:
xorl %eax, %eax
ret
代码已检查,所有可能的32位整数都已通过,错误为-2147483647(下溢)。
number f( number n)
{
static count(0);
if(count > 0) return -n;
return n;
}
f(n) = n
f(f(n)) = 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)
Scala中使用隐式转换的一个奇怪且唯一稍微聪明的解决方案:
sealed trait IntWrapper {
val n: Int
}
case class First(n: Int) extends IntWrapper
case class Second(n: Int) extends IntWrapper
case class Last(n: Int) extends IntWrapper
implicit def int2wrapper(n: Int) = First(n)
implicit def wrapper2int(w: IntWrapper) = w.n
def f(n: IntWrapper) = n match {
case First(x) => Second(x)
case Second(x) => Last(-x)
}
我认为这不是一个很好的主意。
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();
}