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;
        }
    }
}