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

2008-04-03 Ruby测试题(00009)

感谢bbschat提供题目。

输入字符串，比如： "fb,bc,ac,eb,da,ga"
每组2个字母，用逗号分割。
第一个字母是节点，第2个字母是它的父结点。
写个函数处理输入字符串，并输出整个树的结构。

输出结果：
c
┣ a
┃┣ g
┃┗ d
┗ b
    ┣ e
    ┗ f

[[i] 本帖最后由 jmouse 于 2008-4-3 11:13 编辑 [/i]]

简化一下，不用去验证输入串是否正确。
也就是不会出森林，也不会绕循环。
最好是用题目给出的答案输出方式，退一步，如果用自己的方式输出，只要树构造对了，输出也是明了的，也可以。

子节点没有排序，不知算不算合格。

**** Hidden Message *****

[[i] 本帖最后由 AllenDang 于 2008-4-3 17:16 编辑 [/i]]

这么专业的东西还没接触过呢
过来学学吧

[code]#!/usr/bin/env ruby
class Tree
  attr_reader :name, :children
  def initialize name
    @name = name
  end
  
  def <<(nodeset) #append a child node
    @children = [] if ! @children
    @children << nodeset if (nodeset.is_a? Tree) &&
      !(@children.member? nodeset)
  end
  
  def [](childname) #access direct children by ['childname']
    @children.find{|n| n.name == childname}
  end
  
  def seek(nodename)#find an arbitrary descendant by name, return the node/nil
    if @name == nodename
      self
    elsif @children
      if got = @children.find{|child|child.name == nodename}#direct child?
        got
      else
        @children.each{|child| (got=child.seek(nodename))&&break}
        ## child of child of ...?
        got
      end
    end
  end
  
  def inspect(branch = '') #branchlines for non-root node
    diagram = ''  << branch + @name +"\n"
   
    if children
      tail = branch.slice!(-2,2)
      branch << case tail
        when nil ; ""
        when "|-" ; '┃'
        when "|_" ; '  '
      end
      children[0..-2].each{|child| diagram << child.inspect(branch + '|-')   }
      diagram << children.last.inspect(branch + "|_")
    end
    return diagram
  end
end

def assemble_tree(nodes)
  nodes = nodes.split(',').map!{|it| it.split('')}
  buffer=[]
  
  nodes.each do|n|
    #eliminate buffered tree if it has a parent
    sub = buffer.delete(buffer.find{|tr| tr.name == n[0] })
    sub = Tree.new(n[0]) unless sub
    failed = buffer.each do|tr|
      ## check if the given node is a subnode of one buffered tree
      (got=tr.seek(n[1])) && got << sub && break
    end
   
    if failed
      new_tree=Tree.new(n[1])
      new_tree << sub
      buffer.push(new_tree)
    end
  end
  raise "It's not a tree" if buffer.size > 1
  return buffer[0]
end
## test
tree = assemble_tree "fb,le,bc,ac,eb,me,da,ga,ha,jf,kh,nl,ol,pn,qp"
p tree

結果：
c
|-b
| |-f
| | |_j
| |_e
|   |-l
|   | |-n
|   | | |_p
|   | |   |_q
|   | |_o
|   |_m
|_a
  |-d
  |-g
  |_h
    |_k[/code]

[[i] 本帖最后由 blankego 于 2008-4-4 00:34 编辑 [/i]]

Cleaned up, fixed some bugs, added more comments, and sorting functions.[code]#!/usr/bin/env ruby
class Tree
  attr_reader :name, :children
  def initialize name
    @name = name
  end
  
  def <<(nodeset) #append a child node
    if nodeset.is_a?(Tree) && !(@children ||= []).include?(nodeset) #get it :)
       @children << nodeset
    end
    self ### Don't forget to return self
  end
  
  def [](childname) #access direct children by ['childname']. Not used in this example
    @children.find{|n| n.name == childname}
  end
  
  def seek(nodename)#find an arbitrary descendant by name, return the node/nil
    if @name == nodename
      self
    elsif @children
      if got = @children.find{|child|child.name == nodename}#direct child?
        got
      else
        @children.each{|child| (got=child.seek(nodename))&&break}
        ## child of child of ...?
        got
      end
    end
  end
  def <=>(other)#Needed for sorting
    self.name <=> other.name
  end
  def sort!
    @children.map!{|child|child.sort!}.sort! if @children
    self #Again, don't forget to return self, otherwise, it won't work
  end
  def inspect(branch = '') #branch is branchlines for non-root node
    diagram = ''  << branch + @name +"\n"
    #Every node has its own line,that's the idea
    if children #determine the "branch" for chidren according to the "tail" of the parent
      tail = branch.slice!(-2,2)
      branch << case tail
        when nil ; ""
        when "|-" ; '| '
        when "|_" ; '  '
      end
      children[0..-2].each{|child| diagram << child.inspect(branch + '|-')   }
      diagram << children.last.inspect(branch + "|_") #the last child has special look
    end
    return diagram
  end
end

def assemble_tree(nodes)
  nodes = nodes.split(',').map!{|it| it.split('')}#'ab,db'->[['a','b'],['d','b']]
  buffer=[]#temporary tree(nodeset) buffer
  
  nodes.each do|n|
    #eliminate buffered tree if it has a parent
    sub = buffer.delete(buffer.find{|tr| tr.name == n[0] })
    sub = Tree.new(n[0]) unless sub
    failed = buffer.each{|tr|
      ## check if the given node is a subnode of one buffered tree
      (got=tr.seek(n[1])) && got << sub && break #break will passes nil to failed
    }
    buffer << (Tree.new(n[1]) << sub) if failed
  end
  raise "It's not a tree" if buffer.size > 1
  return buffer[0]
end

## test
  p assemble_tree("kh,me,fb,le,bc,nl,ol,ac,eb,ha,ga,da,jf,pn,qp").sort!
=begin
+++++++++ output+++++++++++
c
|-a
| |-d
| |-g
| |_h
|   |_k
|_b
  |-e
  | |-l
  | | |-n
  | | | |_p
  | | |   |_q
  | | |_o
  | |_m
  |_f
    |_j
=end[/code]

本题延一天。
明天出新题。
太忙了。。。。

大学学的排序忘光了

=.= 我学过树么？学过么？没学过么？

[quote]原帖由 [i]jmouse[/i] 于 2008-4-7 09:56 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=13767&ptid=4099][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
本题延一天。
明天出新题。
太忙了。。。。 [/quote]

没有问题。

[quote]原帖由 [i]calebx[/i] 于 2008-4-8 09:41 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=13814&ptid=4099][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
=.= 我学过树么？学过么？没学过么？ [/quote]

你应该学过的，忘了吧。
我是忘了...呵呵...

反正我是没学过:(

树型结构这种东西在计算机里太常见了，比如文件夹就是典型的树型结构。一般都是自学的吧？一般在现存的树上动手脚比较容易点，根据随机内容生成一颗树就有点难了，
这题当初我在论坛帮另一个版主解答问题的时候做过，所以就不再贴代码了。

支持支持,呵呵

这个题完全没有想法，哎！追！

不错，顶起来206

不错，顶起来

[url=http://www.88324639.com/article_view.asp?id=46]电烤箱[/url]
[url=http://www.88324639.com/article_view.asp?id=46]烤炉[/url]
[url=http://www.88324639.com/article_view.asp?id=46]食品烤箱[/url]