Linux Command
Ubuntu下挂载U盘

ghost leg (画鬼脚)

Jimmy posted @ 2011年10月28日 02:40 in Others , 4687 阅读

港大CS一年级data structure的作业,模拟“画鬼脚”游戏,编码测试花了三个小时,总算可以交差。在网上搜了下,发现这个简单游戏背后有着不简单的数学原理。

1. 游戏规则

画鬼脚又称画线抽签。是几个人需要用抽签来决定事物或工作的分配时,最简便的方式。进行时只需要一个能够画线的地方或物品就足够了,人数决定了竖线的条数。

在竖线的一端分别写上参与人,将需分配的事物或工作分成与人数的同等分后分别写在另一端。然后在每两个竖线相隔的区域,每个人任意的画上横线。每个人画横线的条数一般不限,但横线间不可交叉且横线不可横跨穿过两个间隔。

从写有自己名字的竖线一端开始,向另一端前进。每当遇上横线时,则沿着横线转弯走向另一根竖线,到达竖线后继续向前最终到达另一端,而这一端所写的事物便是你所抽到的事物。

2. 数学现象

当游戏结束时总是会出现1:1的对应关系,不会有多个人对应同一物品也不会有物品没有人对应。重要的是这个性质在任意条横线情况下均成立

3. 重要性质

a) 排列性

整个游戏过程会将一串输入元素排列变为另一串顺序不同的输出元素的排列

b) 周期性

可以将游戏过程看作对输入元素的变换M,则在对输入元素重复进行有限次变换后,输出元素排列会与输入元素排列相同。即 M^{n} = I

c) 可逆性

对任意变换M,存在变换M^{-1},使得M M^{-1} = I

d) 等价性

将输入序列变为同一输出序列的变换M的个数是无无限的,它们之间是等价的。那么如何寻找最小数目横线的变换呢?可以参考:http://en.wikipedia.org/wiki/Ghost_Leg

4. 游戏过程模拟

因为添加的横线距离顶端的高度不能相同,可以用链表结构来组织数据,然后设计链表上的游戏算法,整个过程也就显得清晰简单了。C代码可以从GitHub上下载: https://github.com/jia1546/ghostleg

Avatar_small
λ 说:
2011年10月28日 08:10

呵,看來你是 LaTeX 不會弄空格,到網上找一本《More Math into LaTeX》來看看就好了。
那個周期性的问题,矩阵实在不懂……

代码风格有点奇特,其实我觉得不用在 -> 左右留空格的。而且建议判断语句中该加的括号都加上,反正编译器会优化的。

还有,那三个参数 x,y,z 的具体作用没有一点点的注释,搞到我一开始实在不明白你弄了什么数据结构。狠狠地看才知道 z 是说第几条横线…… x,y 是指连接的鬼脚号……

Avatar_small
jia1546 说:
2011年10月28日 15:50

谢谢你的建议,我会在以后的代码规范中注意的。

Avatar_small
Shawn 说:
2011年10月28日 20:47

哈哈我也在做这个(yr2 IS),不过我记得assignment里要求要delete,所以我就用doubly linked list了,,


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter