金沙澳门官网登录-www.js8.com-金沙澳门官网下载app

高校挑战赛:观看世界杯--限制排序算法

试题来源:高校挑战赛:观看世界杯--限制排序算法。高校挑战赛:观看世界杯--限制排序算法。高校挑战赛:观看世界杯--限制排序算法。  观看世界杯

  

  以前在学校参加每年的ACM程序设计大赛,感觉程序算法还是挺有意思的,这两天发现一个网站上放出一些算法试题,有点当年的那种心情,看到了,感觉能干掉,那就干掉它。目前还在公司守夜中,闲着没事就试了试算法题。

  速手打,没有详细检查,可能有瑕疵请见谅,但是读题、解题、算法设计,一个不少。

 if(type == 1){...} 这段里,虽然写的有点小复杂,但是是个简单的优化,呵呵。

  做事前,先看清,再下手。程序猿时间有限,不要随意浪费,错误的解读,终会造成一个不正确的结果。

class Program
    {
        /*
         *     世界杯正在火热进行中,室友不惜睡眠时间,凌晨起来观看,但Njzy对此不是很感兴趣,他在思考一个问题: 
         * 假设世界杯观看台上有n个座位,排成一排,游客们来到这里自由占位。一般情况下,一个游客首先考虑的座位
         * 肯定是两边都没人的座位,其次考虑的是一边没人的座位,最后没得考虑,只能随便选一张两边都是人的座位。
         * 假设有n个游客依次到场占位,每个人都是按照上述规则选择自己的位子,Njzy就在思考这n个游客占位的可能顺
         * 序有多少种,你能帮助他? 输入描述: 有多组测试数据,每组测试数据包括一个正整数n(0<n<1000000)。 输出
         * 描述: 对于每组数据,由于答案可能会很大,所以输出:答案%1000000007
         * 
         * **************************************
         * 
         * 首先仔细读题:
         *  1.世界杯观看台上有n个座位,这n个座位有n个依次到场的游客来坐。
         *    解析:这里面隐藏两点(这两点很重要,如果没有读出这两点,计算会非常复杂):
         *                  a.座位数等于游客数
         *                  b.游客有入场顺序(此题中游客的入场顺序为1,2,3,4...)
         * (限制型排序算法)                 
         * 
         *                  
         *  2.首先考虑的座位肯定是两边都没人
         *  
         *  3.其次考虑的是一边没人的座位
         *  
         *  4.只能随便选一张两边都是人的座位
         *  
         * 
         * 输出结果:
         * 表示游客的选座方法(顺序号对应游客的入场顺序)。
         * 
         * 
         * 修改 _PersonCount 的值表示入场的人数(座数),为题中n(0<n<1000000)
         * 如果只求出总选座的方法,可以注释 Console.WriteLine(string.Join(",", _SiteArray));
         * 没有输出,提高程序的计算效率。
         */

        static void Main(string[] args)
        {
            //假设:人数、座位数(1,2,3...表示游客的入场顺序)
            int _PersonCount = 4;

            int[] _SiteArray = new int[_PersonCount];

            int personIndex = 1;
            int type = 2;

            switch (_SiteArray.Length)
            {
                case 0: type = -1; break;
                case 1: type = 0; break;
                case 2: type = 1; break;
                case 3: type = 2; break;
                default: type = 2; break;
            }

            FuncRun(ref _SiteArray, ref personIndex,  type);

            Console.WriteLine("总共 {0} 种选座的方法",ResCount);
        }

        static void Swap(ref int l, ref int r)
        {
            l = l ^ r;
            r = l ^ r;
            l = l ^ r;
        }

        static int ResCount = 0;

        static void FuncRun(ref int[] _SiteArray, ref int personIndex,  int type)
        {
            if (personIndex > _SiteArray.Length)
            {
                Console.WriteLine(string.Join(",", _SiteArray));
                ResCount++;
                return;
            }

            if (type == 2)
            {
                //---------------------------------------------------
                //首先考虑的座位肯定是两边都没人
                for (int i = 1; i < _SiteArray.Length - 1; i++)
                {
                    if (_SiteArray[i] > 0)
                        continue;

                    if (_SiteArray[i - 1] == 0 && _SiteArray[i + 1] == 0)
                    {
                        _SiteArray[i] = personIndex++;
                        FuncRun(ref _SiteArray, ref personIndex,  type);
                        //数据恢复
                        personIndex--;
                        _SiteArray[i] = 0;
                    }
                }
                type--;
            }

            //---------------------------------------------------
            //其次考虑的是一边没人的座位
            if (type == 1)
            {
                if (personIndex <= 1 || _SiteArray.Length < 3)
                    return;

                if (_SiteArray[0] == 0 && _SiteArray[1] == 0)
                {
                    _SiteArray[0] = personIndex++;
                    FuncRun(ref _SiteArray, ref personIndex,  type);
                    //数据恢复
                    personIndex--;
                    _SiteArray[0] = 0;
                }

                for (int i = 1; i < _SiteArray.Length - 1; i++)
                {
                    if (_SiteArray[i] > 0)
                        continue;

                    if (_SiteArray[i - 1] == 0)
                    {
                        _SiteArray[i] = personIndex++;
                        FuncRun(ref _SiteArray, ref personIndex,  type);
                        //数据恢复
                        personIndex--;
                        _SiteArray[i] = 0;
                    }
                    else if (_SiteArray[i + 1] == 0)
                    {
                        _SiteArray[i] = personIndex++;
                        FuncRun(ref _SiteArray, ref personIndex,  type);
                        //数据恢复
                        personIndex--;
                        _SiteArray[i] = 0;
                    }
                }

                if (_SiteArray[_SiteArray.Length - 1] == 0 && _SiteArray[_SiteArray.Length - 2] == 0)
                {
                    _SiteArray[_SiteArray.Length - 1] = personIndex++;
                    FuncRun(ref _SiteArray, ref personIndex,  type);
                    //数据恢复
                    personIndex--;
                    _SiteArray[_SiteArray.Length - 1] = 0;
                }
                type--;
            }

            //---------------------------------------------------
            //只能随便选一张两边都是人的座位
            if (type == 0)
            {
                for (int i = 0; i < _SiteArray.Length; i++)
                {
                    if (_SiteArray[i] == 0)
                    {
                        _SiteArray[i] = personIndex++;
                        FuncRun(ref _SiteArray, ref personIndex,  type);
                        //数据恢复
                        personIndex--;
                        _SiteArray[i] = 0;
                    }
                }
            }
        }
    }

 

本文由金沙澳门官网登录发布于世界杯实况,转载请注明出处:高校挑战赛:观看世界杯--限制排序算法

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。