〖转贴〗技术面试题：f(f(n)) == -n

microblue 2009-05-25 05:55:36

加精

（转自博客园）

最近遇到的一个技术面试题，在这里分享一下。题目是设计一个函数 f，使得

f(f(n)) = -n

这里 n 是一个 32 比特的整数。不可以使用复数运算。

如果你无法设计出一个函数使得其对32比特下的所有整数都适用，那么设计此函数使得其能够适用于尽可能多的整数。

Design a function f, such that:

f(f(n)) == -n

Where n is a 32 bit signed integer; you can't use complex numbers arithmetic.

If you can't design such a function for the whole range of numbers, design it for the largest range possible.

...全文

1689 69 打赏收藏转发到动态举报

写回复

用AI写文章

69 条回复

切换为时间正序

请发表友善的回复…

发表回复

tianhe1314 2009-06-10

打赏
举报

学习中。。。

sxmonsy 2009-05-30

打赏
举报

留爪

zhangxun2007 2009-05-30

打赏
举报

这个函数是多元函数，但还不完善。

mingxuanxixi 2009-05-30

打赏
举报

顶

jlsp2005 2009-05-30

打赏
举报

学习中。。。。

gxj760998 2009-05-27

打赏
举报

小弟不才，这样想：
当f奇数次作用n时，返回其本身（或其相反数）；
当f偶数次作用n时，返回其相反数身（或其本身）；

你是可以这样想，但程序未必会这样做。
如果你用数学公司简单的推导下就知道错了！
既然f(n) = n,那么
ff(n) = -n，而f(n)= n，一替换就不行了。

zhangxun2007 2009-05-27

打赏
举报

小弟不才，这样想：
当f奇数次作用n时，返回其本身（或其相反数）；
当f偶数次作用n时，返回其相反数身（或其本身）；
从而，问题转化为：
确定f对n作用的次数的奇偶性，可以用静态变量表示。

static boolean a[4294967295];//默认值为false或赋值为true
static tiny f(tiny n)
{
int m=n+2147483648;
if(a[m]){a[m]=false;return -n;}
else {a[m]=true;return n;}
}

bbb332 2009-05-26

打赏
举报

好东西

ljp888 2009-05-26

打赏
举报

good

breezes2008 2009-05-26

打赏
举报

是个好题。关注

码农7号- 2009-05-26

打赏
举报

f(x)=0

wuyi8808 2009-05-26

打赏
举报

LZ的原题说：
[Quote=引用楼主 microblue 的帖子:]
如果你无法设计出一个函数使得其对32比特下的所有整数都适用，那么设计此函数使得其能够适用于尽可能多的整数。
If you can't design such a function for the whole range of numbers, design it for the largest range possible.
[/Quote]

显然，当n = -2147483648时不可能返回2147483648。
所以，应该努力使对于32位有符号整数范围内的其他n，f(f(n)) = -n。

wuyi8808 2009-05-26

打赏
举报

[Quote=引用 25 楼 cnzdgs 的回复:]
32位整数的范围是-2147483648 ~ 2147483647，所以2147483648没法表示。
可以再修改一下程序，当n = -2147483647时返回-2147483648，当n = -2147483648时返回-2147483647。
[/Quote]

当n = -2147483647时应该返回2147483647

当然，当n = -2147483648时不可能返回2147483648，因为不在32位有符号整数范围内，无论如何都是无法表示的，所以我在6楼说的是：不知能不能减少到一个值。

wuyi8808 2009-05-26

打赏
举报

这样，还是两个值ERROR:

using System;



class Program

{

  static void Main()

  {

    foreach (int n in new int[] { int.MinValue, 0, 1, 2, 3, int.MaxValue - 1, int.MaxValue, -1, -2, -3, int.MinValue+2, int.MinValue+1 })

    {

      Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));

      Console.Write((long)f(f(n)) == -(long)n ? "OK" : "ERROR");

      Console.WriteLine();

    }

  }

  

  static int f(int n)

  {

    if (n == 0) return -int.MaxValue;

    if (n == int.MaxValue) return 0;

    if ((n & 1) == 0) return Math.Sign(n) - n;

    return Math.Sign(n) + n;

  }

}

/* 程序输出：

n = -2147483648  f(n) = 2147483647   f(f(n)) = 0            ERROR

n = 0            f(n) = -2147483647  f(f(n)) = -2147483648  ERROR

n = 1            f(n) = 2            f(f(n)) = -1           OK

n = 2            f(n) = -1           f(f(n)) = -2           OK

n = 3            f(n) = 4            f(f(n)) = -3           OK

n = 2147483646   f(n) = -2147483645  f(f(n)) = -2147483646  OK

n = 2147483647   f(n) = 0            f(f(n)) = -2147483647  OK

n = -1           f(n) = -2           f(f(n)) = 1            OK

n = -2           f(n) = 1            f(f(n)) = 2            OK

n = -3           f(n) = -4           f(f(n)) = 3            OK

n = -2147483646  f(n) = 2147483645   f(f(n)) = 2147483646   OK

n = -2147483647  f(n) = -2147483648  f(f(n)) = 2147483647   OK

*/

不过，如果把 int.MinValue 当作“负零”来看待的话：

n = -2147483648  f(n) = 2147483647   f(f(n)) = 0            ERROR  // -2147483648 看作 -0

n = 0            f(n) = -2147483647  f(f(n)) = -2147483648  ERROR  // -2147483648 看作 -0

十八道胡同 2009-05-26

打赏
举报

顶，好贴

会思考的草 2009-05-26

打赏
举报

mark

cnzdgs 2009-05-26

打赏
举报

32位整数的范围是-2147483648 ~ 2147483647，所以2147483648没法表示。
可以再修改一下程序，当n = -2147483647时返回-2147483648，当n = -2147483648时返回-2147483647。

wuyi8808 2009-05-26

打赏
举报

请注意，6楼的说法是如果自变量和返回值都是int：

[Quote=引用 6 楼 wuyi8808 的回复:]
如果函数原形要求是：int f(int n)，也就是自变量和返回值都是int，
则有两个值是错的：int.MinValue 和 int.MaxValue，
不知能不能减少到一个值。
[/Quote]

要是这样换一种思路的话：

[Quote=引用 41 楼 guoyichao 的回复:]
换一种思路就能得到完美答案：
public static F f(int n)
{
}

public static int f(F a)
{
}
[/Quote]

那还不如用5楼的 long f(long n) 的方案。

ForestDB 2009-05-26

打赏
举报

既然是程序方面的技术题，个人想到的一个解法：
闭包，closure，这是计算机科学中一个很通用的概念，很多编程语言都有不同程度的支持
在C++中叫函数对象，functor，个人的理解从某种程度来说就是有状态的函数，不知道C#中有没有类似的行为
以下是简单的示例代码，可能有语法错误，但不影响想表达的内容



class foo {

  unsigned int i;

public:

  foo(): i(0) {} // 构造函数将i置0

  int operator()(int n) // 重载()运算符，即函数对象的必要条件

  {

    if (i++ % 2) // 根据内部i的状态，调用()时一次不变，一次取相反数，最后的效果总是两次调用会取相反数

      return n;

    else

      return -n;

  }

};



foo f;

int x;

f(f(x)) == -x;