您当前的位置:首页 > 学习 > 阅览室

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

时间:12-07来源:作者:点击数:
城东书院 www.cdsy.xyz

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/

城东书院 www.cdsy.xyz
方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门
本栏推荐