昨天晚上，被一个同事问到一个有趣的问题，想了一天，觉得很有趣味，在这里和大家分享一下。

    问题是这样的：有5个渔夫，一同捕了一堆鱼，然后都睡着了，甲醒来后，扔掉一条鱼然后将剩余的鱼平均分成了5分，自己拿走了其中的一份，乙醒来后，也仍掉一条鱼，然后将剩余的鱼平均分成5分，自己拿走一份，以此类推，丙、丁、戊醒来后都按照甲和乙的做法去做，问他们至少补了多少条鱼？

    对于这个问题的思考，从一开始，我们便有了不同的想法，他的想法是从1遍历到10000，对每个数进行判断，判断的规则就是这个数字减去1后可以整除5，然后再减去1还是可以被5整除，之后再减去1.。。。。。。，判断的过程可以写一个递归。而我的想法恰好相反，我认为应该从最后一个人醒来后看到的鱼的数量着手解题，假设最后一个人看到的鱼的数量为N，那么N可以被4整除，减去1后可以被5整除，同样可以写一个递归，但是递归的过程是算上一个醒来人所看到的鱼的数量，（N*5/4 +1 ） 是丁醒来时看到的鱼的数量，这个数量我们定义为M，那么M可以被4整除，减去1可以被5整除，如此递归下去，就可以解决问题。

     似乎问题就这样解决了，可是这里有一个小问题，如果确定遍历的范围呢？如果这个数值不在10000内，该怎么办，如果把遍历范围扩大到10万，还是面临同样的问题，如果不在10万里呢？这也就是说，我们是没有办法确定这个遍历范围的，怎么办？

     解决的办法就是自动扩大遍历范围，1到1万没有找到的，就自动扩大遍历范围，遍历1万到2万之间的数字，以此类推，直到找到这个数字为止。似乎问题又得到了很好的解决，可是这个时候又面临新的问题，在遍历的过程中，我们是不是遍历了很多无意义的数字呢？要知道，我们遍历的实质是找到一个我们认为包含这个答案数值的集合，然后逐个去检验，那么有没有什么办法可以缩小这个遍历的范围呢？

      当然有的，我们注意观察的话，可以发现，后面四个人醒来时发现的鱼的数量有一个共同点，鱼的数量可以被4整除，减去1后可以被5整除。那么想一想，这样的数字个位一定是6，只有个位是6的数字才能满足这样的要求，OK，我们已经已经在很大程度上缩小遍历的范围了，那么继续思考的话，我们不难发现，这个数值除以4的话，其商值的个位数一定是9，只有这样，这个数字在乘以4分之5后所得的数值的个位数才能是5，进而可以被5整除，加1后可以被4整除。这样，我们又一次缩小了遍历的范围，后面四个人醒来时发现的鱼的数量的个位是6，除以4后得到的数值的个位是9，我们要遍历的数值的范围可以确定了:36 +i*40,i从0开始递增。

     似乎问题再一次被有效解决了，但还是存在着一个小问题，按照最开始的思路，我们要确定一个遍历范围，即确定这个范围内的最大值，然后逐个数值去做判断，当在范围内找不到答案时，扩大范围。可是难道要我们去判断在这个范围内的数值首先要满足个位是6，除以4后个位是9么？当然不能，既然我们已经知道了要遍历数值的特点，我们可以自己生成这些数字，而不是从一个集合中把他们挑选出来。我们完全可以一次创建10个数字，然后逐个递归判断，如果正确数值不在这10个内，我们则继续生成10个新的数字，直到找到答案为止。这里还有一个有趣的地方，就是做递归判断时，我们应该做乘法，从最后一个人开始算，算之前的人所看到的鱼的数量，这样比做除法要快，因为我们只需要遍历到最小的那个数值就可以得出答案了，下面是C#写的代码，欢迎大家指点。

using System;
using System.Collections;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Sunday
    {
        public static void Main()
        {

            Test MyTest = new Test();
            Console.WriteLine(MyTest.GetNumber());
        }
    }

    class Test
    {
        private Hashtable HT_Test;
        public Test()
        {
            HT_Test = new Hashtable();
        }
        public int GetNumber()
        {
            int i;
            int Result;
            int start;
            Boolean bResult;
            bResult = true;
            start = 36;
            Result = -1;
            while (bResult)
            {
                //每次产生10个数字
                HT_Test.Clear();
                for (i = 0; i < 10; i++)
                {
                    start = start + 40;
                    HT_Test.Add(i, start);
                }
                //对一组数字进行计算
                Result = GetMinNumber(HT_Test);
                if (Result != -1)
                {
                    bResult = false;
                }
            }
            return Result;
        }
        private int GetMinNumber(Hashtable Table)
        {
            int i;
            int iReturnVale;
            iReturnVale = -1;
            Boolean bRetruenvalue;
            bRetruenvalue = true;
            foreach (int iKey in Table.Keys)
            {
                //对每个数字进行校验和计算，校验的过程采用递归
                bRetruenvalue = CheckValue((int)(Table[iKey]), 4);
                if (bRetruenvalue)
                {  
                    //当最小的数字被发现时，用它计算最大的数字
                    iReturnVale = (int)(Table[iKey]);
                    for (i = 0; i < 4; i++)
                    {
                        iReturnVale = (iReturnVale*5) / 4 + 1;
                       
                    }
                }
            }
            return iReturnVale;
        }
        private Boolean CheckValue(int Number, int count)
        {
            int CheckCount;
            int UpNumber;
            Boolean ReturnValue;
            ReturnValue = true;
            CheckCount = count;
            UpNumber = Number;
            if (CheckCount == 0)
            {
                ReturnValue = true;
            }
            else
            {
                //先看其是否能被4整除，满足条件后继续递归
                if ((UpNumber) % 4 == 0)
                {
                    UpNumber = (Number * 5) / 4 + 1;
                    CheckCount--;
                    ReturnValue = CheckValue(UpNumber, CheckCount);
                }
                else
                {
                    ReturnValue = false;
                }
            }
            return ReturnValue;
        }
    }
}