设计函数f(f(n))== -n

2019/12/17 21:34
阅读数 62

来源:厦门SEO

我上次面试时遇到的一个问题:

设计一个函数f ,使得:

f(f(n)) == -n

其中n是一个32位有符号整数 ; 您不能使用复数算法。

如果您不能为整个数字范围设计这样的函数,请为最大范围设计它。

有任何想法吗?


#1楼

x86 asm(AT&T风格):

; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
    testl   %edi, %edi
    je  .zero

    movl    %edi, %eax
    movl    $1, %ecx
    movl    %edi, %edx
    andl    $1, %eax
    addl    %eax, %eax
    subl    %eax, %ecx
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edx
    subl    %edx, %eax
    imull   %ecx, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    imull   %ecx, %eax
.zero:
    xorl    %eax, %eax
    ret

检查代码,传递所有可能的32位整数,错误-2147483647(下溢)。


#2楼

该Perl解决方案适用于整数,浮点数和字符串 。

sub f {
    my $n = shift; return ref($n) ? -$$n : \$n; } 

尝试一些测试数据。

print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar'; 

输出:

-2 2
0 0
1 -1 1.1 -1.1 -3.3 3.3 foo -foo -bar +bar 

#3楼

没有人说过f(x)必须是同一类型。

def f(x):
    if type(x) == list: return -x[0] return [x] f(2) => [2] f(f(2)) => -2 

#4楼

这是受要求启发的解决方案,或声称不能使用复数来解决此问题。

乘以-1的平方根是一个想法,这似乎只是失败了,因为-1在整数上没有平方根。 但是,使用诸如mathematica之类的程序可以得出以下等式

(1849436465 2 +1)mod(2 32 -3)= 0。

这几乎与平方根为-1一样好。 该函数的结果必须是一个有符号整数。 因此,我将使用修改后的模运算mods(x,n),它返回与最接近0的x模n一致的整数y。只有极少数的编程语言具有suc模运算,但是很容易定义。 例如在python中,它是:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n return y 

使用上面的方程,现在可以解决问题

def f(x):
    return mods(x*1849436465, 2**32-3) 

对于[-2 31 -2, 2 31 -2]范围内的所有整数,满足f(f(x)) = -x 。 f(x)结果也在此范围内,但是计算当然需要64位整数。


#5楼

利用JavaScript异常。

function f(n) {
    try { return n(); } catch(e) { return function() { return -n; }; } } 

f(f(0)) => 0

f(f(1)) => -1

 
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部