javatagle.cpp

数字三角形问题,使用动态规划算法解决问题,包含输入输出文件

思路: 
1.算出每个节点的规划值(也就是待比较的最大值),并记录搜索路径 
2.取三角形底边所有规划值中的最大值 
3.输出路径 

主程序 

 import  java.util. * ;
 /** 
 *  用动态规划法求出最优路径
 *   @author  zqc
 *  */ 
  public   class  DynamicSolveTrianglePath   {
    
     private  String[][] str_triangle  =   null ;
     private  Node[][] triangle_nodes  =   null ;
     private  List nodes;
     private  List paths;
    
     // 节点 
       static   class  Node  {
         private   int  value;
         private  List path  =   new  Vector();
         public  List getPath()   {
             return  path;
        } 
          public   void  setPath(List p)  {
            path  =  p;
        } 
         // n=(0,0) or (0,1) or (2,2) 
           public   void  addPath(String n)  {
            path.add(n);
        } 
          public   void  addPath(List pa)  {
            path.addAll(pa);
        } 
          public   int  getValue()   {
             return  value;
        } 
          public   void  setValue( int  value)   {
             this .value  =  value;
        } 
    } 
    
     public  DynamicSolveTrianglePath()  {
        initNodes();
        findPath();
    } 
    
     // 从根节点开始,逆向推解出到达所有节点的最佳路径
    private void initNodes(){
        this.str_triangle = ReadTriangle.getTriangle();
        triangle_nodes = new Node[str_triangle.length][];
        nodes = new Vector();
        for(int i = 0 ; i < str_triangle.length; i++){
            triangle_nodes[i] = new Node[str_triangle[i].length];
            for(int j = 0 ; j< str_triangle[i].length;j++){
                String currentPath = "("+i+","+j+")";
                Node n = new Node();
               if(i==0&&j==0){
                   n.setValue(c(str_triangle[0][0]));
                   n.addPath(currentPath);
                   triangle_nodes[i][j] = n;
                   continue;
               }
               //左右边界节点
               if((j==0||j==str_triangle[i].length-1)){
                   if(i==1){//第2行的节点
                       int value = c(str_triangle[0][0])+c(str_triangle[i][j]);
                       List ph = triangle_nodes[0][0].getPath();
                       n.addPath(ph);
                       n.addPath(currentPath);
                       n.setValue(value);
                       ph = null;
                   }else{//0,1行以下的其他边界节点
                     int value = j==0?c(str_triangle[i][j])+triangle_nodes[i-1][j].getValue():
                         c(str_triangle[i][j])+triangle_nodes[i-1][j-1].getValue();
                     List ph = j==0?triangle_nodes[i-1][j].getPath():
                         triangle_nodes[i-1][j-1].getPath();
                     n.addPath(ph);
                     n.addPath(currentPath);
                     n.setValue(value);
                   }
               }else{//除边界节点外其他节点
                       Node node1 = triangle_nodes[i-1][j-1];
                       Node node2 = triangle_nodes[i-1][j];
                       Node bigger = max(node1,node2);
                       List ph = bigger.getPath();
                       n.addPath(ph);
                       n.addPath(currentPath);
                       int val = bigger.getValue()+c(str_triangle[i][j]);
                       n.setValue(val);
               }
              triangle_nodes[i][j] = n; 
              n = null;
            }//end of for j
        }//end of for i
    }
    
    private Node max(Node node1,Node node2){
        int i1 = node1.getValue();
        int i2 = node2.getValue();
        return i1>i2?node1:node2;
    }
    
    private int c(String s){
        return Integer.parseInt(s.trim());
    }
    
    //找出最佳路径
    private void findPath(){
        if(this.triangle_nodes==null)return;
        int max = 0;
        int mi = 0;
        int mj = 0;
        for(int i = 0 ; i < triangle_nodes.length; i++){
            for(int j = 0 ; j< triangle_nodes[i].length;j++){
                int t = triangle_nodes[i][j].getValue();
                if(t>max){
                    max = t;
                    mi = i;
                    mj = j;
                }
            }
        }
        System.out.println("Max Path:"+triangle_nodes[mi][mj].getPath());
        System.out.println("Max Value:"+max);
    }
    
    public static void main(String[] args)throws Exception{
        DynamicSolveTrianglePath dsp = new
           DynamicSolveTrianglePath();
    }
    
} 
 
用于读取文件的辅助类 



 import  java.io. * ;
 import  java.util. * ;
/** 
 *  输入文本格式为
 *  类似这样一个数字三角形
 *  
 *          x
 *         x x
 *        x x x
 *       x x x x
 *      x x x x x 
 *      
 *   @author  zqc
 *  */ 
  public   class  ReadTriangle   {
     public   static  String TRIANGLE_FILE  ="c:/java/triangle.txt" ;
    
     public   static  String[][] getTriangle()  {
        String[][] rtn;
         try{
            File f  =new File(ReadTriangle.TRIANGLE_FILE);
            BufferedReader br=new BufferedReader(new  FileReader(f));
            List l  =new Vector();
            String line  =br.readLine();
             while (line != null )  {
                l.add(line.trim());
                line=br.readLine();
            } 
             int heigth=l.size();
            rtn  =new  String[heigth][];
             for ( int i  =0  ; i< heigth ; i ++ )  {
                String s  = (String)l.get(i);
                String[] tk  =s.split(" ");
                 int  tklen  =tk.length;
                rtn[i]  =new String[tklen];
                 for ( int  k  =0  ; k  < tklen ; k ++ )  {
                    rtn[i][k]  =  tk[k];
                } 
            } 
             return  rtn;
        }   catch  (FileNotFoundException e)   {
            System.out.println("err1="+e);
        }   catch  (IOException e)   {
            System.out.println("err2="+e);
        } 
         return   null ;
    } 
   public static void main(String args[]){
       String[][] trn=ReadTriangle.getTriangle();
       System.out.println("toal="+trn.length);
       for(int i=0;i< trn.length;i++){
            System.out.println("ok="+trn[i].length);
            for(int j=0;j< trn[i].length;j++)              
              System.out.println(trn[i][j]);
      }
     }
    
} 


结果输出如下: 

Max Path:[(0,0), (1,0), (2,0), (3,1), (4,1), (5,2)] 
Max Value:39