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同学的解答
发信人: thom (栋淼|暮霭沉沉楚天阔), 信区: Linux 标 题: 12个球找异常 发信站: 我爱南开站 (2007年06月26日13:02:17 星期二), 站内信件
分成三组，每组四个 4 . 4 ? 4 先比较其中两组。
1. 4 = 4 => 2 ? 平 => 1~平
如果一边4个相比相等，这8个均为平常，异常的只在剩下的4个里面。
从中取2个与普通2个相比，可以知道异常的分布。
(如果相等，在剩下的2个里面，否则就为这2个)
最后从异常的2个里面任取1个与平常的比较。2. 4 < 4 => 2轻+重 ? 轻+重+平
(如果一边4个相比不等，记4个轻的那组为轻，4个重的那组为重，剩下组记为平)
取轻中2个加上重中1个，再取轻中1个加重中1个加平中1个。
(还有可能出现异常的一组中有轻中1个+重中2个)
(可能异常组表示为异常)
A. <
2轻+重 < 轻+重+平 => 轻?轻 重
因为是轻，所以异常的不可能为左边的重或右边的轻。
轻与轻相比，轻的那个为轻异常，为所求；
如果相等，剩下重的那个为重异常，所求。
B. >
2轻+重 > 轻+重+平 => 重 轻 平
因为是重，所以异常的不可能为左边的2轻或右边的重
从重或轻中任取一个与平相比，异常即可得知。
C. =
2轻+重 = 轻+重+平 => 轻 重?重
相比相等，则异常在剩下那组，里面有轻中1个+重中2个
取重中2个相比，重的那个为重异常，为所求；
如果相等，剩下轻的那个为轻异常，为所求。※ 来源:·我爱南开站 nkbbs.org·[FROM: 10.22.22.121]
程序如下
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;
}
}
}