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

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

有什么想法吗?


当前回答

这个怎么样:

do
    local function makeFunc()
        local var
        return function(x)
            if x == true then
                return -var
            else
                var = x
                return true
            end
        end

    end
    f = makeFunc()
end
print(f(f(20000)))

其他回答

这里有一个解决方案,其灵感来自于不能使用复数来解决这个问题的要求或声明。

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

(18494364652+1)模(232-3)=0。

这几乎和平方根为-1一样好。函数的结果必须是有符号整数。因此,我将使用一个修改的模运算mods(x,n),它返回与x模n最接近0的整数y。只有极少数编程语言能够成功地进行模运算,但它很容易被定义。例如,在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)

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

利用JavaScript异常。

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

f(f(0))=>0f(f(1))=>-1

这个想法已经在其他答案中使用过,但我把它融入了Python的一行:

def f(n):
    return str(n) if type(n) == int else -int(n)

C函数:

int f(int n) /* Treats numbers in the range 0XC0000000 to 0X3FFFFFFF as valid to
                generate f(f(x)) equal to -x. If n is within this range, it will
                project n outside the range. If n is outside the range, it will
                return the opposite of the number whose image is n. */
{
    return n ? n > 0 ? n <= 0X3FFFFFFF ? 0X3FFFFFFF + n : 0X3FFFFFFF - n :\
           n >= 0XC0000000 ? 0XC0000000 + n : 0XC0000000 - n : 0;
}

Ideone测试和下载链接

少于50个字符(C#)

int f(int n) { return (n <= 0) ? n : f(-n); }

或更容易阅读:

static int f(int n) { 
  if (n <= 0)
    return n;
  else 
    return f(-n);
}

要测试

static void Main(string[] args) {
    for (int n = int.MinValue; n < int.MaxValue; n+=1) {
        Console.Out.WriteLine("Value: " + n + " Result: " + f(f(n)));
    }
}

它有效(假设我正确理解问题)