黑马程序员技术交流社区

标题: 发几个有意思的算法小例子——摘自《编程之美》 [打印本页]
作者: zhouchl122    时间: 2015-3-5 22:22
标题: 发几个有意思的算法小例子——摘自《编程之美》
java基础不是很好，暂时发不了java相关的内容，不过既然是大数据方向，算法应该也是很重要的一块吧。
听同学介绍这本书，感觉还有点意思，借以抛砖引玉，引起大家对技术的兴趣。话不多说，开始小故事。
【一摞烙饼的排序】
星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：
“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌之前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。
我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？
你能否写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程呢？
分析与解法
这个排序问题非常有意思，首先我们要弄清楚解决问题的关键操作——“单手每次抓几块饼，全部颠倒”。


每次我们只能选择最上方的一堆饼，一起翻转。而不能一张张地直接抽出来，然后进行插入，也不能交换任意两块饼子。这说明基本的排序办法都不太好用。那么怎么把这n个烙饼排好序呢？
由于每次操作都是针对最上面的饼，如果最底层的饼已经排序，那我们只用处理上面的n-1个烙饼。这样，我们可以再简化为n-2，n-3，直到最上面的两个饼排好序。
解法一：
我们用图1-7演示一下，为了把最大的烙饼摆在最下面，我们先把最上面的烙饼和最大的烙饼之间的烙饼翻转（1~4之间），这样，最大的烙饼就在最上面了。接着，我们把所有烙饼翻转（4~5之间），最大的烙饼就摆在最下面了。


之后，我们对上面n-1、n-2个饼重复这个过程就可以了。
那么，我们一共需要多少次翻转才能把这些烙饼给翻转过来呢？
首先，经过两次翻转可以把最大的烙饼翻转到最下面。因此，最多需要把上面的n-1个烙饼依次翻转两次。那么，我们至多需要2（n-1）次翻转就可以把所有烙饼排好序（因为第二小的烙饼排好的时候，最小的烙饼已经在最上面了）。
这样看来，单手翻转的想法是肯定可以实现的。我们进一步想象怎么减少翻转烙饼的次数吧。
怎样才能通过程序来搜索到一个最优的方案呢？
首先，通过每次找出最大的烙饼进行翻转时一个可行的解决方案。那么，这个方案是最好的一个吗？考虑这样一种情况，假如这对烙饼中有好几个不同的部分相对有序，凭直觉来猜想，我们可以先把小一些的烙饼进行翻转，让其有序。这样会比每次翻转最大的烙饼要更快。
既然如此，有类似的方案可以达到目的吗？比如说，考虑每次翻转的时候，把两个本来应该相邻的烙饼尽可能的换到一起。这样，当所有的烙饼都换到一起之后，实际上就是完成排序了。（从这个意义上来说，每次翻最大的烙饼的方案实际上就是每次把最大的和次大的交换到一起。）
这样的基础之上，本能的一个想法就是穷举。只要穷举出所有可能的交换方案，那么，我们一定能够找到一个最优的方案。
沿着这个思路去考虑，我们自然就会使用动态规划或者递归的方法来进行实现了。可以从不同的翻转策略开始，比如说第一次先翻最小的，然后递归把所有的可能全部翻转一遍，这样，最终肯定是可以找到一个解的。
但是，既然是递归，就一定有退出的条件。在这个过程中，第一个退出的条件肯定是所有的烙饼已经排好序。那么，有其他的吗？如果大家仔细想想就会发现到，既然2（n-1）是一个最多的翻转次数。如果在算法中，需要翻转的次数多余2（n-1），那么，我们就应该放弃这个翻转算法，直接退出。这样，就能够减少翻转的次数。
从另外一个层面上来说，既然这是一个排序问题。我们也应该利用到排序的信息来进行处理。同样，在翻转的过程中，我们可以看看当前的烙饼数组的排序情况如何，然后利用这些信息来帮助减少翻转次数的判断过程。
当烙饼不多的时候，我们已经可以很快的找出最优的翻转方案。
我们还有办法来对这个程序进行优化，使得能更快的找出最优方案吗？
我们已经知道怎么构造一个可行的翻转方案，所以最优的方案肯定不会比这个差。这个就是我们程序中的上界（UpperBound），就是说，我们感兴趣的最优方案最差也就是我们刚刚构造出来的方案了。如果我们能够找到一个更好的构造方案，我们的搜索空间就会继续缩小。
除了上界的改进，还有什么办法可以提高搜索效率吗？如果我们翻了若干次之后，又回到一个已经出现过的状态，我们还值得继续从这个状态开始搜索吗？我们怎样去检测一个状态是否出现过呢？
读者也许不相信，比尔盖茨在上大学的时候也研究过这个问题，并且发表过论文。你不妨跟比尔盖茨的结果比比吧。
作者: zhouchl122    时间: 2015-3-5 22:23
不知道报名流程里要求的技术博客要在哪儿发啊，智商拙计。知道的麻烦告诉一下。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2