StackOverflow(http://stackoverflow.com/)最近有一个面试题(http://stackoverflow.com/questions/731832/interview-question-ffn-n)特别火爆:构造一个定义域和值域都是全体整数的函数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)……并对它们分别做类似的定义就可以了。
=================== 我是可爱的分割线 ===================
另一个类似的题目(http://stackoverflow.com/questions/732485/interview-question-ffx-1-x)则是要求你设计函数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/