1.INTEL的一道面试题
有10大瓶药丸，其中有若干瓶药丸受到了污染，已知未受过污染的药丸每粒重量为1g，受过污染的每粒为1.1g，现在手头有一个天平（带砝码），只称一次，便可以知道哪几瓶药丸受污染了。如何称？
这题和另外一题相似。
有100筐苹果，有99筐苹果每个重量都是500克，但有一筐苹果的重量为490克一个，问怎么秤一次就能把490克一个的那筐找出来。解法是给100筐都编上号，第1筐取1个，第2筐取2个……第100筐取100个，这样根据最后的重量和（1+2+3+4……100）x500比较就可以找出来。
药丸这题因为是若干瓶受污染所以取法和苹果一样的话，没法找出受污染的药瓶。最初的想法就是编号以后，每瓶取10的n次幂，最后称出来的重量比对一下即可（如果第一瓶受污染则小数点多出0.1克，如果是第二瓶则是1克……）。
第1瓶取10^0=1粒
第2瓶取10^1=10粒
……
第10瓶取10^9=9000000000粒
—————————————————————
推广一下，取10的n次幂其实就是利用10进制来区分，那么二进制、三进制、四进制和其他都是可以的。
比如二进制
第1瓶取2^0=1粒
第2瓶取2^1=2粒
……
第10瓶取2^9=512粒
如果第一瓶受污染则小数点多出0.1克，如果是第二瓶则是0.2克，如果多出0.7克，则应该是(2^2+2^1+2^0)x0.1=0.7，即第一瓶、第二瓶和第三瓶受污染了。
—————————————————————
又如三进制
第1瓶取3^0=1粒
第2瓶取3^1=3粒
……
第10瓶取3^9=19683粒
如果第一瓶受污染则小数点多出0.1克，如果是第二瓶则是0.3克，如果多出3.1克，则应该是(3^3+3^1+3^0)x0.1=3.1，即第一瓶、第二瓶和第四瓶受污染了。
—————————————————————
比较一下2进制最节省药丸，也是最合理的，一共只需要2^10-1=1023粒。

2.12个球找异常
题目：有12个乒乓球特征相同，其中只有一个重量异常，现在要求一部没有砝码的天平称三次，将那个重量异常的球找出来。
程序如下，相关说明见thom同学的解答http://panweizeng.com/document/archives/156
using System;

namespace Microsoft
{
class Program
{
static void Main(string[] args)
{
int[] arrBallb = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int[] temp = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
for (int i = 0; i < 12; i++)
{
arrBallb.CopyTo(temp, 0);
temp[i] = 0;
//temp[i] = 2;
Console.WriteLine(GetAbnormalBall(temp));
}
Console.Read();
}
public static int GetAbnormalBall(int[] arrBall)
{
bool isSwap = false;
if (GetWeight(arrBall, 0, 3) == GetWeight(arrBall, 4, 7)) // 最先比较的两组相等
{
if (GetWeight(arrBall, 0, 1) == GetWeight(arrBall, 8, 9))
{
switch (Compare(arrBall, 0, 10))
{
case "<":
case ">“:
return GetIndex(10, isSwap);
case “=”:
return GetIndex(11, isSwap);
default:
return -1;
}
}
else
{
switch (Compare(arrBall, 0, 8))
{
case “<":
case ">“:
return GetIndex(8, isSwap);
case “=”:
return GetIndex(9, isSwap);
default:
return -1;
}
}
}
else if (GetWeight(arrBall, 0, 3) != GetWeight(arrBall, 4, 7))// 最先比较的两组不相等
{
if (GetWeight(arrBall, 0, 3) > GetWeight(arrBall, 4, 7)) //重的在先就交换
{
for (int i = 0; i < 4; i++)
{
Swap(ref arrBall, i, i + 4);
}
isSwap = true;
}
int[] arrLight = { arrBall[0], arrBall[1], arrBall[4] };//轻+轻+重
int[] arrMix = { arrBall[2], arrBall[5], arrBall[8] };//轻+重+平
//还剩轻arrBall[3] 重arrBall[6]和arrBall[7]

if (GetWeight(arrLight, 0, 2) < GetWeight(arrMix, 0, 2))
{
switch (Compare(arrBall, 0, 1))
{
case "<":
return GetIndex(0,isSwap);
case ">“:
return GetIndex(1, isSwap);
case “=”:
return GetIndex(5, isSwap);
default:
return -1;
}
}
else if (GetWeight(arrLight, 0, 2) > GetWeight(arrMix, 0, 2))
{
switch (Compare(arrBall, 4, 8))
{
case “<":
return -1;
case ">“:
return GetIndex(4, isSwap);
case “=”:
return GetIndex(2, isSwap);
default:
return -1;
}
}
else if (GetWeight(arrLight, 0, 2) == GetWeight(arrMix, 0, 2))
{
switch (Compare(arrBall, 6, 7))
{
case “<":
return GetIndex(7, isSwap);
case ">“:
return GetIndex(6, isSwap);
case “=”:
return GetIndex(3, isSwap);
default:
return -1;
}
}
else return -1;
}
else return -1;
}
public static int GetWeight(int[] arrBall, int beginIndex, int endIndex)
{
int sum = 0;
for (int i = beginIndex; i <= endIndex; i++ )
{
sum += arrBall[i];
}
return sum;
}
public static string Compare(int[] arrBall, int beginIndex, int endIndex)
{
if (arrBall[beginIndex] == arrBall[endIndex]) return "=";
else if (arrBall[beginIndex] < arrBall[endIndex]) return "<";
else if (arrBall[beginIndex] > arrBall[endIndex]) return “>”;
else return “error”;
}
public static void Swap(ref int[] arrBall, int beginIndex, int endIndex)
{
int temp = arrBall[beginIndex];
arrBall[beginIndex] = arrBall[endIndex];
arrBall[endIndex] = temp;
}
public static int GetIndex(int index, bool isSwap)
{
//如果交换过则对位置进行修正
if (isSwap && index > 3) return index - 4;
else if (isSwap && index <= 3) return index + 4;
else return index;
}
}
}