烙饼排序问题最优次数求解

将直径不同的烙饼有序排列的问题，求取最优解需要的反转次数。

代码：

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，如需转载请自行联系原作者