我在上次面试中遇到的一个问题是:

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

在Python中

f=lambda n:n[0]if type(n)is list else[-n]

其他回答

PHP,不使用全局变量:

function f($num) {
  static $mem;

  $answer = $num-$mem;

  if ($mem == 0) {
    $mem = $num*2;
  } else {
    $mem = 0;
  }

  return $answer;
}

适用于整数、浮点数和数字字符串!

只是意识到这会做一些不必要的工作,但是,不管怎样

我承认我会作弊,但还是符合要求。这是编程魔术,而不是数学。它适用于整个范围,-2^31除外。

int f(int n)
{
    static bool eFlag = false; // Only executed once
    eFlag = !eFlag;
    return eFlag?-n:n;
}

事实上,这些问题更多的是关于面试官与规范、设计、错误处理、边界案例以及为解决方案选择合适的环境等进行斗争,而不是关于实际解决方案。然而::)

这里的函数是围绕封闭的4循环思想编写的。如果函数f只允许落在有符号的32位整数上,那么上面的各种解决方案都将起作用,除了其他人指出的三个输入范围数。minint永远不会满足函数方程,因此如果这是一个输入,我们将引发一个异常。

在这里,我允许Python函数操作并返回元组或整数。任务规范承认这一点,它只指定函数的两个应用程序应该返回一个与原始对象相等的对象,如果它是int32。(我会询问有关规范的更多细节)

这使得我的轨道可以很好且对称,并且可以覆盖所有输入整数(minint除外)。我最初设想的循环是访问半整数值,但我不想陷入舍入错误。因此是元组表示。这是一种将复杂旋转作为元组隐藏的方式,而不使用复杂的算术机制。

注意,在调用之间不需要保留任何状态,但调用者确实需要允许返回值为元组或int。

def f(x) :
  if isinstance(x, tuple) :
      # return a number.
      if x[0] != 0 :
        raise ValueError  # make sure the tuple is well formed.
      else :
        return ( -x[1] )

  elif isinstance(x, int ) :
    if x == int(-2**31 ):
      # This value won't satisfy the functional relation in
      # signed 2s complement 32 bit integers.
      raise ValueError
    else :
      # send this integer to a tuple (representing ix)
      return( (0,x) )
  else :
    # not an int or a tuple
    raise TypeError

因此,将f应用于37两次得到-37,反之亦然:

>>> x = 37
>>> x = f(x)
>>> x
(0, 37)
>>> x = f(x)
>>> x
-37
>>> x = f(x)
>>> x
(0, -37)
>>> x = f(x)
>>> x
37

将f两次应用于零得到零:

>>> x=0
>>> x = f(x)
>>> x
(0, 0)
>>> x = f(x)
>>> x
0

我们处理一个问题没有解决方案的情况(在int32中):

>>> x = int( -2**31 )
>>> x = f(x)

Traceback (most recent call last):
  File "<pyshell#110>", line 1, in <module>
    x = f(x)
  File "<pyshell#33>", line 13, in f
    raise ValueError
ValueError

如果你认为函数通过模拟乘以i的90度旋转打破了“无复杂算术”规则,我们可以通过扭曲旋转来改变这一点。这里元组表示半整数,而不是复数。如果你在数字线上追踪轨道,你会得到满足给定函数关系的非相交循环。

f2: n -> (2 abs(n) +1, 2 sign( n) ) if n is int32, and not minint.
f2: (x, y) -> sign(y) * (x-1) /2  (provided y is \pm 2 and x is not more than 2maxint+1

练习:通过修改f来实现这个f2。还有其他解决方案,例如,中间着落点是有理数而不是半整数。有一个分数模块可能很有用。你需要一个符号函数。

这个练习让我真正体会到了动态类型语言的乐趣。我在C中看不到这样的解决方案。

Clojure解决方案:

(defmacro f [n]
  (if (list? n) `(- ~n) n))

也适用于任何大小的正整数和负整数、双整数和比率!

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

我认为这不是一个很好的主意。