趣题：构造整数域上的函数f使得f(f(n))等于-n

    StackOverflow最近有一个面试题特别火爆：构造一个定义域和值域都是全体整数的函数f使得f(f(n)) = -n。如果你不能设计出函数对于所有n都成立，那就设计函数能够满足尽可能多的数。

    一些比较容易想到的解如：
if n > 0:
    return -n
else:
    return n
    不过这个函数只适用于所有非负整数。当然，这并不是我们的最优解。你还能想到更好的办法吗？


    在思考这个问题时，我想到了一个奇妙的解：找一个非常非常大的素数p，然后定义函数f(n)为
if n % p == 0:
    return - n / p
else:
    return n * p

    这个函数可以满足更多的数——只要n不含有因子p，函数总能使得f(f(n)) = -n。因此，取充分大的素数p，满足要求的整数可以任意多。

    StackOverflow上的网友给出了下面这个答案，它对所有整数均成立：
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)

    其实基本思想很简单：考虑四个数(a, b, -a, -b)。令f(a)=b, f(b)=-a, f(-a)=-b, f(-b)=a，则该函数对这四个数都满足要求。然后呢，只需要注意到函数对这四个数封闭，因此不断取(1, 2, -1, -2)、(3, 4, -3, -4)、(5, 6, -5, -6)……并对它们分别做类似的定义就可以了。

  =================== 我是可爱的分割线 ===================

    另一个类似的题目则是要求你设计函数f使得f(f(n)) = 1/n对所有实数都成立。解决办法也非常妙：
if n >= 0
    return -1/x
else:
    return -x

 
 
来源：http://techblog.zellux.czm.cn/2009/06/two-function-related-interview-questions/

30 条评论

发表评论

9  +  1  =