1.3 一摞烙餅的排序

參考《程式設計之美–1.3 一摞烙餅的排序》

問題描述：

一摞亂序擺放的烙餅，每次隻能抓取最上面幾塊烙餅并翻轉，多次翻轉後能夠實作烙餅的從小到大（從上往下）的有序擺放。

問題分析：

這裡我們使用回溯法解決這個問題。直接用回溯法效率是低下的，是以要進行剪枝。這裡的剪枝條件是利用翻轉次數的上界和下界完成的。

上界：

[4,2,1,5,3] -> [5,1,2,4,3] -> [3,4,2,1,5]

兩步可以按大小順序将某塊餅放到它應該在的位置。

同理，可以把其他四塊烙餅擺放好，要注意最後一塊烙餅會在最後第二塊烙餅擺放正确後位于正确位置。假設烙餅個數為n，則翻轉次數上界為2（n-1）。

下界：

上界我們已經得出了，下面考慮下界。在試驗翻轉的時候，我們可以發現，當烙餅堆部分有序時，翻轉次數較少。若一摞烙餅中有m對相鄰的烙餅半徑不相鄰，理想情況下需要m次翻轉來排序，[3,4,2,1,5,6]，此時就需要兩次來翻轉。

代碼如下：

#include <iostream>
#include <windows.h>
#include <math.h>
#include <assert.h>

using namespace std;

class PreFixSorting
{
public:
    PreFixSorting()
    {
        CakeCount = 0;
        MaxSwap = 0;
    }

    ~PreFixSorting()
    {
        if(CakeArray != NULL)
        {
            delete CakeArray;
        }
        if(SwapArray != NULL)
        {
            delete SwapArray;
        }
        if(ReverseCakeArray != NULL)
        {
            delete ReverseCakeArray;
        }
        if(ReverseCakeArraySwap != NULL)
        {
            delete ReverseCakeArraySwap;
        }
    }

    //計算烙餅翻轉資訊
    //@param
    //pCakeArray    存儲烙餅索引數組，索引大的烙餅個頭大
    //pCakeCount    烙餅個數

    void Run(int* pCakeArray, int pCakeCount)
    {
        Init(pCakeArray, pCakeCount);
        nSearch = 0;
        Search(0);
    }

    void Output()
    {
        for(int i = 0; i < MaxSwap; i++)
        {
            cout<<SwapArray[i]<<" ";
        }
        cout<<'\n'<<"|Search Times|: "<<nSearch<<endl;
        cout<<"Total Swap Times = "<<MaxSwap<<endl;

    }


private:
    //初始化數組資訊
    //@param
    //pCakeArray    存儲烙餅索引數組，索引大的烙餅個頭大
    //pCakeCount    烙餅個數

    void Init(int *pCakeArray, int pCakeCount)
    {
        assert(pCakeArray != NULL);
        assert(pCakeCount > 0);

        CakeCount = pCakeCount;

        //初始化烙餅數組
        CakeArray = new int[CakeCount];
        assert(CakeArray != NULL);
        for(int i = 0; i < CakeCount; i++)
        {
            CakeArray[i] = pCakeArray[i];
        }

        //擷取最多交換次數
        MaxSwap = UpperBound(CakeCount);
        //初始化交換結果數組
        SwapArray = new int[MaxSwap + 1];
        assert(SwapArray != NULL);
        //初始化中間交換結果數組
        ReverseCakeArray = new int[CakeCount];
        for(int i = 0; i < CakeCount; i++)
        {
            ReverseCakeArray[i] = CakeArray[i];
        }
        ReverseCakeArraySwap = new int[MaxSwap];


    }

    //尋找目前翻轉上界

    int UpperBound(int pCakeCount)
    {
        return (pCakeCount-1)*2;
    }


    //尋找目前翻轉下界
    int LowerBound(int* pCakeArray, int pCakeCount)
    {
        int t, ret = 0;
        //根據目前數組排序情況判斷最少需要交換的次數
        for(int i = 1; i < pCakeCount; i++)
        {
            //判斷位置相鄰的兩個烙餅是否索引相鄰
            t = pCakeArray[i] - pCakeArray[i-1];
            if((t == 1) || (t == -1))
            {

            }
            else
            {
                ret++ ;
            }
        }
        return ret;
    }


    //排序主函數
    void Search(int step)
    {
        int i, nEstimate;
        nSearch++;

        //估算交換次數下界
        nEstimate = LowerBound(ReverseCakeArray, CakeCount);
        if(step + nEstimate > MaxSwap )
        {
            return;
        }

        //若已排好序則輸出結果
        if(IsSorted(ReverseCakeArray, CakeCount))
        {
            if(step < MaxSwap)
            {
                MaxSwap = step;
                for(int i = 0; i < MaxSwap; i++)
                {
                    SwapArray[i] = ReverseCakeArraySwap[i];
                }
                return;
            }
        }


        //回溯法遞歸翻轉
        for(i = 1; i < CakeCount; i++)
        {
            Reverse(0, i);
            ReverseCakeArraySwap[step] = i;
            Search(step + 1);
            Reverse(0, i);
        }


    }


    //true：     已排序
    //false：    未排序
    bool IsSorted(int* pCakeArray, int pCakeCount)
    {
        for(int i = 1; i < pCakeCount; i++)
        {
            if(pCakeArray[i-1] > pCakeArray[i])
            {
                return false;
            }
        }
        return true;
    }


    //翻轉烙餅數組
    void Reverse(int nBegin, int nEnd)
    {
        assert(nEnd > nBegin);
        int i, j, t;

        for(i = nBegin, j = nEnd; i < j; i++, j--)
        {
            t = ReverseCakeArray[i];
            ReverseCakeArray[i] = ReverseCakeArray[j];
            ReverseCakeArray[j] = t;
        }

    }


private:
    int* CakeArray;                 //烙餅數組
    int CakeCount;                  //烙餅個數
    int MaxSwap;                    //交換次數上界
    int* SwapArray;                 //翻轉烙餅結果數組（翻轉前幾層烙餅，用于輸出）
    int* ReverseCakeArray;          //目前轉烙餅數組（中間狀态）
    int* ReverseCakeArraySwap;      //目前翻轉烙餅結果數組
    int nSearch;                    //目前搜尋次數
};



int main()
{
    PreFixSorting pfs;

    int CakeArray[] = {4,2,1,5,3};
    int CakeCount = 5;
    pfs.Run(CakeArray,CakeCount);
    pfs.Output();



    return 0;

}

           

注意： 關于這裡的上下界，其實目前研究的結果是上界最小為(5n+5)/3向上取整，下界最大為15n/14向上取整。用這個上下界的搜尋次數更少，效率更高（n較大時）。