将直径不同的烙饼有序排列的问题，求取最优解需要的反转次数。
代码：
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;
}
}
}
}
本文转自today4king博客园博客，原文链接：http://www.cnblogs.com/jinzhao/archive/2008/08/21/1272660.html，如需转载请自行联系原作者