编程之美——一摞烙饼的排序（暴搜+剪枝）

题目

分析

深度优先搜索遍历每一种情况，去翻转次数最小的，当然，还要加一些剪枝，毕竟O(nⁿ)的时间复杂度。

代码

C风格

/**** 前缀排序 ****/
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 100 + 10;
int n, arr[maxn];            //烙饼个数和烙饼数组
int arr_cmp[maxn];
int arr_tmp[maxn];                //记录初始数组

int search_times = 0;        //总搜索次数
int max_swap;            //最小交换次数
int arr_swap[2 * maxn];        //最终翻转方案
int tarr_swap[2 * maxn];    //当前翻转方案

void Init()
{
    for (int i = 0; i < n; i++)  arr_tmp[i] = arr_cmp[i] = arr[i];
    sort(arr_cmp, arr_cmp + n);
    max_swap = 2 * (n - 1);
}

void Reverse(int* arr,int start, int end)
{
    for (int i = start, j = end; i < j; i++, j--)
        swap(arr[i], arr[j]);
}

int LowerBound()
{
    int ret = 0;
    for (int i = 1; i < n; i++)
        if (arr[i - 1] > arr[i])  ret++;
    return ret;
}

bool IsSort()
{
    for (int i = 0; i < n; i++)
        if (arr_cmp[i] != arr[i])  return false;
    return true;
}

void Search(int step)
{
    search_times++;

    if (IsSort())    //已排好序
    {
        if (step < max_swap)
        {
            max_swap = step;
            for (int i = 0; i < max_swap;i++)  arr_swap[i] = tarr_swap[i];
        }
    }

    if ((step + LowerBound()) > max_swap)  return;

    for (int i = 1; i <= n; i++)
    {
        Reverse(arr,0, i);
        tarr_swap[step] = i;
        Search(step + 1);
        Reverse(arr,0, i);
    }
}

void Print()
{
    printf("搜索次数：%d\n", search_times);
    printf("翻转次数: %d\n", max_swap);
    for (int i = 0; i < max_swap; i++)  printf("%d ", arr_swap[i]);
    printf("\n具体的翻转情况：\n");
    for (int i = 0; i < max_swap; i++)
    {
        Reverse(arr_tmp, 0, arr_swap[i]);
        for (int j = 0; j < n; j++)  printf("%d ", arr_tmp[j]);
        printf("\n");
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)  scanf("%d", &arr[i]);
    Init();
    Search(0);
    Print();
}

C++风格

#include<stdio.h>
#include<cstring>
#include<cassert>         //assert宏的原型定义在<assert.h>中
#include<algorithm>
using namespace std;

class laobing
{
private:
    int* m_CakeArray;        //烙饼信息数组
    int m_nCakeCnt;            //烙饼个数
    int m_nMaxSwap;            //最多翻转次数
    int* m_SwapArray;        //最终翻转烙饼位置
    int* m_ReverseCakeArray;        //当前烙饼数组
    int* m_ReverseCakeArraySwap;    //当前翻转烙饼位置
    int m_nSearch;            //搜索次数

public:
    laobing()
    {
        int m_CakeCnt = 0;
        int m_nMaxSwap = 0;
    }
    ~laobing()
    {
        if (m_CakeArray != NULL)  delete m_CakeArray;
        if (m_SwapArray != NULL)  delete m_SwapArray;
        if (m_ReverseCakeArray != NULL)  delete  m_ReverseCakeArray;
        if (m_ReverseCakeArraySwap != NULL)  delete m_ReverseCakeArraySwap;
    }

    //计算烙饼翻转信息
    //pCakeArray    存储烙饼数组
    //nCakeCnt      烙饼个数
    void run(int* pCakeArray, int nCakeCnt)
    {
        Init(pCakeArray, nCakeCnt);
        m_nSearch = 0;
        Search(0);
    }

    //输出交换过程
    void OutputArray(int* CakeArray, int nCakeCnt, int* m_SwapArray, int m_nMaxSwap)
    {
        for (int i = 0; i < m_nMaxSwap; i++)   //每一次交换
        {
            Reverse(CakeArray, 0, m_SwapArray[i]);
            for (int i = 0; i < nCakeCnt; i++)  printf("%d ", CakeArray[i]);
            printf("\n");
        }
    }

    //输出烙饼具体的翻转情况
    void Output()
    {
        for (int i = 0; i < m_nMaxSwap; i++)  printf("%d ", m_SwapArray[i]);
        printf("\n");
        printf("Search Times: %d\n", m_nSearch);
        printf("Total Times: %d\n", m_nMaxSwap);

        OutputArray(m_CakeArray, m_nCakeCnt, m_SwapArray, m_nMaxSwap);
    }
private:
    void Init(int *pCakeArray, int nCakeCnt)
    {
        assert(pCakeArray != NULL);        //其作用是如果它的条件返回错误，则终止程序执行。
        assert(nCakeCnt > 0);

        //初始化烙饼数组
        m_nCakeCnt = nCakeCnt;
        m_CakeArray = new int[m_nCakeCnt];
        assert(m_CakeArray != NULL);
        for (int i = 0; i < m_nCakeCnt; i++)
            m_CakeArray[i] = pCakeArray[i];

        //设置最多交换次数
        m_nMaxSwap = UpBound(m_nCakeCnt);

        //初始化交换数组结果
        m_SwapArray = new int[m_nMaxSwap];
        assert(m_SwapArray != NULL);

        //初始化中间交换结果
        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];
    }

    //寻找当前翻转次数的上界
    //n个烙饼，翻转最大的n-2烙饼最多需要2*(n-2)次，剩下的2个最多1次，因而上限值为2*n-3，
    //因此，m_nMaxSwap初始值可以取2*n-3+1=2*n-2，这样每步与m_nMaxSwap的判断就可以取大等于号。
    int UpBound(int nCakeCnt)
    {
        return 2 * (nCakeCnt - 1);  
    }

    //寻找当前翻转次数的下界
    int LowerBound(int* pCakeArray, int nCakeCnt)
    {
        int ret = 0;

        //根据当前数组的顺序信息来判断最少需要交换多少次
        for (int i = 1; i < nCakeCnt; i++)
        {
            //判断位置相邻的两个烙饼是否是尺寸相邻的
            int tmp = pCakeArray[i] - pCakeArray[i - 1];
            if (tmp == 1 || tmp == -1)  continue;
            else  ret++;
        }
        if (pCakeArray[nCakeCnt - 1] != nCakeCnt - 1)  ret++;  //判断下界时，如果最大的烙饼不在最后一个位置，则要多翻转一次
        return ret;
    }

    //排序的主函数
    void Search(int step)
    {
        m_nSearch++;
        // // 估算这次搜索所需要的最小交换次数  
        int nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
        if (step + nEstimate >= m_nMaxSwap)  return;        //剪枝

        //如果已经排好序，直接输出
        if (IsSort(m_ReverseCakeArray, m_nCakeCnt))
        {
            if (step < m_nMaxSwap)
            {
                m_nMaxSwap = step;
                for (int i = 0; i < m_nMaxSwap; i++)  m_SwapArray[i] = m_ReverseCakeArraySwap[i];
            }
            return;
        }

        //递归进行翻转
        for (int i = 1; i < m_nCakeCnt; i++)
        {
            Reverse(m_ReverseCakeArray, 0, i);
            m_ReverseCakeArraySwap[step] = i;
            Search(step + 1);    //递归
            Reverse(m_ReverseCakeArray,0, i);        //回溯
        }
    }

    //检查是否排好序
    bool IsSort(int * pCakeArray, int nCakeCnt)
    {
        for(int i = 1;i < nCakeCnt;i++)
            if (pCakeArray[i - 1] > pCakeArray[i])  return false;
        return true;
    }

    //翻转烙饼信息
    void Reverse(int* m_arr,int nBegin, int nEnd)
    {
        assert(nEnd > nBegin);

        for (int i = nBegin, j = nEnd; i < j; i++, j--)
            swap(m_arr[i], m_arr[j]);
    }
};

const int maxn = 100 + 10;
int n, arr[maxn];

int main()
{
    laobing lb;
    laobing* p = new laobing();
    scanf("%d", &n);
    for (int i = 0; i < n; i++)  scanf("%d", &arr[i]);

    p->run(arr, n);
    p->Output();

    lb.run(arr, n);
    return 0;
}

参考链接：

https://blog.csdn.net/tianshuai1111/article/details/7659673

http://blog.sina.com.cn/s/blog_a2aa00d70101ewuf.html

https://blog.csdn.net/ML_algorithmResearch/article/details/50405548