问题很简单了,就是大小不同的盘子,摞在一次。如果通过反转,达到盘子最终上到下,为从小到大的顺序。
要求时,不能单独拿。一次必须是上面的几个一起反转。
方法一
最简单的方法,就是,冒泡的思想,我们先找最大的,然后反转到顶部,然后再反转到地步。重复。
但是,反转次数过多。
方法二
凡是这种什么最少几次,啥的。几乎都可以使用广度优先搜索解决。
我们以最终状态为起点(序好的状态),然后去遍历每一种反转的情况到起始状态(未排序状态)。
这里就涉及到如何记录这种盘子的状态。如果都是十个,那么使用一个很大的数来表示,不然就只能使用容器了,比较容器。
而且广度优先搜索得到的翻转步骤一定是最少的。
方法三
编程之美中使用的也是类似的方法,但他居然使用的是深度优先搜索。并且没有记录已经反转过的状态,这样不可避免的,会重复。所以使用最大的反转次数(2n)来返回上一步(预判断,进入某个状态的时候,先判断是否可能大于2n,如果大于直接return)。
其预判的标准的是,当前状态乱序的次数+当前已反转的次数<2n。