我对算法很感兴趣，这次介绍的煎饼排序问题是在很多算法课程上都介绍过的经典例子。如果这是你第一次接触这个问题，我非常建议你在阅读时先独立思考解决方法。下面我们开始，希望大家喜欢咯。
- 煎饼排序： 维基百科给出的释义煎饼排序是数学上的一个问题的一种通俗叫法：对一堆无序的煎饼以大小排序，铲子可以在任意位置伸进去并且把上面的煎饼都翻转过来。
通俗点说，我们有一个锅铲和一堆煎饼，我们的目标是将煎饼按照大小排序，大的在下面。我们唯一的办法是让锅铲从一个地方伸进去，并且把上面所有的煎饼翻下来。举个栗子，一开始的煎饼是这样子的：
我们决定在这里铲入：
红色箭头代表插入位置，蓝色的表示新的煎饼堆底。
就是这样！
- 煎饼排序算法
（在你往下看之前，我建议你先自己想想解决办法。）
我现在讲的不是最好的办法，但是却是最直观最容易解释的。我选这种方法是为了向人们展示有些算法是非常容易并且直观的。我希望大家看了以后都能来尝试一下算法。通常，计算机专业会把普通人都吓跑，因为它一开始看上去太令人紧张。在这篇文章最后我将贴上更快的算法的链接。
- 将问题分解开来：
- 我们需要将煎饼排序，初始的形状可能是任意的。
- 我们只能对一部分煎饼进行翻转。
- 如果想让某一块特定的煎饼在最下面，需要先把它翻到最上面。
- 因此想要排好一块煎饼就需要先翻一下把它翻到顶上再把它翻到下面才行。
- 凭直觉想出来的算法
- 把未排序的煎饼中最大（或者顺序在最后）的煎饼翻下去（需要两步）。
- 重复第一步。
既然我们有了算法，那么我们就来思考一下看它正确与否吧：
- 只有一个煎饼的时候正确吗？——正确。
- 两个煎饼，大的在上，正确吗？——正确，我们翻一下就行了。
- 如果有三个煎饼，顺序从上到下依次是：中、大、小，正确吗？正确，我们先把大的翻上去，现在从上到下依次是大、中、小；然后我们再整个翻一下，顺序就变成了小、中、大。
既然在这几种简单情况下都是正确的，那么我们不妨用Python写出来吧~（欢迎在Github上Fork我的代码。）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
# Sorts Pancakes def sortPancakes(stack): sorted_index = 10 for i in reversed(range(len(stack))): stack = flip(stack, findLargestPancake(stack, i)) print("Flip Up", stack) stack = flip(stack, i) print("Flip Down", stack) return stack # All of the pancakes are sorted after index # Returns the index of largest unsorted pancake def findLargestPancake(stack, index): largest_pancake = stack[index] largest_index = index; for i in range(index): if stack[i] > largest_pancake: largest_pancake = stack[i] largest_index = i print "" print("Insert Spatula in index", largest_index, "Size", largest_pancake) return largest_index # Slide spatula under pancake at index and flip to top def flip(stack, index): newStack = stack[:(index + 1)] newStack.reverse() newStack += stack[(index + 1):] return newStack stack = [1, 4, 5, 2, 3, 8, 6, 7, 9, 0] print"\nUnsorted:" print stack print "\nIterating:" stack = sortPancakes(stack) print "\nSorted:" print stack print "" |
我们运行一下程序：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
Unsorted: [1, 4, 5, 2, 3, 8, 6, 7, 9, 0] Iterating: (‘Insert Spatula in index’, 8, ‘Size’, 9) 我对算法很感兴趣，这次介绍的煎饼排序问题是在很多算法课程上都介绍过的经典例子。如果这是你第一次接触这个问题，我非常建议你在阅读时先独立思考解决方法。下面我们开始，希望大家喜欢咯。
通俗点说，我们有一个锅铲和一堆煎饼，我们的目标是将煎饼按照大小排序，大的在下面。我们唯一的办法是让锅铲从一个地方伸进去，并且把上面所有的煎饼翻下来。举个栗子，一开始的煎饼是这样子的：
我们决定在这里铲入： 红色箭头代表插入位置，蓝色的表示新的煎饼堆底。
就是这样！
（在你往下看之前，我建议你先自己想想解决办法。） 我现在讲的不是最好的办法，但是却是最直观最容易解释的。我选这种方法是为了向人们展示有些算法是非常容易并且直观的。我希望大家看了以后都能来尝试一下算法。通常，计算机专业会把普通人都吓跑，因为它一开始看上去太令人紧张。在这篇文章最后我将贴上更快的算法的链接。
既然我们有了算法，那么我们就来思考一下看它正确与否吧：
既然在这几种简单情况下都是正确的，那么我们不妨用Python写出来吧~（欢迎在Github上Fork我的代码。）
我们运行一下程序：
|
