2008-03-26 Ruby 测试题(00007)

看看大家怎么求解的
约瑟夫环一般是在数据结构教材中当作单向链表例子来提起的。
我还不清楚Ruby是不是有链表相关的库,但是在基本数据结构没有链表的情况下,我们只能用数组之类的来模拟。
其实,主要问题是在怎么把“线”做成“环"。
rest *= n * m就是一个简单的方法。
而calebx和xavier的想法就是重新构造数组。
xavier的问题在于,算到后面,m会大于n的,所以要用对数组长度取余来做。
然后在写程序的时候要注意一些细节,数组下标从0开始的,我们的环是从1开始标的,这个要注意,所以xavier的程序里才产生了非常别扭的length==2以及[0]+这样的代码。
发现一个问题,为什么都是在弹出之后再构造新数组呢。我的程序:

[Copy to clipboard] [ - ]
剛剛接觸RUBY,程序寫得很笨拙,多承 jmouse 的勉勵。

我的思路就是圍繞著Array 的負index 作文章(python的習慣)。 每次報數都是從右往左來,報到idx0 時再利用array的負值從 last端報起,前提是,不允許 m > n,通過取modulo實現,見 20-25行。(我把 m和n 弄顛倒了,抱歉)。另,我的新環不用 last x + first x 重新生成, 由於m 的絕對值一定 <= n 所以新起點可以 按 28行的 方法求得。

可能有bug,無奈math太差,就這麼著吧:)
这个题目太考算法了。有点偏理论化。
如果给出题目的时候同时给出算法,那样方便更多的人去练习如何能够正确规范的编写代码会比较好。

[ 本帖最后由 雪狼cn 于 2008-7-11 15:14 编辑 ]
本帖隐藏的内容需要回复才可以浏览