logo标签列表

Designing function f(f(n)) == -n

mathinteger
849

我上次面试时收到的一个问题：

设计一个函数f，使得：

f(f(n)) == -n

当 n 是一个32位的有符号整数时，你不能使用复数运算。

如果你不能为所有数字范围设计这样的函数，那就尽可能地为最大范围设计。

有什么想法吗？

6
这次面试是为了什么职位？ - tymtam
120个回答
46

根据你所使用的平台，有些语言允许在函数中保持状态。例如，VB.Net：

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

据我所知，C++ 也允许这样做。但我怀疑他们正在寻找另一种解决方案。

另一个思路是，既然它们没有定义函数的第一次调用的结果，您可以使用奇偶性来控制是否取反符号：

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

将所有偶数的大小加一，将所有奇数的大小减一。两次调用结果具有相同的大小，但在偶数调用中我们交换符号。虽然有一些情况这种方法行不通（-1，max或min int），但它比迄今为止提出的任何其他方法都要好。

1
我相信它适用于MAX_INT，因为那总是奇数。它不适用于MIN_INT和-1。 - Airsource Ltd
9
如果有副作用，它就不是一个函数。 - nos
12
在数学中或许如此，但在编程中无关紧要。所以问题是他们是在寻找数学解决方案还是编程解决方案。但考虑到这是一份编程工作的职位需求... - Ryan Lundy
+1 我本来打算用C语言发布一个带有"static int x"的实现FIFO并对输出进行否定的代码，但这个也差不多了。 - phkahler
2
@nos：是的，它只是不具有引用透明性。 - Clark Gaebel
@Randy 线程安全是在哪里要求的？但除此之外，你指的是哪个例子？我猜你说的是 VB.Net 的静态变量。在 VB 中，静态变量比 C++/C# 更复杂。VB.Net 编译函数内的静态变量时会使用 System.Threading.Monitor 类型进行锁定，因此它在某种程度上是线程安全的，而类似的 C++/C# 程序则不然……至少在两个线程同时访问该函数时如此。但是，如果你想同时跟踪多个数字，那么你是对的。但再次强调：我没有在需求列表中看到这一点。 - Joel Coehoorn
27

利用JavaScript异常。

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

f(f(0)) => 0

f(f(1)) => -1

我怀疑异常之前从未被这样使用过... :) - NoBugs
+1 超越常规的思维方式。很酷！但在生产代码中，我会使用 typeof 来确保安全。 - user235273
23

对于所有32位的值（注意-0为-2147483648）

int rotate(int x)
{
    static const int split = INT_MAX / 2 + 1;
    static const int negativeSplit = INT_MIN / 2 + 1;

    if (x == INT_MAX)
        return INT_MIN;
    if (x == INT_MIN)
        return x + 1;

    if (x >= split)
        return x + 1 - INT_MIN;
    if (x >= 0)
        return INT_MAX - x;
    if (x >= negativeSplit)
        return INT_MIN - x + 1;
    return split -(negativeSplit - x);
}

你基本上需要将每个 -x => x => -x 循环与一个 y => -y => y 循环配对。因此，我将 split 的相反侧配对在一起。

例如：4位整数：

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3
21

这是一个C++版本的代码，可能有些违反规则，但适用于所有数值类型（floats，ints，doubles）甚至是重载一元减号的类类型：

template <class T>
struct f_result
{
  T value;
};

template <class T>
f_result <T> f (T n)
{
  f_result <T> result = {n};
  return result;
}

template <class T>
T f (f_result <T> n)
{
  return -n.value;
}

void main (void)
{
  int n = 45;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
  float p = 3.14f;
  cout << "f(f(" << p << ")) = " << f(f(p)) << endl;
}
好主意。作为替代方案，您可能会失去结构体，而是让一个函数返回指针，另一个函数对其进行解引用并否定它。 - Imbue
20

x86汇编语言（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出现了错误（下溢）。

19

这个 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
但它不保持整数值。实质上，你是在将全局变量数据存储在整数 "n" 中... 只是它不是整数，否则你就无法这样做。例如，如果“n”是一个字符串，我可以使 548 成为 "First_Time_548"，然后下一次运行函数时... 如果 (prefix == 'First_Time_')，则用"-"替换 "First_Time_"。 - Albert Renshaw
@AlbertRenshaw 不确定你从哪里得到这些想法。(1) 这里绝对没有全局变量。(2) 如果你给函数一个整数，你会得到一个整数返回--或者是一个整数的引用，如果你调用函数奇数次。(3) 或许最基本的是，这是Perl。在实际应用中，整数和字符串是完全可互换的。看起来像数字的字符串在大多数情况下都可以作为数字正常运行，而数字也会在需要时愉快地转化为字符串。 - FMc
抱歉，我不太了解 Perl，看起来你在使用全局数组哈哈。 - Albert Renshaw
19

使用全局变量...那又怎样？

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}
3
不确定提问者的意图是否是如此，但对于“跳出思维定式”的想法点赞。 - Liran Orevi
5
你应该总是使用 "done = !done" 而不是有条件地使用 "done = true"，这样你的函数可以被多次使用。 - Chris Lutz
1
我的第一反应也是使用全局变量来解决这个问题，尽管在这个特定的问题中感觉有点像作弊。然而，我认为在问题的规格说明中，全局变量解决方案是最好的解决方案。使用全局变量使得理解正在发生的事情非常容易。我同意 done != done 更好，只需将其移动到 if 语句之外即可。 - Alderath
3
从定义上来讲，任何维护状态的东西都不是一个函数，而是一个状态机。根据定义，函数总是对于相同的输入产生相同的输出。 - Ted Hopp
@userunknown，无论如何都很荒谬...在这种情况下，线程安全甚至并不重要，因为“n”必须是一个全局变量才能正常工作。 - Albert Renshaw
显示剩余2条评论
18

没有人说f(x)必须是相同的类型。

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


f(2) => [2]
f(f(2)) => -2
16
这里有一个解决方案，受到了无法使用复数解决此问题的要求或声明的启发。
乘以负一的平方根是一个想法，只是似乎失败了，因为在整数范围内-1没有平方根。但是像Mathematica这样的程序给出了例如以下方程：
(1849436465²+1) mod (2^32−3) = 0.
这几乎就像拥有负一的平方根一样。函数的结果需要是一个有符号整数。因此，我将使用一个修改过的模运算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)

对于范围内所有整数，f(f(x)) = -x。 f(x) 的结果也在此范围内，但计算需要使用64位整数。

16

我希望你更改最高有效位的2个比特。

00.... => 01.... => 10.....

01.... => 10.... => 11.....

10.... => 11.... => 00.....

11.... => 00.... => 01.....

正如您所看到的，这只是一种加法，忽略了进位位。

我是怎么得出答案的呢？我的第一个想法只是需要对称性。需要4个转弯才能回到起点。起初我认为这是2位格雷码。然后我想实际上标准二进制就足够了。

这种方法的问题在于它不能处理二进制补码负数（这是现代CPU使用的方式）。这就是为什么我删除了我的相同答案。 - Tamas Czinege
该问题指定了32位有符号整数。这个解决方案不适用于32位有符号整数的二进制补码或反码表示法。它只适用于原码表示法，而这在现代计算机中非常罕见（除了浮点数）。 - Jeffrey L Whitledge
1
@DrJokepu - 哇，六个月后——不好意思！ - Jeffrey L Whitledge
你只需要在函数内将数字转换为符号-大小表示形式，执行变换，然后在返回之前将其转换回本机整数表示形式，不是吗？ - Bill Michell
我喜欢你通过引入虚数部分来实现复数的方式 :) - jabirali
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接