高校挑戰賽：觀看世界杯--限制排序算法，高校挑戰賽

高校挑戰賽：觀看世界杯--限制排序算法，高校挑戰賽

試題來源：http://student.csdn.net/mcs/programming_challenges?&page=1  觀看世界杯

　　以前在學校參加每年的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.只能隨便選一張兩邊都是人的座位
         *  
         * 
         * 輸出結果：
         * 表示游客的選座方法（順序號對應游客的入場順序）。
         * 
         * 
         * 修改personIndex 的值表示入場的人數（座數），為題中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;
                    }
                }
            }
        }
    }