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

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

有什么想法吗?


当前回答

由于C++中的重载:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}

其他回答

这个问题并没有说明函数f的输入类型和返回值必须是什么(至少不是你给出的方式)。。。

…只是当n是32位整数时,f(f(n))=-n

那么,怎么样

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

如果n是32位整数,则语句f(f(n))==-n将为真。

显然,这种方法可以扩展到更大范围的数字。。。

number f( number n)
{
  static count(0);
  if(count > 0) return -n;
  return n;
}

f(n) = n

f(f(n)) = f(n) = -n

在awk中,由于几乎没有任何信息被传递,因此必须求助于允许将状态信息作为函数返回的一部分传递的方法,而不会危及传递内容的可用性:

jot - -5 5 | mawk 'function _(__,___) { 

     return (__~(___=" ")) \
      \
      ? substr("",sub("^[ ]?[+- ]*",\
        substr(" -",__~__,index("_"___,___)-\
              (__~"[-]")),__))\
            (__~"[-]"?"":___)__\
      : (+__<-__?___:(___)___)__ 

  } BEGIN { CONVFMT=OFMT="%.17g" 
  } { 
      print "orig",           +(__=$(__<__))<-__?__:" "__,
            "f(n)....",        _(__),_(_(__)),_(_(_(__))),
                         _(_(_(_(__)))), _(_(_(_(_(__))))) 

  }' |gcat -n | lgp3 5 

 1  orig -5 f(n)....  -5   5  -5   5  -5
 2  orig -4 f(n)....  -4   4  -4   4  -4
 3  orig -3 f(n)....  -3   3  -3   3  -3
 4  orig -2 f(n)....  -2   2  -2   2  -2
 5  orig -1 f(n)....  -1   1  -1   1  -1

 6  orig  0 f(n)....   0  -0   0  -0   0
 7  orig  1 f(n)....   1  -1   1  -1   1
 8  orig  2 f(n)....   2  -2   2  -2   2
 9  orig  3 f(n)....   3  -3   3  -3   3
10  orig  4 f(n)....   4  -4   4  -4   4

11  orig  5 f(n)....   5  -5   5  -5   5

因此,这样做的限制是,只有整数或浮点值已经是字符串格式,可以在没有风险的情况下使用,因为额外的ASCII空间\040作为状态信息

这种方法的优点是

它愿意为您提供“负零”,对于绝对值小于2^53的整数,简单地添加加号,即+f(f(_))函数调用本身将具有隐式代表您完成类型铸造,结果值将再次为数字对于大整数,只需减去()任何前导空格轻松处理大整数,而不会丢失精度从类型转换为双精度浮点

`

    1   orig -99999999999999999999999999999999 
        f(n).... 
             -99999999999999999999999999999999   
              99999999999999999999999999999999
             -99999999999999999999999999999999   
              99999999999999999999999999999999  
             -99999999999999999999999999999999

 2  orig      -1239999999999999999999999999999 
    f(n)....  -1239999999999999999999999999999                   
               1239999999999999999999999999999
              -1239999999999999999999999999999
               1239999999999999999999999999999
              -1239999999999999999999999999999`

使用全局。。。但事实如此?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}

下面是一个简短的Python答案:

def f(n):
  m = -n if n % 2 == 0 else n
  return m + sign(n)

一般情况

稍微调整一下上面的内容就可以处理我们希望k个自调用否定输入的情况——例如,如果k=3,这意味着g(g(g)n))=-n:

def g(n):
  if n % k: return n + sign(n)
  return -n + (k - 1) * sign(n)

这是通过将0保留在适当位置并创建长度为2*k的循环来实现的,因此,在任何循环中,n和-n之间的距离为k。具体来说,每个周期如下:

N * k + 1, N * k + 2, ... , N * k + (k - 1), - N * k - 1, ... , - N * k - (k - 1)

或者,为了更容易理解,这里是k=3的示例循环:

1, 2, 3, -1, -2, -3
4, 5, 6, -4, -5, -6

这组循环最大化了在任何以零为中心的机器类型(如有符号int32或有符号int64类型)内工作的输入范围。

兼容范围分析

映射x->f(x)实际上必须形成长度为2*k的循环,其中x=0是特殊情况下的1-长度循环,因为-0=0。因此,一般k的问题是可解的,当且仅当输入-1(补偿0)的范围是2*k的倍数,并且正负范围是相反的。

对于有符号整数表示,我们总是有一个最小的负数,在该范围内没有正的对应项,因此该问题在整个范围内变得不可解决。例如,有符号字符的范围为[-128127],因此在给定范围内f(f(-128))=128是不可能的。