烙餅排序問題最優次數求解

将直徑不同的烙餅有序排列的問題，求取最優解需要的反轉次數。

代碼：

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace CakeSorting

{

    class Program

    {

        private int[] cakeSizeArray;//大餅直徑隊列

        private int[] cakeArray;//大餅隊列

        const int cakeNum = 5;

        private int maxTime = 0;

        static void Main(string[] args)

        {

            Program p = new Program();

            p.run();

        }

        void run()

            init();

            search(0);

            Console.WriteLine("maxtime is :{0}", maxTime);

            Console.ReadLine();

        void init()

            //初始化指派

            maxTime = 2 * (cakeNum - 1);

            cakeArray = new int[cakeNum];

            cakeSizeArray = new int[cakeNum];

            for (int i = 0; i < cakeSizeArray.Length; i++)

            {

                cakeSizeArray[i] = i;

            }//大餅直徑初始化

            randomCollection();

            //隊列初始化完畢

        void randomCollection()

            if (cakeSizeArray.Length != cakeArray.Length)

                return;

            Random r = new Random();

                cakeArray[i] = cakeSizeArray[0];

            }

            for (int i = 1; i < cakeSizeArray.Length; i++)

                int address = r.Next(10);

                for(;;)

                {

                    if (address >= cakeSizeArray.Length)

                        address = 0;

                    if (cakeArray[address] != cakeSizeArray[0])

                        address++;

                    else

                        break;

                }

                cakeArray[address] = cakeSizeArray[i];

            //列印結果

            Console.WriteLine("Cake Array:");

            for (int i = 0; i < cakeArray.Length; i++)

                Console.Write("{0}\t", cakeArray[i]);

        void search(int step)

            if (step > maxTime)

                return;//大于2（n-1）時退出

            for (int i = 1; cakeArray [i-1]<cakeArray [i]; i++)

                if (i == cakeArray.Length - 1)

                    maxTime = step;

                    return;

            }//排序成功退出

                revert(0, i);

                search(step+1);

            }//遞歸窮舉所有方案

        void revert(int begin, int end)

            int t = cakeArray[begin];

            for (int i = begin, j = end; i < j; i++, j--)

                t = cakeArray[i];

                cakeArray[i] = cakeArray[j];

                cakeArray[j] = t;

    }

}

本文轉自today4king部落格園部落格，原文連結：http://www.cnblogs.com/jinzhao/archive/2008/08/21/1272660.html，如需轉載請自行聯系原作者