math - 面试问题 f( f( n ) ) == - n

  显示原文与译文双语对照的内容

我上次面试时遇到的一个问题:

设计一个函数 f,这样:

 
f(f(n)) == -n

 

其中 n 是一 32位有符号整数 ;你不能使用复数算术。

如果你不能为整个数字范围设计这样的函数,那么可以设计为尽可能大的范围。

有什么想法吗?

时间:

怎么办:

f(n) = sign(n) - (-1)n * 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 自动将整数提升到任意长度。 在其他语言中,最大正整数将溢出,因此它将适用于所有整数,除了。


在( -1 ),实数部分,使之能在你需要更换 n n 打开方式 { ceiling(n) if n>0; floor(n) if n<0 }

在 C# ( 适用于任何 double,但在溢出情况除外) 中:


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));
}

你没有说他们需要什么样的语言。。 这是一个静态解决方案( Haskell ) 。 它基本上搞乱了 2个最重要的位:


f :: Int -> Int
f x | (testBit x 30/= testBit x 31) = negate $ complementBit x 30
 | otherwise = complementBit x 30

在动态语言( python ) 中更容易。 检查参数是否为数字,返回返回-X的lambda:


def f(x):
 if isinstance(x,int):
 return (lambda: -x)
 else:
 return x()

这里有一个证明为什么这样一个函数不能存在的证明,如果它不使用额外的information(except 32 bits of int):

我们必须有 f(0) = 0. ( 证明:假设 f(0) = x 。 然后 f(x) = f(f(0)) = -0 = 0. 现在,-x = f(f(x)) = f(0) =,这意味着x = 0.

此外,对于任何 xy,假设 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个数字。 ( 但这只是一个愚蠢的假设)

感谢 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));
}

或者,你可以滥用预处理器:


#define f(n) (f##n)
#define ff(n) -n

int main()
{
 int n = -42;
 cout <<"f(f(" <<n <<")) =" <<f(f(n)) <<endl;
}

对于所有负数都是真的。

 f(n) = abs(n)

因为现在还有一个负数数大于的正数的二进制补码整数,一年多的f(n) = abs(n) 是有效的情况下比 f(n) = n> 0? -n : nf(n) = -abs(n) 相同的解决方案。 找到你了。。 :

更新

不不是对一个案例更多,因为我只是被litb的评论。识别。有效。 abs(Int.Min) 将溢出。。

我也想使用 mod 2信息,但结论是,它不工作。 于所有号码除了 Int.Min 相关,因为这将overflow,可以早些来。如果使用得当,它将工作

更新

在one,我还调整了一下这一段时间,想找一个漂亮的位操作骗局,可是却找不到一个很好的mod 2解决方案 fits. one-liner,而

 f(n) = 2n(abs(n) % 2) - n + sgn(n)

在 C# 中,这将成为以下内容:


public static Int32 f(Int32 n)
{
 return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

要使它为所有值工作,你必须用 (n> 0)? +n : -n 并在 unchecked 块中包含计算。 然后你甚至会把 Int.Min 映射为未经检查的否定。

更新

由另一个答案启发,我将解释函数如何工作以及如何构造这样一个函数。

让我们从头开始开始。 函数 f 被重复应用到给定值 n,产生一系列值。

 n => f(n) => f(f(n)) => f(f(f(n))) => f(f(f(f(n)))) =>.. .

问题需要 f(f(n)) = -n,这是 f的两个连续的应用,否定了参数。 f的两个进一步应用总共有4 个- - 否定了参数再次产生 n

 n => f(n) => -n => f(f(f(n))) => n => f(n) =>.. .

现在有一个明显的长度为4的周期。 替换 x = f(n) 并注意得到的方程式 f(f(f(n))) = f(f(x)) = -x 保留,生成以下结果。

 n => x => -n => -x => n =>.. .

所以我们得到了一个长度为4的循环,两个数字和两个数字是可逆的。 如果你把循环想象成一个矩形,那么反数值就位于相反的拐角。

构建这样一个循环的众多解决方案之一是从n 开始。

 n => negate and subtract one
-n - 1 = -(n + 1) => add one
-n => negate and add one
 n + 1 => subtract one
 n

一个具体的例子是这样一个循环 +1 => -2 => -1 => +2 => +1 基本上已经完成了时指出,甚至所构造的循环包含一个诡异的正数,它的后继项目,它和两数取反,我们可以轻松地将整数分区到很多这样周期( 2^32 是四的倍数) 并且已经找到一个函数这个满足上条件。

但我们有一个问题,零。 循环必须包含 0 => x => 0 因为零被否定为自身。 因为循环状态已经是 0 => x,所以它遵循 0 => x => 0 => x 经过两个应用程序,而不是尿到这只是一个周期的长度两个然后 x 可以转换为 itself. 幸运的是,有一个案例可以解决这个问题。 如果 x 等于零,我们得到一个长度为零的循环周期,我们解决了这个问题,结果是零是 f的一个固定点。

做了什么差不多了我们 2^32 数字,0 是一个不动点离开 2^32 - 1 数字和我们必须分区,数量为周期的四个数字。 糟糕, 2^32 - 1 不是4的倍数——仍将是三个数字没有任何周期长度的4.

我将解释解决方案的其余部分使用较小的组 3签署itegers从 -4+3 。 我们已经完成了零。 我们有一个完整的循环 +1 => -2 => -1 => +2 => +1 现在,我们来构建一个从 +3 开始的循环。

 +3 => -4 => -3 => +4 => +3

出现的问题是 +4 不能表示为 3位整数。 我们将通过否定 -3 获得 +4+3 ——仍然是一个有效的3位整数,然后添加一个 +3 ( 二进制 011 ) 收益率 100 二进制。 解释为无符号整数是 +4,但我们必须将它的解释为有符号整数 -4 。 所以实际上 -4 对于这个示例或 Int.MinValue 在一般情况下是第二定点整数算术否定—— 0Int.MinValue 映射到themselve。 所以循环实际上如下所示。

 +3 => -4 => -3 => -4 => -3

它是一个长度为二的循环,另外 +3 通过 -4 进入循环。 由于 -4 本身就是正确地映射到两个函数的应用程序后, +3 正确映射到 -3 两函数的应用程序,但 -3 本身就是错误地映射到在两个函数的应用程序。

所以我们构造了一个对所有整数都有效的函数,但一个。 我们能做得更好不,我们不能。 为什么?我们必须构建周期长度的4和能够覆盖整个整数范围内四值。 剩下的值是两个固定分 0Int.MinValue 必须映射到自己和两个任意整数 x-x 必须映射到彼此由两个函数的应用程序。

x 映射到 -x,反之亦然它们必须形成四个循环,并且它们必须位于循环的相反角。 因此 0Int.MinValue 必须在相反的拐角处。 这将正确映射 x-x,但在两个函数应用程序之后交换两个定点 0Int.MinValue,并将两个失败的输入留给我们。 所以不可能构造一个函数,它适用于所有的价值观,但我们有一个适用于所有值,只有一个除外,这是最好的我们可以实现。

使用复数,你可以有效地将一个数字的任务分为两个步骤:

  • 乘以n,得到 n*i,它是旋转 90 ° counter-clockwise
  • 再乘以我,你得到 -n

最棒的是你不需要任何特殊的处理代码。 我只是做了这个工作。

但是你不能使用复数。 所以你必须用你的数据区域的一部分来创建你自己的假想轴。 因为你需要尽可能多的假想( 中间) 值作为初始值,你只剩下一半的数据范围。

我试图在下图中可视化,假定签名的8 -bit数据。 你必须为 32位 整数缩放。 初始n的允许范围为 -64到 +63 。 下面是函数对正数的作用:

  • 如果n 在 0.。63 ( 初始范围),函数调用将 64添加到范围 64到范围。127 ( 中间范围)
  • 如果n 在 64.127 ( 中间范围),函数从 64减去n,映射n 到范围 0.-63

对于负数,函数使用中间范围 -65.。-128.

alt text

除 int.MaxValue 和 int.MinValue 以外的工作


 public static int f(int x)
 {

 if (x == 0) return 0;

 if ((x % 2)!= 0)
 return x * -1 + (-1 *x)/(Math.Abs(x));
 else
 return x - x/(Math.Abs(x));
 }

pictorial

这个问题并没有说任何有关的输入函数的类型和返回值什么 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 将是真。

显然,这种方法可以扩展为更广泛的数字。

根据你的平台,某些语言允许你在函数中保持状态。 VB.Net,例如:


Function f(ByVal n As Integer) As Integer
 Static flag As Integer = -1
 flag *= -1

 Return n * flag
End Function

IIRC,C++ 也允许这样。 我怀疑他们在寻找一个不同的解决方案。

另一个想法是,因为它们没有定义函数第一次调用的结果,所以你可以使用奇数/均匀度来控制是否反转符号:


int f(int n)
{
 int sign = n>=0?1:-1;
 if (abs(n)%2 == 0)
 return ((abs(n)+1)*sign * -1;
 else
 return (abs(n)-1)*sign;
}

将一个数添加到所有偶数的大小,从所有奇数的大小中减去一个。 两个调用的结果有相同的大小,但在一个调用中,我们交换了符号。 在某些情况下,这将无法工作( -1,最大或者最小 int ),但它比其他任何建议的工作都要好很多。

...