精华内容
下载资源
问答
  • python-取矩阵的上下三角形矩阵

    千次阅读 2019-02-13 15:50:25
    python-取矩阵的上下三角形矩阵
    arr = np.triu([[1, 2, 3], [4, 5, 6], [7, 8, 9]], 0)
    print(arr)
    
    展开全文
  • 求解三角形伴随矩阵的参考文献,根据这篇文献设计求逆矩阵思路如下: 求逆矩阵思路: 1.求矩阵的crout(LU)分解,其中L为三角矩阵,U为上三角矩阵 2.求L,U矩阵的伴随阵 3.求L,U矩阵的逆(伴随阵A* /det(A...
  • 一、子问题重叠:无论问题规模怎么变化,都是以三角形矩阵的方式呈现,大的三角形包含小的三角形,直到行数减小到2为止。 二、原问题的最优解包含子问题的最优解:通过最简单的方法,我称之为暴力带值。列出小问题...

    问题描述

    如下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大.

    在这里插入图片描述

    算法分析

    首先,该问题的解法符合动态规划的思想。

    一、子问题重叠:无论问题规模怎么变化,都是以三角形矩阵的方式呈现,大的三角形包含小的三角形,直到行数减小到2为止。

    二、原问题的最优解包含子问题的最优解:通过最简单的方法,我称之为暴力带值。列出小问题规模的结果,通过矩阵data[i][j]存入数值:

    在这里插入图片描述

    再生成value表:

    在这里插入图片描述

    通过value[i][j]-data[i][j]==value[i-1][j] or value[i-1][j-1]得出下一个路径。

    最终结果为:9->12->10->18->10.

    可以看出n=5的结果包含n=4的结果。符合题意。

    所以用动态规划思想对数塔自底向上计算,自顶向下分析的方式实现算法。

    算法实现

    1.建立二维数组data[n][n]存放给定数值,建立方法get()输出三角形矩阵。

    2.建立与data[n][n]相同的二维数组dp[n][n],用于自底向上创建value表。

    核心算法:

    在这里插入图片描述

    3.通过对value表的编辑得出path表。

    核心算法:

    在这里插入图片描述

    4.设置算法执行时间函数,得出算法所需时间。

    5.输出结果(取一次)

    在这里插入图片描述

    结果比较

    在这里插入图片描述

    复杂度分析

    ​ 路径最大值之和。二重循环,时间复杂度:O(n2)。二维数组,空间复杂度:O(n2)。

    ​ 路径排列。一重循环,时间复杂度:O(n)。二维数组,空间复杂度:O(n2)。

    源代码

    import java.text.SimpleDateFormat;
    import java.util.Scanner;
    import java.util.Date;
    
    public class Trangle {
        static int N=50;
        int[][] dp =new int[N][N];
        int n;
        int[][] data =new int[N][N];
        private void max_write(int q){
            int temp_max;
            for (int i = 0; i < q; i++) {
                for (int j = 0; j <= i; j++) {
                    dp[i][j] = data[i][j];
                }
            }
            for (int i = q-1; i >=0; i--) {
                for (int j = 0; j <=i; j++) {
                    temp_max = Math.max(dp[i+1][j],dp[i+1][j+1]);// i+1为空,为了保证dp[i][j]准确输出。
                    dp[i][j] = temp_max + data[i][j];
                }
            }
            System.out.println("最大值为:"+dp[0][0]);
        }
    
        private void route(int p){
            int a;
            int j=0;
            System.out.print("最大值路径:"+data[0][0]);
            for (int i = 1; i < p; i++) {
                a = dp[i-1][j]-data[i-1][j];
                if (dp[i][j+1]==a) ++j;
                System.out.print("->"+data[i][j]);
            }
        }
        private void get(int m){
            System.out.println("输入节点数据:");
            Scanner sc = new Scanner(System.in);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j <=i; j++) {
                    data[i][j] = sc.nextInt();
                    System.out.print(data[i][j]+",");
                }
                System.out.println("");
            }
        }
        public static void main(String[] args) {
            System.out.print("输入层数:");
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            Trangle t =new Trangle();
            t.get(n);
            long startTime = System.currentTimeMillis();
            SimpleDateFormat df = new SimpleDateFormat("\n"+"yyyy-MM-dd HH:mm:ss");
            System.out.println(df.format(new Date()));
            t.max_write(n);
            t.route(n);
            long endTime = System.currentTimeMillis();
            System.out.println(df.format(new Date()));
            System.out.println("\n"+"执行时间"+(endTime-startTime)+"ms");
        }
    }
    
    
    展开全文
  • 在做此题时,首先运用了跟1745矩阵最大路径一样的作法,自顶而,状态转移方程:a[i[[j]+=max(a[i-1][j],a[i-1][j-1]),但是WA了。必须改成自底而上的方式才能AC掉。在网上找类似的题,发现Leetcode:三角形阵列...

    在做此题时,首先运用了跟1745矩阵最大路径一样的作法,自顶而下,状态转移方程:a[i[[j]+=max(a[i-1][j],a[i-1][j-1]),但是WA了。必须改成自底而上的方式才能AC掉。在网上找类似的题,发现Leetcode:三角形阵列最小和 一题,可以使用自顶而下。为什么POJ是这样还没有搞明白,思考了很久不觉得两者有什么除了顺序上的区别。望高手告知!

    附上代码:

    #include <iostream>
    #include <cstring>
    using namespace std;
    #define maxn 101
    int a[maxn][maxn];
    int main()
    {
    	int n;
    	while(cin>>n)
    	{
    		memset(a,0,sizeof(a));
    		for(int i=1;i<=n;i++)
    		{
    			for(int j=1;j<=i;j++)
    			{
    				cin>>a[i][j];
    			}
    		}
    		for(int i=n-1;i>=1;i--)
    		{
    			for(int j=1;j<=i;j++)
    			{
    				a[i][j]+=a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
    			}
    		}
    		cout<<a[1][1]<<endl;
    	}
    }


    展开全文
  • /**************************************** * File Name : arithmetic.c * Creat Data : 2015.2.4 * Author : ZY *****************************************.../*Algorithm Gossip: 上三角形,下三角形,对称矩阵*
    /**************************************** 
    *  File Name  : arithmetic.c 
    *  Creat Data : 2015.2.4
    *  Author     : ZY 
    *****************************************/ 
    
    
    
    /*Algorithm Gossip: 上三角形,下三角形,对称矩阵*/
    /*上三角形:Aij = 0,i > j
      下三角形:Aij = 0,i < j
      对称矩阵:对称于对角线*/
    /*假设矩阵为n*n,将阵列索引由1开始,
    上三角矩阵化为一维阵列:
    若以列为主,其公式为:loc = n*(i-1)-i*(i-1)/2+j
    若以行为主,其公式为:loc = j*(j-1)/2+i
    下三角矩阵化为一维阵列:
    若以列为主,其公式为:loc = i*(i-1)/2+j
    若以行为主,其公式为:loc = n*(j-1)-j*(j-1)/2+i*/
    
    
    #include <stdio.h>
    #define N 5
    int main(void)
    {
    	int arr1[N][N] = {
    		{1,2,3,4,5},
    		{0,6,7,8,9},
    		{0,0,10,11,12},
    		{0,0,0,13,14},
    		{0,0,0,0,15}
    	};
    	int arr2[N*(1+N)/2] = {0};
    	int i,j,k = 0;
    	printf("原矩阵表示为:\n");
    	for(i = 0;i < N;i++)
    	{
    		for(j = 0;j < N;j++)
    		{
    			printf("%4d",arr1[i][j]);
    		}
    		printf("\n");
    	}
    	printf("\n以列为主:\n");
    	for(i = 0;i < N;i++)
    	{
    		for(j = 0;j < N;j++)
    		{
    			if(arr1[i][j] != 0)
    			{
    				arr2[k++] = arr1[i][j];
    			}
    		}
    	}
    	for(i = 0;i < N*(1+N)/2;i++)//除去0输出
    	{
    		printf("%4d",arr2[i]);
    	}
    	printf("\n输出索引(i,j):");//增添索引来快速得出数据,不包含0
    	scanf("%d,%d",&i,&j);
    	k = N*i-i*(i+1)/2+j;
    	printf("(%d,%d) = %d",i,j,arr2[k]);
    	printf("\n");
    	return 0;
    }
    

    展开全文
  • public class Triangle { public static void main(String[] ... //带对角线的Upper三角形 int[][] arr=new int[][]{ {4,5,8,6,9}, {7,9,3,5,8}, {3,5,1,1,4}, {5,8,7,4,9}, {1,4,7,8,9} }; Sys
  • //求3*3矩阵下三角形的和 #include <stdio.h> int main(){ int a[3][3]={1,2,3,4,5,6,7,8,9}; int i,j,sum=0; for(i=0;i<3;i++){ for(j=0;j<=i;j++){ sum+=a[i][j]; ...
  • #include<iostream> using namespace std; int main() { int matrix[3][3]; for (int i = 0;...//输入一个3*3的矩阵 } } int a = 0, b = 0, c = 0; int(*p)[3] = matrix; for (int i
  • } if ((it - p.begin() + 1) % (a) == 0)//注意此if和下面的if语句的位置区别,根据上三角还是三角判断。 i++; val1 += *it; } cout 上三角数之和为:" (p.begin() + i + a * (i))) { if ((it - p.begin() +...
  • 矩阵

    2020-05-28 17:38:49
    开发工具与关键技术:VS, ASP.NET MVC 作者:谭威 撰写时间:2019年05月28日 在数学中,矩阵是一个按照长方阵列排列的...五、上/下三角形矩阵:主对角线以下/上元素全为0的矩阵;六:行/列矩阵:矩阵中只有一行/一列元
  • Problem Description 输入一个正整数n(1 Input ...接下来的n行为矩阵数据。...矩阵三角元素之和。 Example Input 5 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 Example Output
  • 旋转正方形矩阵Here is the C++ program to print upperhalf and ... 这是C ++程序,用于打印方矩阵的上半部和半部三角形。 #include<iostream> using namespace std; int main() { int a[10][10],i...
  • **为了获得三维空间中 三角形平面上的点和三角形三个点的位置关系,并将其展现在平面上(纹理映射用),需要将三维空间中的三角形矩阵变换,使其一点在原点上,一边在坐标轴上,平铺在xoz平面上。 解决方法:需要...
  • matlab之矩阵分解

    2019-10-03 18:04:58
    要求原矩阵为方阵,将之分解成一个上三角形矩阵(或是排列(permuted) 的上三角形矩阵)和一个下三角形矩阵,简称LU分解法。 注意:这种分解法所得到的上下三角形矩阵并非唯一,还可找到数个不同的一对上下三角形...
  • 矩阵分解-LU分解

    2020-10-09 15:06:09
    三角分解法是将原正方矩阵分解成一个上三角形矩阵或是排列 的上三角形矩阵和一个 下三角形矩阵,这样的分解法又称为LU分解法。它的用途主要在简化一个大矩阵的行列式值的计算过程,求逆矩阵,和求解联立方程组。不过...
  • 矩阵分解-Cholesky分解

    2020-10-09 14:32:02
    三角分解法是将原正方矩阵分解成一个上三角形矩阵或是排列的上三角形矩阵和一个 下三角形矩阵,这样的分解法又称为LU分解法。它的用途主要在简化一个大矩阵的行列式值的计算过程,求逆矩阵,和求解联立方程组。不过...
  • 并存储于n´n阶半三角矩阵中,半三角矩阵采用行序为主序顺序存储,存储空间用内存动态分配函数建立。 杨辉三角形的生成方法如下(设矩阵名为a,其i行j列元素计为ai,j): ai,0=1 and ai,i=1,for i=0,1,…, n-1;...
  • 对于对称矩阵 A,A(:)(完全“矢量化”)包含的信息比严格必要的要多,因为矩阵完全由对称性和三角部分决定,即 n(n+1) /2 主对角线上和下方的条目。 使用包构建的半向量化如下: > A(itril(size(A))), 对称 n×n ...
  • 数组与矩阵

    2020-08-26 16:12:56
    数组:存储空间链接的表结构 矩阵:带二维信息的数据,一般使用二维数组来存储矩阵。 特殊矩阵: 上三角形矩阵: [0][1][3][6] ...下三角形矩阵: [0][ ][ ][ ] [1][2][ ][ ] [3][4][5][ ] [6]
  • 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右角的路径,使得路径上的数字总和为最小。 说明:每次只能向或者向右移动一步。 贪婪法,从终点开始,到每一个方块都计算出最小路径,然后一直反推到...
  • MATLAB_2_矩阵处理

    2019-07-28 15:11:02
    MATLAB_矩阵处理 需要提到的数学知识 这里只是简单的了解,不做太多性质上的解释,或者以后更新吧。 名称 ...下三角形矩阵 对角线以上的元素全为零的矩阵 零矩阵 元素全为0的矩阵 幺矩阵 元...
  • WebGL三角形平移变换(矩阵方式)

    千次阅读 2017-09-25 23:15:29
    本程序通过矩阵运算方式实现一个三角形的平移变换任务,最终效果如图。 整个程序包含两个文件,分别是: 1. TranslatedTriangleMatrix.html &lt;!DOCTYPE HTML PUBLIC "-//W3C//DTD ...
  • 给定一个由n行数字组成的数字三角形图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 对于给定的由n行数字组成的数字三角形,编程计算...
  • 平面内三点A(x1,y1),B(x2,y2),C(x3,y3)求三角形面积(行列式表示法)。 此种数学方法是利用行列式求三角形面积的同时,可以判断给定一点在一条线的左侧/右侧,上侧/侧。
  • 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右角的路径,使得路径上的数字总和为最小。 说明:每次只能向或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 ...
  • 问题相关定义: (1)凸多边形的三角剖分:将凸多边形分割成...凸多边形三角剖分如图所示:  相关性质 在凸多边形P的一个三角形部分T中,各弦互不相交,且弦数已达到最大,即P的任一不在T中的弦必与T中某一弦...
  • 模型矩阵、视图矩阵、投影矩阵

    千次阅读 2019-07-30 23:41:24
    总而言之,模型视图投影矩阵=投影矩阵×视图矩阵×模型矩阵,模型矩阵将顶点从局部坐标系转化到世界坐标系中,视图矩阵将顶点从世界坐标系转化到视图坐标系,而投影矩阵将顶点从视图坐标系转化到规范立方体中。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 425
精华内容 170
关键字:

下三角形矩阵