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

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

有什么想法吗?


当前回答

很简单,只需让f返回看起来等于任何整数的值,并且可以从整数转换。

public class Agreeable
{
    public static bool operator==(Agreeable c, int n)
        { return true; }

    public static bool operator!=(Agreeable c, int n)
        { return false; }

    public static implicit operator Agreeable(int n)
        { return new Agreeable(); }
}

class Program
{
    public static Agreeable f(Agreeable c)
        { return c; }

    static void Main(string[] args)
    {
        Debug.Assert(f(f(0)) == 0);
        Debug.Assert(f(f(5)) == -5);
        Debug.Assert(f(f(-5)) == 5);
        Debug.Assert(f(f(int.MaxValue)) == -int.MaxValue);
    }
}

其他回答

在C中,

int 
f(int n) {
     static int r = 0;
     if (r == 1) {r--; return -1 * n; };
     r++;
     return n;
}

知道这是为了什么语言会有帮助。我错过了什么吗?许多“解决方案”似乎过于复杂,坦率地说,并非如此工作(当我读到问题时)。

简单的Python解决方案之所以成为可能,是因为对f(x)应该输出的内容没有限制,只有f(f(x)):

def f(x):
    return (isinstance(x, tuple) and -x[0]) or (x,)

使用复数,您可以有效地将否定数字的任务分为两个步骤:

将n乘以i,得到n*i,n逆时针旋转90°再乘以i,得到-n

最棒的是,您不需要任何特殊的处理代码。只要乘以i就可以了。

但不允许使用复数。因此,您必须使用部分数据范围创建自己的虚拟轴。由于需要的虚(中间)值与初始值一样多,因此只剩下一半的数据范围。

我试图在下图中显示这一点,假设有符号的8位数据。您必须将其缩放为32位整数。初始n的允许范围为-64到+63。下面是函数对正n的作用:

如果n在0..63(初始范围)内,函数调用将添加64,将n映射到范围64..127(中间范围)如果n在64..127(中间范围)内,则函数从64中减去n,将n映射到范围0..-63

对于负n,函数使用中间范围-65..-128。

这是rossfabricant答案的C实现。注意,由于我始终使用32位整数,f(f(2147483647))==2147483648,而不是-2147483647。

int32_t f( int32_t n )
{
    if( n == 0 ) return 0;
    switch( n & 0x80000001 ) {
        case 0x00000000:
            return -1 * ( n - 1 );
        case 0x00000001:
            return n + 1;
        case 0x80000000:
            return -1 * ( n + 1 );
        default:
            return n - 1;
    }
}

如果您将问题定义为允许f()接受并返回int64_t,则会涉及2147483647。当然,switch语句中使用的文字必须更改。

这里有一个我从未见过的变体。因为这是ruby,所以32位整数的东西就不见了(当然可以添加检查)。

def f(n)
    case n
    when Integer
        proc { n * -1 }
    when Proc
        n.call
    else
        raise "Invalid input #{n.class} #{n.inspect}"
    end
end

(-10..10).each { |num|
    puts "#{num}: #{f(f(num))}"
}