Java实现输出数字三角形实例代码

目录
  • 题目:
  • 题解:
  • 代码:
  • 总结

题目:

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 nn，表示数字三角形的层数。

接下来 nn 行，每行包含若干整数，其中第 ii 行表示数字三角形第 ii 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤5001≤n≤500,
−10000≤三角形中的整数≤10000−10000≤三角形中的整数≤10000

输入样例：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例：

30

题解:

 相对于二维数组来看，每一个数只能往下放或者右下方走，发现从下往上走更加方便实现。我们反向思考，从下或者右下方走，如果我们每次都知道了某数的下放和右下方谁最大了呢?

        每次从最后行的相邻两个数比较谁最大，把每次最大的加到第一个数的上方，这样数组的第一行第一个数就是最大值了。

        例如:

代码:


import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int nums[][] = new int[n][];
        for(int i = 0;i<n;i++){
            nums[i] = new int[i+1];
            for(int j = 0;j<i+1;j++){
                nums[i][j] = sc.nextInt();

            }
        }
        for(int i =n-1 ;i>0;i--){
            for(int j = 0;j<nums[i].length-1;j++){
                nums[i-1][j] += Math.max(nums[i][j],nums[i][j+1]);
            }
        }
        System.out.println(nums[0][0]);

    }

}

总结

到此这篇关于Java实现输出三角形实例代码的文章就介绍到这了,更多相关Java输出三角形内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java编程实现帕斯卡三角形代码示例

    Java编程实现帕斯卡三角形代码示例

    源程序揭秘 杨辉三角形性质: 每行数字左右对称,由 1 开始逐渐变大,然后变小,回到 1. 第 n 行的数字个数为 n 个. 第 n 行数字和为 2^(n-1) . 每个数字等于上一行的左右两个数字之和.可用此性质写出整个杨辉三角形. 第 n 行的第 1 个数为 1,第二个数为 1× (n-1) ,第三个数为 1× (n-1) × ( n-2) /2,第四个数为 1× (n-1) × (n-2) /2× (n-3) /3-依此类推. 算法原理1: 使用一个二维数组 yh[][] 存储杨辉三角形的

  • Java数据结构及算法实例：三角数字

    /** * 三角数字: * 比达哥斯拉领导下的古希腊数学家发现了一个有趣的数字序列1, 3, 6, 10, 15, 21,... * 你能看出他们有什么规律么? * 对了它的规律就是f(x) = x+ f(x-1) * 想想是不是很像小时候打算盘从1一直加到100啊 */ package al; public class Triangle { public static void main(String[] args) { Triangle triangle = new Triangle();

  • Java基础之练习打印三角形

    Java基础之练习打印三角形

    一.打印直角三角形 这个循环控制打印十行空格 for (int x = 1; x <= 10; x++) {//因为要打印一个十行的直角三角形,这行表示先打印十行空格 System.out.println(); } 这个循环控制打印 星号 for (int y = 1; y <= x; y++) {//这个循环控制打印 System.out.print("*"); } 嵌套for循环 package com.kuang.struct; public class TestDe

  • Java实现输出数字三角形实例代码

    Java实现输出数字三角形实例代码

    目录 题目: 题解: 代码: 总结 题目: 给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输入格式 第一行包含整数 nn,表示数字三角形的层数. 接下来 nn 行,每行包含若干整数,其中第 ii 行表示数字三角形第 ii 层包含的整数. 输出格式 输出一个整数,表示最大的路径数字和. 数据范围 1≤n≤5001≤n≤50

  • java 实现输出随机图片实例代码

    java  实现输出随机图片实例代码 输出随机图片(CAPTCHA图像):Completely Automated Public Turing Test to Tell Computers and Humans Apart (全自动区分计算机和人类的测试) 相关主要类(JDK 查看API) BufferedImage:内存图像 Graphics:画笔 ImageIO:输出图像 放在html页面上<img src/> 注意:浏览器默认会缓存图片 public static int WIDTH =

  • java  实现输出随机图片实例代码

    java  实现输出随机图片实例代码 输出随机图片(CAPTCHA图像):Completely Automated Public Turing Test to Tell Computers and Humans Apart (全自动区分计算机和人类的测试) 相关主要类(JDK 查看API) BufferedImage:内存图像 Graphics:画笔 ImageIO:输出图像 放在html页面上<img src/> 注意:浏览器默认会缓存图片 public static int WIDTH =

  • Java编程实现打地鼠文字游戏实例代码

    控制台输入数字,与随机数匹配,匹配正确则返回"打中了!" 匹配错误则返回"太遗憾!没打中!" package hitmouse; import java.util.Random; import java.util.Scanner; public class HitMouse { public static void main(String[] args) { // TODO Auto-generated method stub int[] map = new int

  • Java制作验证码的完整实例代码

    JAVA代码制作验证码,可用于注册等功能页面 要导入servlet-api.jar包 创建验证码的Util工具类: 先创建图片并生成随机的验证码字母 设置图片的底色,并用setFont函数将验证码画在图片上,如果想让验证码难一点,可以添加for循环的代码给图片增加旋转角度 给验证码增加干扰线,提高安全性 设置边框 创建VerifyPic的servlet,通过Util类获取代码,并存入session中,然后输送去前端页面 前端页面验证码如下: 完整Util工具类代码如下: package com.

  • Java实现FTP服务器功能实例代码

    FTP(File Transfer Protocol 文件传输协议)是Internet 上用来传送文件的协议.在Internet上通过FTP 服务器可以进行文件的上传(Upload)或下载(Download).FTP是实时联机服务,在使用它之前必须是具有该服务的一个用户(用户名和口令),工作时客户端必须先登录到作为服务器一方的计算机上,用户登录后可以进行文件搜索和文件传送等有关操作,如改变当前工作目录.列文件目录.设置传输参数及传送文件等.使用FTP可以传送所有类型的文件,如文本文件.二进制可执

  • Java执行hadoop的基本操作实例代码

    Java执行hadoop的基本操作实例代码 向HDFS上传本地文件 public static void uploadInputFile(String localFile) throws IOException{ Configuration conf = new Configuration(); String hdfsPath = "hdfs://localhost:9000/"; String hdfsInput = "hdfs://localhost:9000/user/

  • java List 排序之冒泡排序实例代码

    java List 排序之冒泡排序实例代码 List排序,这里介绍两种排序: 1.Collections.sort()排序: 假如List集合中放的是Menu对象. public class Menu{ private int id; private String name; private int seq;//自定义排序字段 //构造函数.getter.setter省略....... } List<Menu> menus=new ArrayList<Menu>(); menus.

  • Java构建树形菜单的实例代码(支持多级菜单)

    Java构建树形菜单的实例代码(支持多级菜单)

    效果图:支持多级菜单. 菜单实体类: public class Menu { // 菜单id private String id; // 菜单名称 private String name; // 父菜单id private String parentId; // 菜单url private String url; // 菜单图标 private String icon; // 菜单顺序 private int order; // 子菜单 private List<Menu> children;

  • java随机验证码生成实现实例代码

    java随机验证码生成实现实例代码 摘要: 在项目中有很多情况下都需要使用到随机验证码,这里提供一个java的随机验证码生成方案,可以指定难度,生成的验证码可以很方便的和其他组件搭配 之前要使用一个生成随机验证码的功能,在网上找了一下,有很多的人提出了不同的解决方案,但是很多人都使用了com.sun.image.这个包或者子包里面的类,而这个包结构下面的类都是不推荐使用的,我们应该依赖于java.或者javax.这些包结构下面的类,否则将来的可移植性就很不好(比如换成IBM的JDK就不行了),但

随机推荐