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

本文主要是介绍烙饼排序问题最优次数求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

代码：

  
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();

             for (int i = 0; i < cakeSizeArray.Length; i++)
             {
                 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;
                 }
             }//排序成功退出

             for (int i = 0; i < cakeArray.Length; i++)
             {
                 revert(0, i);
                 search(step+1);
                 revert(0, i);
             }//递归穷举所有方案
        }

         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;
             }
         }
     }
 }
 