〖转贴〗技术面试题：f(f(n)) == -n解决方法
日期：2014-05-20 浏览次数：20964 次
〖转贴〗技术面试题：f(f(n)) == -n
（转自博客园）
最近遇到的一个技术面试题，在这里分享一下。题目是设计一个函数 f，使得
f(f(n)) = -n
这里 n 是一个 32 比特的整数。不可以使用复数运算。
如果你无法设计出一个函数使得其对32比特下的所有整数都适用，那么设计此函数使得其能够适用于尽可能多的整数。
Design a function f, such that:
f(f(n)) == -n
Where n is a 32 bit signed integer; you can't use complex numbers arithmetic.
If you can't design such a function for the whole range of numbers, design it for the largest range possible.
------解决方案--------------------
（转自博客园）
最近遇到的一个技术面试题，在这里分享一下。题目是设计一个函数 f，使得
f(f(n)) = -n
这里 n 是一个 32 比特的整数。不可以使用复数运算。
如果你无法设计出一个函数使得其对32比特下的所有整数都适用，那么设计此函数使得其能够适用于尽可能多的整数。
Design a function f, such that:
f(f(n)) == -n
Where n is a 32 bit signed integer; you can't use complex numbers arithmetic.
If you can't design such a function for the whole range of numbers, design it for the largest range possible.
------解决方案--------------------
- C# code
using System;
class Program
{
static void Main()
{
foreach (int n in new int[] { 0, 1, 2, 3, 4, 1000, 1001, -1, -2, -3, -4, -1000, -1001, int.MaxValue - 1, int.MinValue+1, int.MaxValue, int.MinValue })
{
Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
Console.Write((long)n == -(long)(f(f(n))) ? "OK" : "ERROR");
Console.WriteLine();
}
}
static long f(long n)
{
if ((n & 1) == 0) return -n + Math.Sign(n);
return n + Math.Sign(n);
}
}
/* 程序输出：
n = 0 f(n) = 0 f(f(n)) = 0 OK
n = 1 f(n) = 2 f(f(n)) = -1 OK
n = 2 f(n) = -1 f(f(n)) = -2 OK
n = 3 f(n) = 4 f(f(n)) = -3 OK
n = 4 f(n) = -3 f(f(n)) = -4 OK
n = 1000 f(n) = -999 f(f(n)) = -1000 OK
n = 1001 f(n) = 1002 f(f(n)) = -1001 OK
n = -1 f(n) = -2 f(f(n)) = 1 OK
n = -2 f(n) = 1 f(f(n)) = 2 OK
n = -3 f(n) = -4 f(f(n)) = 3 OK
n = -4 f(n) = 3 f(f(n)) = 4 OK
n = -1000 f(n) = 999 f(f(n)) = 1000 OK
n = -1001 f(n) = -1002 f(f(n)) = 1001 OK
n = 2147483646 f(n) = -2147483645 f(f(n)) = -2147483646 OK
n = -2147483647 f(n) = -2147483648 f(f(n)) = 2147483647 OK
n = 2147483647 f(n) = 2147483648 f(f(n)) = -2147483647 OK
n = -2147483648 f(n) = 2147483647 f(f(n)) = 2147483648 OK
*/
------解决方案--------------------
如果函数原形要求是：int f(int n)，也就是自变量和返回值都是int，
则有两个值是错的：int.MinValue 和 int.MaxValue，
不知能不能减少到一个值。
- C# code
using System;
class Program
{
static void Main()
{
foreach (int n in new int[] { 0, 1, 2, 3, 4, 1000, 1001, -1, -2, -3, -4, -1000, -1001, int.MaxValue - 1, int.MinValue+1, int.MaxValue, int.MinValue })
{
Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
Console.Write((long)n == -(long)(f(f(n))) ? "OK" : "ERROR");
Console.WriteLine();
}
}
static int f(int n)
{
if ((n & 1) == 0) return -n + Math.Sign(n);
return n + Math.Sign(n);
}
}
/* 程序输出：
n = 0 f(n) = 0 f(f(n)) = 0 OK
n = 1 f(n) = 2 f(f(n)) = -1 OK
n = 2 f(n) = -1 f(f(n)) = -2 OK
n = 3 f(n) = 4 f(f(n)) = -3 OK
n = 4 f(n) = -3 f(f(n)) = -4 OK
n = 1000 f(n) = -999 f(f(n)) = -1000 OK
n = 1001 f(n) = 1002 f(f(n)) = -1001 OK
n = -1 f(n) = -2 f(f(n)) = 1 OK
n = -2 f(n) = 1 f(f(n)) = 2 OK
n = -3 f(n) = -4 f(f(n)) = 3 OK
n = -4 f(n) = 3 f(f(n)) = 4 OK
n = -1000 f(n) = 999 f(f(n)) = 1000 OK
n = -1001 f(n) = -1002 f(f(n)) = 1001 OK
n = 2147483646 f(n) = -2147483645 f(f(n)) = -2147483646 OK
n = -2147483647 f(n) = -2147483648 f(f(n)) = 2147483647 OK
n = 2147483647 f(n) = -2147483648 f(f(n)) = 2147483647 ERROR
n = -2147483648 f(n) = 2147483647 f(f(n)) = -2147483648 ERROR
*/
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
