Back

前几天被一个动态规划的题目难倒了。。。( a dynamic program question:triangle. )

发布时间: 2012-08-20 04:40:00

参考:http://poj.org/problem?id=1163

做为一个WEB开发的人,我表示对数据结构一无所知,一塌糊涂,忘的一光二净,看题时一头雾水,解题时异想天开。所以。。。同学们不必看了。。。写在这里,就不往github上放了。。。

有个题目:给出一个树状结构:
            A
        B      C
     D     E     F
  G    H     I       J
列出所有可能的路径, 例如:  
1.  ABDG
2.  ABDH
3.  ABEH
4.  ABEI 。。。

一想就是个递归函数。。。头大啊。所以,我的思维不够灵光,只好用最笨的方法来遍历它。RUBY代码放在这里,有机缘的时候再试试其他的ACM题目吧。。。

class Tree
  def initialize(nodes)
    @nodes = nodes

    # init the matrix
    @matrix = []
    @nodes.each_with_index { |row, i | 
        @matrix[i] = []
        row.each_with_index { |cell, j|
            @matrix[i][j] = cell
        }   
    }   
  end 
  def print
    @matrix.each { |row| puts row.inspect; }
  end 
  def routes
    @result = []
    set_route_by_node(0, 0, "") 
    puts '==='
    puts @result
  end 
  def set_route_by_node(column_index, row_index, route_from_parent)
    route = route_from_parent + @matrix[row_index][column_index]
    puts "== considering: row:#{row_index}, column:#{column_index}, route: #{route}"
    # should return for the leaves.
    if row_index + 1 == @matrix.size
      puts '++++++++++++++++++++++++++++++++== a branch is done'
      @result << route
    else
      # left child
      puts '-- setting left child'
      set_route_by_node(column_index, row_index + 1, route)
      # right child
      puts '-- setting right child'
      set_route_by_node(column_index + 1, row_index + 1, route)
    end
  end
end

tree = Tree.new([['a'], ['b','c'], ['d','e','f'], ['g','h','i','j']])

# a
# b  c
# d  e  f
# g  h  i  j
tree.print

# "a,b,d,g"
# "a,b,d,h"
# "a,b,e,g"
# "a,b,e,h" ...
tree.routes

输出是:

sg552@siwei-moto:~/workspace/recursive_function_exams$ ruby print_tree.rb
["a"]
["b", "c"]
["d", "e", "f"]
["g", "h", "i", "j"]
== considering: row:0, column:0, route: a
-- setting left child
== considering: row:1, column:0, route: ab
-- setting left child
== considering: row:2, column:0, route: abd
-- setting left child
== considering: row:3, column:0, route: abdg
++++++++++++++++++++++++++++++++== a branch is done
-- setting right child
== considering: row:3, column:1, route: abdh
++++++++++++++++++++++++++++++++== a branch is done
-- setting right child
== considering: row:2, column:1, route: abe
-- setting left child
== considering: row:3, column:1, route: abeh
++++++++++++++++++++++++++++++++== a branch is done
-- setting right child
== considering: row:3, column:2, route: abei
++++++++++++++++++++++++++++++++== a branch is done
-- setting right child
== considering: row:1, column:1, route: ac
-- setting left child
== considering: row:2, column:1, route: ace
-- setting left child
== considering: row:3, column:1, route: aceh
++++++++++++++++++++++++++++++++== a branch is done
-- setting right child
== considering: row:3, column:2, route: acei
++++++++++++++++++++++++++++++++== a branch is done
-- setting right child
== considering: row:2, column:2, route: acf
-- setting left child
== considering: row:3, column:2, route: acfi
++++++++++++++++++++++++++++++++== a branch is done
-- setting right child
== considering: row:3, column:3, route: acfj
++++++++++++++++++++++++++++++++== a branch is done
===
abdg
abdh
abeh
abei
aceh
acei
acfi
acfj

Back