We start with a stack n of pancakes of distinct sizes. The problem is to convert the stack to one in which the pancakes are in size order with the smallest on the top and the largest on the bottom. To do this, we are allowed to flip the top k pancakes over as a unit (so the k-th pancake is now on top and the pancake previously on top is now in the k-th position). For example: This problem is to write a program, which finds a sequence of at most (2n - 3) flips, which converts a given stack of pancakes to a sorted stack.
输入描述:
Each line of the input gives a separate data set as a sequence of numbers separated by spaces. The first number on each line gives the number, N, of pancakes in the data set. The input ends when N is 0 (zero) with no other data on the line. The remainder of the data set are the numbers 1 through N in some order giving the initial pancake stack.The numbers indicate the relative sizes of the pancakes. N will be, at most, 30.
输出描述:
For each data set, the output is a single-space separated sequence of numbers on a line. The first number on each line, K, gives the number of flips required to sort the pancakes. This number is followed by a sequence of K numbers, each of which gives the number of pancakes to flip on the corresponding sorting step. There may be several correct solutions for some datasets. For instance 3 3 2 3 is also a solution to the first problem below.
备注:
http:en.wikipedia.orgwikiPancake_sorting关于Pancake sorting的一种简单情况。就是有种方法可以保证至多2n-3次完成。类似于选择排序：先找出n各数字种最大的一个数n，假设所在位置为sn，那么先翻转前sn个数字f(sn)，使得n在最顶部，之后再翻转前n个元素f(n)，这样一来n就到了最底部。就是两次翻转。之后再选择第二大的假设为n-1，位置在sn-1，那么先翻转前sn-1个数字f(sn-1)，使得n-1在最顶部，之后再翻转前n-1个元素f(n-1)，这样一来n-1就到了倒数第二个。也是两次翻转。注意：每次对于第x大的元素要判断它是不是在倒是第x个位置上，若在就不用翻转这个数字了。一直进行n-2次，最多2n-4次翻转。剩下上面三个最小的1,2其它的都排序了。分成2种情况，顶多1次搞定：12：已经有序，不用翻转。21：一次，f(2)
加载中...