Creative Commons License
本Blog采用 知识共享署名-非商业性使用-禁止演绎 3.0 Unported许可协议 进行许可。 —— Fox <游戏人生>

游戏人生

游戏人生 != ( 人生 == 游戏 )
站点迁移至:http://www.yulefox.com。请订阅本博的朋友将RSS修改为http://feeds.feedburner.com/yulefox
posts - 62, comments - 508, trackbacks - 0, articles - 7

编程之美:一摞烙饼的排序(未完成)

Posted on 2008-04-20 14:59 Fox 阅读(3801) 评论(13)  编辑 收藏 引用 所属分类: G游戏编程

Author: Fox

首先声明:本人没有解决掉这个问题。

相比第一道让CPU占用率曲线听你指挥对Windows系统中CPU占有率概念的考察和对API的使用,以及第二道中国象棋将帅问题对抽象建模的考察。这道题目才算是一道算法题吧?之前那两道尤其是中国象棋将帅问题总有点脑筋急转弯的味道。

题目:星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢?自然是算法问题。有个同事说:

“我以前在餐馆打工,顾客经常点非常多的烙饼。店里的饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小次序摆好——小的在上面,大的在下面。由于我一只手托着盘子,只好用另一只手,一次抓住最上面的几块饼,把它们上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了。

我后来想,这实际上是个有趣的排序问题:假设有n块大小不一的烙饼,那最少要翻几次,才能达到最后大小有序的结果呢?

你能否写出一个程序,对于n块大小不一的烙饼,输出最优化的翻饼过程呢?

排序问题是数据结构和算法中比较重要的一个了,之前在一篇被同事成为标题党的文章中因为提到排序中关于(非)稳定排序的概念还被很多TX鄙视了一番,甚至引来人身攻击,现在想来都有些后怕。

这道题目一眼看上去最先让我想到的居然是那道经典的汉诺塔(Tower of Hanoi)问题(当然,汉诺塔不算排序问题)。

1) 相似点★:

a. 都要不断调整位置,最终实现从小到大排好;

b. 都要借助中间量进行调整。

2) 不同处★:

a. 汉诺塔有多出来的两根针,翻烙饼只有一只手,明确说明没有第三只手;

b. 汉诺塔一次只能移动一个,翻烙饼没限制;

c. 汉诺塔要保证小的始终在上面,翻烙饼没限制;

d. 汉诺塔移动之前就有序,所以其移动次数是固定的,算法的逻辑也固定(不管是递归还是栈操作),翻烙饼没有这个前提。

3) 把题目用程序语言描述一下吧★:

a. Input : n.

b. Process : generate n random number 0-(n-1), sortting.

c. Output : 0, 1, ..., n-1, and move times num.

4) 存储结构★★★:

我最开始想到的是:这一摞烙饼其实就是一个双链表,每翻一次相当于将头节点H与某非头节点N进行如下变换:

H->next = N->next

N->prior = H->prior = NULL

N->next->prior = H

如果使用普通的双链表,这儿就有一个很明显的问题,H和N之间的所有节点(如果有的话)的前趋prior和后继next互换了,对于n比较大的情况,这个操作明显浪费时间啊(交换前趋prior和后继next和题目要求的翻几次似乎也没有关系吧?只是我作为一个一线的Coder考虑的太具体了)。如果摒弃前趋和后继的概念,又该怎样描述呢?

唐朝禅宗大师青原行思曾说:参禅之初,看山是山,看水是水;禅有悟时,看山不是山,看水不是水;禅中彻悟,看山仍然山,看水仍然是水

俗:日,扯那么多,什么意思?

师:前趋不是前趋,后继不是后继。

俗:日,前趋不是前趋,难道是后继吗?

师:然也。

Fox:O, my God!整点实际的吧!翻转一次之后,前趋视为后继,后继视为前趋,第奇数次翻转的前趋是后继,第偶数次翻转的后继是前趋。

整个链表的形态如下:

H:Head, F:First, G:F's next, B:C's prior, C:Change, D, C's next, L:Last.

H<==>F<==>G<=...=>B<==>C<==>D<=...=>L

F与C交换的操作如下(Word、PS画图),n表示next,p表示prior:

这里只需要修改F、D节点的prior,H、C节点的next,其他节点不变。

后面想了一下,这种方式很难在不添加flag或者对换n、p的情况下正常操作,没有找到好的方法L如果你有好的方法不妨告诉我

最后只好作罢,何苦呢?直接使用数组就完了嘛J!既然是数组,除了翻转移动麻烦一点,理解和操作还是很容易的。

果然不是搞数学、算法出身的,一上来考虑的就是如何存储^.^'''',而不是算法本身。

更可笑的是,扯了半天,最后居然还是用数组

5) 算法分析★★★★★:

冒泡排序思想:

最关键的是要抽象出随机数列特征(含当前和移动后数列特征的抽象),并尽量使每一次翻转有效(所谓有效,即尽量保证每一次操作都向最后的有序靠近而非背离 )。

师:要使大头在后,应使大头在后。

俗:日,这是什么狗屁逻辑?

师:因果。在前既是在后。

俗:USA, CNN(操你娘)。

师:翻转。既不在前,也不在后,使之在前,使之在后。

俗:日,什么东西?既不在前,也不在后,不前不后,难道在中间啊?

师:然也。

Fox:O, my God!整点实际的吧!整个过程分为n轮,在第i(i=0, 1, ..., n-1)轮:

a. 找到大头n-i,是否有序?是,转g;

b. 是否大头在后?是,转f;

c. 是否大头在前?是,转e;

d. 将队头(第一个元素)与大头n-i对调(别忘了是翻转,中间元素也变序了),++times

e. 将队头n-i与第n-i个元素对调,++times

f. ++i,转a;

g. 输出序列(0, 1, ..., n)和翻转次数times;OVER:D。

快速排序思想:

在最开始的时候,我就想到使用快速排序的思想,先使整个数列局部有序,最后调整使全部有序。悲哀的是,在我考虑 4 3 1 2这个数列的时候,我断定还要通过上面的方式重新像冒泡排序一样重新来过,立即放弃想法,于是给了上面的思路,而且坚定的认为这个方法已经很好。结果,下午GR告诉我他的反例:4 3 1 2 --> 2 1 3 4|--> 1 2| 3 4,“|”表示从该处翻转。

我必须承认,这才是好的方法,我过分拘泥于不去改动已经有序的部分。然而,这家伙只知道反驳我,却无法给出算法。

我只好自己重新考虑局部有序之后的问题。

十分钟后,我有了如下的答案(目前我能想到的最佳答案),但不得不承认,表述算法比给出一种情况对应的解要麻烦的多的多的多,假定A、B满足A==B-1,即A、B为相邻数列(为简单记,元素和数列统称数列)。则A、B的组合类型有8种:B(O)A(O)、B(C)A(O)、B(O)A(C)、B(C)A(C)、A(C)B(O)、A(O)B(O)、A(C)B(C)、A(O)B(C),O表示正向(obverse)C表示逆向(reverse),以1 2 3 4为例:

B(O)A(O):3 4 1 2<2>B(C)A(O):4 3 1 2<4>B(O)A(C):3 4 2 1<5>、B(C)A(C):4 3 2 1<7>;

A(C)B(C):2 1 4 3<1>A(O)B(C):1 2 4 3<3>A(C)B(O):2 1 3 4<6>、A(O)B(O):1 2 3 4<8>。

对应操作规则如下:

a. 0x0101: B(O)A(O) --> B(C)A(O); 3

b. 0x0001: B(C)A(O) --> A(C)B(O); 2

c. 0x0101: B(O)A(C) --> B(C)A(C);1

d. 0x0000: B(C)A(C):如果当前只剩A、B两个子列,则翻转一次成A(O)B(O)1 2 3 4为最终结果,否则,认为B(C)A(C)可以作为一个逆序有序数列考虑,暂时无需翻转;

e. 0x1010: A(C)B(C) --> A(O)B(C); 3

f. 0x1110: A(O)B(C) --> B(O)A(C);  2

g. 0x1011: A(C)B(O) --> A(O)B(O);1

h. 0x1111: A(O)B(O):A、B可以作为一个有序数列考虑如果当前只有A、B两个子列,则正序序列A(O)B(O)1 2 3 4为最终结果

上面规则的制定其实是反向导出的,遵循的原则是,正序有序的A(O)B(O)和逆序有序的B(C)A(C)可以看作一个序列,A(C)B(O)、B(O)A(C)可一步达到,B(C)A(O)、A(O)B(C)可两步达到,B(O)A(O)、A(C)B(C)可三步达到。即对于4个元素,最坏的的A(C)B(C)需要4步(对应于上面的冒泡法却只需要3步L)。而且当元素比较多的时候,记住1、2个有序子列是可行的,但对于完全无序的数列,分析出所有有序子列,既不现实,也无必要。

修改规则如下:队头无序&&相邻数列有序||队头有序,翻转队头;否则,将队头连同该元素一同翻转

由此可见,这算法还要改进:

a. 判断Array[0]是否正序连续(连续个数nNum1),如果nNum1==n,转i,如果nNum1!=1,转c;

b. 判断Array[0]是否逆序连续(连续个数nNum1),如果nNum1==n,翻转Array,转f;

c. 从下标nNum1开始查找Array[0]+1(bObserve = true)和Array[0]-1(bObserve = false)的下标nStart2,如果nNum1==nStart2bOrder1==true,转e,如果nNum1!=1,置nEnd2=nStart2

d. 判断( bObserve == true&&Array[nStart2]+1==Array[nStart2+1] ) || ( bObserve == false&&Array[nStart2]==Array[nStart2+1]+1 ),true则置nEnd2=nStart2,false则置nEnd2=nStart2+1;

e. 翻转Array[0] to Array[nEnd2],转a;

f. 输出Arraytimes

这样来看,改进后的算法竟简单了许多!

不幸的是:按上面给出的算法翻转合并1 3 5 6 4 8 7 9 2 0:

1 3 5 6 4 8 7 9| 2| 0

2 9 7 8 4 6 5| 3| 1 0

3 5 6| 4| 8 7 9 2 1 0

4 6| 5| 3 8 7 9 2 1 0

5 6| 4 3 8 7 9 2 1 0

6 5 4 3 8| 7| 9 2 1 0

7 8 3 4 5| 6| 9 2 1 0

进入死循环了……

很明显应该是下面这个样子:

1 3 5 6 4 8 7 9 2| 0

9 8 7 4 6 5| 3 1 2 0

5 6 4| 7 8 9 3 1 2 0

6 5 4 7| 8 9 3 1 2 0

4 5 6 7 8 9 3| 1 2 0

3 4 5 6 7 8 9 1 2| 0

1 9 8 7 6 5 4 3 2| 0

2 3 4 5 6 7 8 9 1| 0

9 8 7 6 5 4 3 2 1 0|

0 1 2 3 4 5 6 7 8 9

执行9次翻转。算法如何得到呢?

a. 确定最小无序完整子集SnSn中含n>1个连续数);

b. 将Sn最前面的有序子集Soo>1)加以考虑,一个子集?两个子集?

______________________________________________________________________________

O, my God!

这个问题,从前天晚上到现在,思考、分析、抽象了至少有15个小时以上了:

a. Apr.18th-19th: 23:00 - 01:30

b. Apr.19th: 11:00 - 13:00

c. Apr.19th-20th: 22:00 - 05:30

d. Apr.20th: 11:00 - 15:00

结果是,到现在无法给出一个最优的翻转算法。一个周末都花在这上面了,准备放弃L

LP催着我让我回学校,是该回去了!

Feedback

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-21 09:59 by 亨德列克
这个跟那个0、1开关灯问题有点类似,书上有现成的解决方案;具体不记得了,翻下书就有了,LZ可以参考一下?
我是菜鸟,评论……可以忽略……

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-21 11:25 by yayv
栈排序

从上到下检查顺序, 出现逆序, 就截取,然后顺序出栈逆序入栈

如此反复,顺序正确之后,判断最上面是不是最小的,决定最后反转就是了么

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-21 20:21 by Fox
这个问题,如果有哪位TX实现了,给个链接我去学习一下,如果只是简单给出分析的话,就未必经得住推敲了……

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-22 11:11 by kayak
还没有认真考虑, 不过觉得用程序实现和人工翻转烙饼其实有一点是很不一样的.
就是人判断最大那个烙饼的时间复杂度是O(1), 用眼睛扫一下就可以了, 这点计算机做不到.
所以, 人工翻转烙饼的时候, 至少可以采用下面这个算法(可能不是最优, 但肯定有效):
1) 找出从上到下的N个烙饼中最大的烙饼.
2) 判断其是否在最下面, 如果是,到4; 否则到3.
3) 将最大烙饼及其上面的所有烙饼翻转.
4) 忽略此烙饼(N-1 -> N)
5) 如果N=0, 到6; 否则到1.
6) 结束.

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-22 12:26 by kayak
3写错了, 应该在后面加个3.1.
3.1) 将从上往下N个烙饼翻转.

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-22 12:38 by Fox
你这个在我文中给出来了,基于冒泡排序的思想。
次数不能达到最少。

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-23 12:16 by kayak
我相信不存在一种排序方式, 可以对于任何数据都比其他所有的算法更优.

我想确定一下, 你的目的是
1) 找到一种翻转算法, 它比任何其他算法"次数"更少的翻转算法, 或者在大多数情况下次数更少.
2) 对任何一种烙饼分布情况, 找到对于特定于该情型的特定的翻转方式.

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-23 17:56 by Fox
我的本意是找一种最优算法,可惜数学基础太差,对各种算法及其复杂性的计算力不从心……

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-25 13:14 by Bugs
很有趣!

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-04-29 22:41 by HYin
昨天刚买了这本书,学习中呀!

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2008-07-03 21:26 by 我也是想到了汉诺塔啊~~
我也是想到了汉诺塔啊~~

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2011-07-27 12:03 by pzmj
这么简单的问题,写了这么多废话,也算是人才了。。。

# re: 编程之美:一摞烙饼的排序(未完成)  回复  更多评论   

2014-08-30 16:07 by you
U can U up , no can no BB@pzmj

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理