查看完整版本: 2008-03-26 Ruby 测试题(00007)

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

今天的题目是约瑟夫环。
简单介绍一下，N个人排成一圈，编号为1～n。
从1号开始报数，当报到M时，该位置的人出局，余下的人依然是一个圈，从下一个人开始报数（从1开始），再到第M个出局。
有三种求解的要求：
1、求出N个人报到M出局的情况下，哪个初始位置是最后一个出局的人；
2、求出N个人报到M出局的情况下，所有人出局的先后顺序；
3、如果N个人年龄各不相同（可以用一，二，三，四。。。来代替），在报到M出局的情况下，怎样的原始序列（即谁在1号位，谁在2号位。。。）可以保证出局者按年龄大小递增。

约瑟夫环一般如果能写正确，效率就不会有太大的问题。今天的目的是写出短小精悍的程序来。

不是很懂怎么把答案表达清楚。所以就写了一个函数～ 很土很local，不过努力了。
**** Hidden Message *****

对算法很不熟悉，看看先。

比短吗？那就空间换效率了

**** Hidden Message *****

[code]
p joseph(10,100)

[10, 1, 5, 7, 3, 2, 9, 4, 8, 6]
[/code]


rest *= n * m，原来用的是 rest *= (n - 1)，发现 m > n的时候有问题，
在考虑重复多少次比较合适的时候，发现很麻烦，这里懒得去计算了，反正是比短嘛~

rest *= n * m 是什么意思？

回复 #5 ops 的帖子

将 rest 这个数组重复 （n * m ）次，这样就把环变成了串～

**** Hidden Message *****

[[i] 本帖最后由 xavier 于 2008-3-28 20:47 编辑 [/i]]

楼上试一下joseph(6,3)

超过600分钟还不能编辑了.......
jmouse能不能给分析一下应该怎么改？

[code]class Ring
  attr_reader :last, :out_queue, :out_order,:units
  def initialize units, n
    #pass a array of individual member's age or pass the number of members
    #the array will be automatically created using random ages
    if units.is_a? Array
      @units, @m = units, units.size
    elsif units.is_a? Integer
      @units = []
      units.times{unless @units.include?(r=rand(100));@units << r else redo end}
      @m = @units.size
      puts "Random ring: #{@units.join(", ")}\n\n"
    end
    @n = n
    run
  end
  
  def run
    units, m, n, start, outs =@units.dup,@m,@n, 0,[]
    while m > 0
      if n <= m
        pos = start - n
      else
        pos = start - n % m
      end
      outs << units.delete_at(pos)
      m -= 1
      start = pos < 0 ? m + pos : pos
    end
    @out_queue, @last = outs, outs.last
    @out_order = outs.inject([]){|a,el| a << @units.index(el)}
   
  end
end

##-- run it --##
if ARGV[1]
  ring = Ring.new(eval(ARGV[0]),ARGV[1].to_i)
else
  ring =Ring.new(30,25)
end

puts "The last one is #{ring.last} years old\n"
print "The members get out following this order: " + ring.out_queue.join(', ') + "\n\n"
print "Out order compare to original order:\n"

ring.out_order.each_with_index\
  { |e, i| puts "orig:#{i}, out:#{e}, age:#{ring.units[e]}"}[/code]

看看大家怎么求解的

约瑟夫环一般是在数据结构教材中当作单向链表例子来提起的。
我还不清楚Ruby是不是有链表相关的库，但是在基本数据结构没有链表的情况下，我们只能用数组之类的来模拟。
其实，主要问题是在怎么把“线”做成“环"。
rest *= n * m就是一个简单的方法。
而calebx和xavier的想法就是重新构造数组。
xavier的问题在于，算到后面，m会大于n的，所以要用对数组长度取余来做。
然后在写程序的时候要注意一些细节，数组下标从0开始的，我们的环是从1开始标的，这个要注意，所以xavier的程序里才产生了非常别扭的length==2以及[0]+这样的代码。
发现一个问题，为什么都是在弹出之后再构造新数组呢。我的程序：[code]def joseph(n,m)
  arr,out,m= (1..n).to_a,[],m-1
  n.times{
    arr = arr.last(arr.size-m%arr.size) + arr.first(m%arr.size)  
    out<<arr.delete_at(0)
  }
  puts out.join(",")
end
joseph(6,2)[/code]完全可以先转圈，再弹出第一个，这样循环看起来应该明了一些。对于数组0的处理，我把它简化到对M减一上去了。
blankego的程序还没来得及细看，稍后。

[[i] 本帖最后由 jmouse 于 2008-4-1 14:50 编辑 [/i]]

剛剛接觸RUBY，程序寫得很笨拙，多承 jmouse 的勉勵。

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

可能有bug，無奈math太差，就這麼著吧：）

这个题目太考算法了。有点偏理论化。
如果给出题目的时候同时给出算法，那样方便更多的人去练习如何能够正确规范的编写代码会比较好。

[[i] 本帖最后由 雪狼cn 于 2008-7-11 15:14 编辑 [/i]]

**** Hidden Message *****[code]f
l
r
d
k
s
g
o
c
n
e
q
j
h
b
i
p
m
a
t
>Exit code: 1[/code]