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

試題來源：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.只能隨便選一張兩邊都是人的座位         *           *          * 輸出結果：         * 表示游客的選座方法（順序號對應游客的入場順序）。         *          *          * 修改 _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;                    }                }            }        }    }