编程之美—烙饼排序问题(JAVA)

一、问题描述

  星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢?自然是算法问题。有个同事说:“我以前在餐      馆打工,顾客经常点非常多的烙饼。店里的饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小次序摆好——小的在上面,大的在下面。由于我      一只手托着盘子,只好用另一只手,一次抓最上面的几块饼,把它们上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了。我后来想,这实际上是个     有趣的排序问题:假设有n块大小不一的饼,那最少要翻几次,才能达到最后大小有序的结果呢?你能否写出一个程序,对于n块大小不一的烙饼,输出     最优化的翻饼过程呢?

二、问题分析

  首先看到这个问题 ,你第一感觉肯定是:噢,这是一个排序问题。但是这个问题不同于一般的排序,从问题描述中可以看出,每次操作都只能选从第       一个到第n个烙饼,然后整体倒置(如图1)。问题来了,选择从第一个到底n个烙饼,进行倒置(1~n个饼并没有排好序),如何在每一次或者几次         倒置中可以使得烙饼的局部排好序呢?然后经过一系列倒置,然后使整体排好序。描述到这里,你是不是已经想到了一种解法呢?

三、解法一:首先把最上面的烙饼和最大的烙饼之间的烙饼翻转,于是,最大的烙饼就在最上面了,再进行一次翻转,把最大的烙饼放在最底

           部,最大的烙饼就在自己的正确位置上了。即通过两次翻转,把最大的烙饼放在最低部了。然后选择从最上面的饼和次大的烙饼

    ,重复上面的步骤。每两次翻转,把不再正确位置上的最大饼放在合适的位置上。

                 

那么,我们一共需要多少次翻转才能把这些烙饼给翻转过来呢?

             首先,经过两次翻转可以把最大的烙饼翻转到最下面。因此,最多需要把上面的n-1个烙饼依次翻转两次。那么,排到剩下第一个和第二个时,         我们需要2(n-2)次翻转。最后,第一个和第二个最多需要一次翻转(可能一次都不需要,已经排好序了)。

四、我们已经求出了一个解法,但是会不会有更好的方法通过更少的翻转达到相同的目的呢?

考虑一种情况,比如上面的图1,序号1、2、3的最上面三个烙饼其实是三个相邻顺序已经排好的烙饼。考虑每次翻转时都让把两个本来应该相邻在烙饼尽可能地换到一起。这样,当所有的烙饼都换到一起之后,实际上就是完成排序了。(从这个意义上来说,每次翻最大烙饼的方案实质上就是每次把最大的和次大的交换到一起,但是通过了两次翻转,不是每一次都尽可能的把两个本来应该相邻在烙饼尽可能地换到一起)

      那什么的情况下可以通过最少的翻转排好序呢?这里是不是可以选择一种穷举的方法,穷举所有的的每次翻转的情况,展开来看就是一棵树,每个结点都有九个子节点(有九中翻转情况),如果翻转达到2n-3还未排好序则截断这一分支。可以根据当前的翻转次数加上估计还需要的最小翻转次数(下界值,下限值可以这样确定:从最后一个位置开始,往前找到第一个与最终结果位置不同的烙饼编号(也就是说排除最后几个已经就位的烙饼),从该位置到第一个位置,计算相邻的烙饼的编号不连续的次数,再加上1。)来判断是否截断这一分支。我们可以选择递归的方法深度遍历这颗树,得到最小的排好序的那些步骤。

五、代码

public class CFlapjackSorting {
    private int m_nCake;    //烙饼的个数
    private int[] m_CakeArray;  //烙饼的信息数组,也就是初始数组的输入数
    private int m_nMaxSwap;     //最大的交换次数
    private int[] m_SwapArray;  //存储交换位置信息的数组
    private int[] m_ReverseCakeArray;   //当时翻转烙饼信息数组
    private int[] m_ReverseCakeArraySwap;  //当时存储交换位置信息的数组
    private int m_nSearch;      //搜索次数

    public CFlapjackSorting() {
        m_nCake = 0;
        m_nMaxSwap = 0;
    }

    /**
     *
     * @param pCakeArray  输入的烙饼信息
     * @param nCake       数组的长度
     */
    public void init(int[] pCakeArray, int nCake) {
        assert (pCakeArray != null);
        m_nCake = nCake;
        m_CakeArray = new int[m_nCake];
        assert (m_CakeArray != null);
        //初始化烙饼数组
        for (int i = 0; i < m_nCake; i++) {
            m_CakeArray[i] = pCakeArray[i];
        }

        m_nMaxSwap = upBound(m_nCake);
        m_SwapArray = new int[m_nMaxSwap + 1];
        assert (m_SwapArray != null);
        m_ReverseCakeArray = new int[m_nCake];
        for (int i = 0; i < m_nCake; i++) {
            m_ReverseCakeArray[i] = m_CakeArray[i];
        }

        m_ReverseCakeArraySwap = new int[m_nMaxSwap+1];
    }

    /**
     * 最大上界:可以翻转的最大次数
     * @param nCake 烙饼的个数
     * @return
     */
    public int upBound(int nCake) {
        return 2 * nCake;
    }

    /**
     * 最小下界
     * @param pCakeArray
     * @param nCake
     * @return
     */
    int LowerBound(int[] pCakeArray, int nCake) {
        int t, lower = 0;
        for (int i = 1; i < nCake; i++) {
            t = pCakeArray[i] - pCakeArray[i - 1];
            if ((t == 1) || (t == -1)) {

            } else {
                lower++;
            }
        }
        return lower;
    }

    /**
     * 搜索函数
     * @param step  第几步
     */
    public void search(int step) {
        int minEstimate; //最小交换次数估计
        m_nSearch++;
        minEstimate = LowerBound(m_ReverseCakeArray, m_nCake);
        if (step + minEstimate > m_nMaxSwap)
            return;
        //判读是否排好序
        if (isSorted(m_ReverseCakeArray, m_nCake)) {
            //如果排好序了,而且翻转次数小于最大翻转次数。否则终止搜索
            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_nCake; i++) {
            revert(0, i);
            m_ReverseCakeArraySwap[step] = i;  //记录每次翻转时翻转的位置信息
            search(step + 1);
            revert(0, i);
        }
    }

    /**
     * 判断是否排好序
     * @param pCakeArray
     * @param nCake
     * @return
     */
    public boolean isSorted(int[] pCakeArray, int nCake) {
        for (int i = 1; i < nCake; i++) {
            if (pCakeArray[i] < pCakeArray[i - 1]) {
                return false;
            }
        }
        return true;
    }

    public void revert(int nBegin, int nEnd) {
        int t;
        for (int i = nBegin, j = nEnd; i < j; i++, j--) {
            t = m_ReverseCakeArray[i];
            m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
            m_ReverseCakeArray[j] = t;
        }
    }

    /**
     * 输出翻转的位置信息
     * 搜索的次数
     * 翻转的次数
     * 翻转的每一步翻转情况
     */
    public void output() {
        for (int i = 0; i < m_nMaxSwap; i++) {
            System.out.printf("%d", m_SwapArray[i]);
        }

        System.out.printf("\n|Search Times|:%d\n", m_nSearch);
        System.out.printf("Total swap times = %d\n", m_nMaxSwap);

        perReverseArrayOutput(m_CakeArray,m_SwapArray,m_nCake,m_nMaxSwap);
    }
    /**
     * 通过记录每次翻转位置的数组,输入每次翻转的数组
     * 显示每一步的翻转结果
     * @param cakeArray  最初要排序的数组
     * @param swapArray  记录每次翻转时翻转的位置
     *@param nCake  数组的数量
     * @param maxSwap 翻转的次数
     */
    public static void perReverseArrayOutput(int[] cakeArray,int[] swapArray,int nCake,int maxSwap){
        System.out.printf("%d\n", maxSwap);
        int t;
        for(int i=0;i<maxSwap;i++) {
            System.out.printf("%d ",swapArray[maxSwap]);
            for (int x = 0,y = swapArray[i]; x < y; x++, y--) {

                t = cakeArray[x];
                cakeArray[x] = cakeArray[y];
                cakeArray[y] = t;
            }

            for(int k=0;k<nCake;k++){
                System.out.printf("%d ",cakeArray[k]);
            }
            System.out.print("\n");
        }

    }

    public void run(int[] pCakeArray,int nCake){
        init(pCakeArray,nCake);
        m_nSearch=0;
        search(0);
    }

}

六、参考博客

jinLei_zhao的博客(一摞烙饼的排序

Huaerge的博客(一摞烙饼的排序

     

时间: 11-16

编程之美—烙饼排序问题(JAVA)的相关文章

编程之美——烙饼排序问题

java实现: public class Cakes_Test {     private Integer[] m_CakeArray = null;//烙饼信息数组     private Integer m_nCakeCnt;//烙饼个数     private Integer m_nMaxSwap;//最多交换次数,最多为m_nCakeCnt * 2     private Integer[] m_SwapArray = null;//交换结果数组     private Integer[

《Java并发编程之美》(翟陆续著)高清pdf

<Java并发编程之美> 阿里巴巴技术专家力作,用代码说话.用实例验证,并发编程没有这么难!<Java并发编程的艺术>*作者方腾飞老师好评推荐! ? 百度网盘链接: https://pan.baidu.com/s/12oEEeDEO_YofImkpQA1bLA 提取码: pmkh  内容简介  · · · · · · 并发编程相比 Java 中其他知识点的学习门槛较高,从而导致很多人望而却步.但无论是职场面试,还是高并发/ 高流量系统的实现,却都离不开并发编程,于是能够真正掌握并发

《编程之美》之一摞烙饼的排序

星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯,程序员多喝了几杯之后谈什么呢?自然是算法 问题.有个同事说: “我以前在餐厅打工,顾客经常点非常多的烙饼.店里的烙饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小 次序摆好---小的在上面,大的在下面.由于我一只手托着盘子,只好用另一只手,一次抓住最上面的几块饼,把它们 上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了.我后来想,这实际上是个有趣的排序问题:假设有n块大小 不一的摞饼,那最少要翻几次,才能达到大小有序的结果呢?”

【编程之美】java实现重建二叉树

package com.cn.binarytree.utils; /** * @author 刘利娟 [email protected] * @version 创建时间:2014年7月20日 下午2:03:30 类说明: */ class Node { Node left; Node right; char chValue; Node(char chValue) { left = null; right = null; this.chValue = chValue; } } public cla

编程之美学习笔记之 一摞烙饼的排序

编程之美书中讲的一摞烙饼的排序一题 这里无法用基本的排序方法对其排序,那么最直接的方法是找出N个数种最大者,将这通过两次翻转放置到最底部,然后处理N-1,N-2等,直到全部排序完,所以一共需要交换2(N-1)次 void reverse(int cakes[], int beg, int end) { int temp; while(beg < end){ temp = cakes[beg]; cakes[beg++] = cakes[end]; cakes[end--] = temp; } }

java并发编程之美-阅读记录1

1.1什么是线程? 在理解线程之前先要明白什么是进程,因为线程是进程中的一个实体.(线程是不会独立存在的) 进程:是代码在数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,线程则是进程中的一个执行路径,一个进程中至少会有一个线程,进程中的多个线程共享进程的资源. 线程:是cpu分配的基本单位. 由上图可看出,一个进程中会有多个线程,多个线程共享堆和方法区,但是每一个线程都会有自己的栈和程序计数器. 为什么要将栈和程序计数器设置为线程私有的呢? 前边说线程是cpu执行的基本单位,而cp

读书问题之《编程之美》 -----12061161 赵梓皓

我阅读的书是<编程之美> 刚开始的时候阅读序,就觉得控制cpu利用率这个问题很好玩,所以重点看了这部分和解决办法,问题也都大部分是这部分的.那么问题就来了(挖掘机技术xxx?中国山东找蓝翔) 咳咳,问题在下面: 1.关于问题的提出.(也是一点点建议) 本书的主要内容是告诉读者如何思考问题和解决问题.但是提出问题也是很重要的,正如爱因斯坦所说“提出一个问题往往比解决一个问题更重要”,很多面试题(比如井盖为啥是圆的)我觉得正常人很少会想到.所以,这个问题是怎么想出来的...我很好奇.也希望作者能够

leetcode&amp;编程之美——博文目录

leetcode刷题整理: 1——Two Sum(哈希表hashtable,map) 2——Add Two Numbers(链表) 3——Longest Substring Without Repeating Characters(set,哈希表,两个指针) 9——Palindrome Number (数学问题) 11——Container With Most Water(两个指针) 12——Integer to Roman(string,数学问题) 13——Roman to Integer(s

编程之美笔记--第一章游戏之乐--1.2中国象棋将帅问题

后来一版作者又将最后一句改为:”要求在代码中只能使用一个字节存储变量“. 我的解法: package android.zlb.java; /** * * @author zhanglibin * */ public class TestXiangqi { public static void main(String[] args) { for(int i = 11; i < 100; i++) { if(i / 10 % 3 == 1 && (i % 10 == 1 || i % 1