《编程之美》一摞烙饼问题探讨

最新推荐文章于 2024-08-29 12:31:27 发布

王晓华-吹泡泡的小猫

最新推荐文章于 2024-08-29 12:31:27 发布

阅读量5.3k

点赞数

文章标签：编程算法 java 优化 null

本文链接：https://blog.csdn.net/orbit/article/details/2792161

版权

本文探讨了《编程之美》中的一摞烙饼问题，即如何通过翻动盘子实现从大到小排序。文章介绍了FindMaxIdx和Revert函数用于找到最大盘子并进行翻转，以及PrefixSort函数进行排序。作者提出对于局部有序但反序的盘子，如何优化翻转次数的问题，并讨论了动态规划和分枝界限法作为潜在解决方案，但最终的解答仍采用穷举法。此外，文中还指出书中代码存在的内存管理问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

《编程之美》一摞烙饼问题探讨

    这类问题我最早遇到是厨师摆盘子问题，就是厨师要把一个架子上的盘子按照从大到小排列，只能象本题中翻动烙饼的方式翻动盘子，当时我给出了这样的答案：

int FindMaxIdx(int *pDishes, int nBegin, int nEnd)
{
    int i,maxIdx = nBegin;
    for(i = nBegin + 1; i <= nEnd; i++)
    {
        if(pDishes[i] > pDishes[maxIdx])
        {
            maxIdx = i;
        }
    }
    return maxIdx;
}

void Revert(int *pDishes, int nBegin, int nEnd)
{
    int i,j,tmp;
    assert(nEnd > nBegin);
    for(i = nBegin, j = nEnd; i < j; i++,j--)
    {
        tmp = pDishes[i];
        pDishes[i] = m_CakeArray[j];
        pDishes[j] = tmp;
    }
}

int PrefixSort(int *pDishes, int fjCount)
{
    int i,curMax;