算法笔记 14_数字三角形问题


一、问题描述

happysneaker.com

二、算法思想

自顶向下不断向下压缩相加三角形(数组),最后压缩成一排,取最大值(详见注释)。

三、代码如下 (C++)

//#include "stdafx.h"
#include <iostream>  
using namespace std; 

#define MAX 1000
int length[MAX][MAX];  //m[][] 作为记录长度的一个数组
int triangle[MAX][MAX]; //trianlge[][] 用来记录三角形各行值的数组

void main()  
{  
    while(1)
    {   
        int n,i,j,a,b;        
        int max = 0;    //max 作为记录最大值的变量初始化为0

        cout<<"Please input the number of rows:";        
        cin >> n;  //同时读取用户输入的行数

        //读取用户输入的三角形的各行的值
        cout << "Please input each value of the triangle: " << endl;        
        for(i=1; i<=n; i++)       
             for(j=1; j<=i; j++)  
                cin >> triangle[i][j];        
                
        //向下循环遍历整个三角形不断进行二分相加,然后比“较向左下”加与“向右下加”的大小,取较大值存入m[][],这相当于将三角形向下压缩
        for(i=1; i<=n; i++)  
        {  
            for(j=1; j<=i; j++)  
            {  
                //用a、b来分别记录左加与右加的值,最终比较判断,取较长的值
                a = length[i-1][j-1] + triangle[i][j]; //左加 
                b = length[i-1][j] + triangle[i][j]; //右加 
                if(a > b)  
                    length[i][j] = a;  
                else  
                    length[i][j] = b;  
            }  
        }
                
        //从第一行开始遍历整个m[][]记录数组,m[][]的行列数与triangle[][]的行列数是相同的,取最大值给max即最长路径 
        for(i=1; i<=n; i++)  
            if(length[n][i] > max)  //选出最后一行中最大的值
                max = length[n][i];  
        cout << "The biggest value is: " << max << endl;  
        cout << "--------------------------------------------------------------------" << endl;
    }
}


happysneaker.com

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论