我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
int f( int n ){
return n==0?0:(n&1?n:-n)+(n<0?-1:1);
}
其他回答
int func(int a)
{
static int p = 0;
int ret = a;
if ( p ) ret *= -1;
p ^= 1;
return ret;
}
这个怎么样?
int nasty(int input)
{
return input + INT_MAX/2;
}
int j = 0;
void int f(int n)
{
j++;
if(j==2)
{
j = 0;
return -n;
}
return n;
}
:D
我参加这个聚会迟到了,现在可能是墓地了。但我有两个贡献,灵感来自viraptor先前使用lambda的Python答案。读者可能认为该解决方案仅在非类型化语言中可行,而在类型化语言中将需要一些明确的额外标记。
但下面是Haskell中的解决方案1(我不是Haskell专家)。它有点作弊,因为从技术上讲,两个f是两个不同的实现。(一个f::Int->()->Int,另一个f::(()->Int)->Int)
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}
module Main where
class Tran σ τ | σ -> τ where
tran :: σ -> τ
instance Tran Int (() -> Int) where
tran n = \_ -> (-n)
instance Tran (() -> Int) Int where
tran g = g ()
f :: Tran σ τ => σ -> τ
f = tran
main :: IO ()
main = do
print $ f (f (42 :: Int)) -- --> -42
print $ f (f (0 :: Int)) -- --> 0
print $ f (f (-69 :: Int)) -- --> 69
接下来是Typed Racket中的解决方案2。这一个满足了最大可能域的属性,因为Racket中的Number最多包含复数:
#lang typed/racket
(: f (case->
[Number -> (-> Number)]
[(-> Number) -> Number]))
(define (f x)
(if (number? x) (λ () (- x)) (x)))
(f (f 42)) ; --> -42
(f (f 0)) ; --> 0
(f (f -69)) ; --> 69
(f (f 3/4)) ; --> -3/4
(f (f 8+7i)) ; --> -8-7i
一个C++版本,可能会稍微改变规则,但适用于所有数值类型(浮点、整型、双精度),甚至是重载一元负号的类类型:
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;
}