問題描述: 有一摞烙餅,因為一隻手端着盤子,是以隻能用另外一隻手來給烙餅排序,将烙餅由大到小排好序。這樣就要求我們在給烙餅排序的時候總是将最上面的N個烙餅一起翻轉。如果最下面的烙餅是最大的,那麼隻需要解決上面的N-1個烙餅,同理可以最後到解決兩個烙餅的排序。
簡單的排序方法:先找到最大的烙餅,将其和其以上的烙餅一起翻轉,這樣最大的烙餅就在盤子的最上面了,然後翻轉所有的烙餅,這樣最大的烙餅就在盤子的最下面了。同樣的,處理剩下的N-1個烙餅,知道最後所有的烙餅都排好序。可以知道我們最多需要進行2*(N-1)次翻轉就可以将所有的烙餅排好序。
問題? 如果減少烙餅的反轉次數,達到一個最優的解。 加入這堆老兵中有幾個不同的部分相對有序,憑直接來猜測,可以把笑一下的烙餅進行翻轉,每次考慮翻轉烙餅的時候總是把相鄰的烙餅盡可能的放到一起。
解決方法: 通過窮舉法來找所有可能方案中的最優方案,自然會用到動态規劃或者遞歸的方法來實作。可以從不同的翻轉政策開始,比如第一次先翻最小的,然後遞歸的把所有的可能都全部翻轉一次。
既然2(N-1)是一個最多的翻轉次數,就可以得知,如果算法中的翻轉次數超過了2(N-1),我們就應該放棄這個算法。
我們總是希望UpperBound越小越好,而LowerBound則越大越好,這樣就可以盡可能的減少搜尋的次數,是算法的性能更好。
代碼如下:(代碼可能需要仔細的閱讀,才能明白算法的含義)
#pragma once
class CPrefixSorting
{
public:
~CPrefixSorting(void);
CPrefixSorting()
{
m_nCakeCnt=0;
m_nMaxSwap=0;
}
// 計算烙餅翻轉資訊
// @param
// pCakeArray 存儲烙餅索引數組
// nCakeCnt 烙餅個數
//
void Run(int* pCakeArray, int nCakeCnt)
{
Init(pCakeArray,nCakeCnt);
m_nSearch=0;
Search(0);
}
// 輸出烙餅的翻轉次數,翻轉資訊
void Output()
{
for(int i=0;i<m_nMaxSwap;i++)
{
printf("%d",m_SwapArray[i]);
}
printf("\n |Search Times|:%d\n",m_nSearch);
printf("Total Swap times=%d\n",m_nMaxSwap);
}
private:
int* m_CakeArray; // 烙餅資訊數組
int m_nCakeCnt; // 烙餅的個數
int m_nMaxSwap; // 最多交換次數,根據前面的推斷,最多為m_nCakeCnt*2
int* m_SwapArray; // 交換結果數組
int* m_ReverseCakeArray; // 目前翻轉烙餅資訊數組
int* m_ReverseCakeArraySwap; // 目前翻轉烙餅交換結果數組
int m_nSearch; // 目前搜尋次數資訊
// 初始化數組資訊
// @param
// pCakeArray 存儲烙餅索引數組
// nCakeCnt 烙餅個數
//
void Init(int* pCakeArray,int nCakeCnt)
{
m_nCakeCnt=nCakeCnt;
// 初始化烙餅數組
m_CakeArray=new int[m_nCakeCnt];
for(int i=0;i<m_nCakeCnt;i++)
{
m_CakeArray[i]=pCakeArray[i];
}
// 設定最多交換次數資訊
m_nMaxSwap=UpperBound(m_nCakeCnt);
// 初始化交換結果數組
m_SwapArray=new int[m_nMaxSwap+1];
// 初始化中間交換結果資訊
m_ReverseCakeArray=new int[m_nCakeCnt];
for(int i=0;i<m_nCakeCnt;i++)
{
m_ReverseCakeArray[i]=m_CakeArray[i];
}
m_ReverseCakeArraySwap=new int[m_nMaxSwap];
}
// 翻轉上屆
int UpperBound(int nCakeCnt)
{
return nCakeCnt*2;
}
// 目前翻轉的下屆
int LowerBound(int* pCakeArray, int nCakeCnt)
{
int t,ret=0;
// 根據目前數組的排序資訊情況來判斷最少需要交換多少次
for(int i=1;i<nCakeCnt;i++)
{
// 判斷位置相鄰的兩個烙餅是否為尺寸排序上相等的
t=pCakeArray[i]-pCakeArray[i-1];
if((t==1)||(t==-1))
{}
else
{
ret++;
}
}
return ret;
}
// 排序的主函數
void Search(int step)
{
int i, nEstimate;
m_nSearch++;
// 估算目前搜尋所需要的最小的交換次數
nEstimate=LowerBound(m_ReverseCakeArray,m_nCakeCnt);
if(step+nEstimate>m_nMaxSwap)
{
return;
}
// 如果已經排好序,即翻轉完成後,輸出結果
if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
{
if(step<m_nMaxSwap)
{
m_nMaxSwap=step;// 修改最大的翻轉次數,讓m_nMaxSwap記錄最小的翻轉次數
for(i=0;i<m_nMaxSwap;i++)
{
m_SwapArray[i]=m_ReverseCakeArraySwap[i];
}
}
return;
}
// 遞歸進行翻轉
for(i=1;i<m_nCakeCnt;i++)
{
Reverse(0,i);
m_ReverseCakeArraySwap[step]=i;
Search(step+1);
Reverse(0,i);
}
}
// 判斷是否已經排好序
bool IsSorted(int* pCakeArray, int nCakeCnt)
{
for(int i=1;i<nCakeCnt;i++)
{
if(pCakeArray[i-1]>pCakeArray[i])
{
return false;
}
}
return true;
}
// 翻轉烙餅資訊
// 非常經典的數組翻轉算法
void Reverse(int nBegin,int nEnd)
{
int i,j,t;
for(i=nBegin,j=nEnd;i<j;i++,j--)
{
t=m_ReverseCakeArray[i];
m_ReverseCakeArray[i]=m_ReverseCakeArray[j];
m_ReverseCakeArray[j]=t;
}
}
};
// CPrefixSorting.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "iostream"
#include "PrefixSorting.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"--->begin"<<endl;
CPrefixSorting panCakeSort;
int panCake[5]={3,5,1,4,2};
panCakeSort.Run(panCake,5);
panCakeSort.Output();
return 0;
}
// CPrefixSorting.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "iostream"
#include "PrefixSorting.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"--->begin"<<endl;
CPrefixSorting panCakeSort;
int panCake[5]={3,5,1,4,2};
panCakeSort.Run(panCake,5);
panCakeSort.Output();
return 0;
}
輸出的結果為:
--->begin
32423
|Search Times|:2189
Total Swap times=5
請按任意鍵繼續. . .