精华内容
下载资源
问答
  • 三角形数字问题

    2016-04-13 17:06:55
    输入第一行数字n是三角形的行数,接下来的n行是数字三角形的每一行,如:  5  7  3 8  8 1 0  2 7 4 4  4 5 2 6 5  输出是 30 思路:  1、递归+记忆法  用二维数组存储数字三角形中的...

    题目:

      给定一个数字三角形,找到从顶部到底部的最大路径和。每一步可以移动到下面一行的相邻数字上。输入第一行数字n是三角形的行数,接下来的n行是数字三角形的每一行,如:
       5
       7
       3 8
       8 1 0
       2 7 4 4
       4 5 2 6 5
      输出是 30

    思路:

      1、递归+记忆法
       用二维数组存储数字三角形中的每一行,不难发现,每个数字的节点nums[i][j]在扫描的过程当中都有两条可选路经(nums[i + 1][j]和nums[i + 1][j + 1]),所以可以把它看成是二叉树。类似二叉树的遍历,递归进行每个节点进行遍历,得到的值加上当前节点的值,取其较大者。在递归的过程中有重复计算的部分,比如在计算nums[2][0]的过程中计算了nums[3][1],而在计算nums[2][1]的过程中也计算了nums[3][1],所以可以用一个辅助数组将每次计算的值存储在visited[i][j]中,每次递归进去之后先判断是否在visited数组中,如果在则直接返回visited数组中的值,否则再递归计算。这样减少了递归的次数,大大节省了时间。
      2、动态规划
       由题可以得到递推式result[i][j] = max(nums[i + 1][j], nums[i + 1][j + 1]) + nums[i][j]。由自低向上进行编程(最后一行每一个元素的最优解就是本身),递推出每一个节点所能得到的最优解,然后result[0][0]的值就是所要求得的解。在这里为了节省内存,将nums数组和result数组使用同一个数组(即在nums数组中直接用每个节点的最优解替换原数值)。

    代码:

    1、递归+记忆法
    class Solution {
    public:
        int longestOfPath(std::vector<std::vector<int>> &nums, int i, int j) {
            if (nums.size() == 0) {
                return 0;
            }
            
            std::vector<std::vector<int>> visited;
            for (auto &a : nums) {               //初始化记忆化数组
                std::vector<int> tmp(a.size(), INT_MIN);
                visited.push_back(tmp);
            }
            
            return longestOfNumber(nums, i, j, visited);
        }
    private:
        int longestOfNumber(std::vector<std::vector<int>> &nums, int i, int j, std::vector<std::vector<int>> &visited)
        {
            if (nums.size() == i + 1) {
                return nums[i][j];
            }
            
            if (visited[i][j] != INT_MIN) {
                return visited[i][j];
            }
            
            int a = longestOfNumber(nums, i + 1, j, visited);          //左边
            int b = longestOfNumber(nums, i + 1, j + 1, visited);    //右边
            int result = maxNum(a, b) + nums[i][j];                          //计算结果
            visited[i][j] = result;                                                          //保存进记忆化数组
            
            return result;
            
        }
        inline int maxNum(int a, int b)
        {
            return a > b ? a : b;
        }
    };

    2、动态规划
    class Solution {
    public:
        int longestOfPath(std::vector<std::vector<int>> &nums)
        {
            for (int i = nums.size() - 2; i >= 0; --i) {             //从倒数第二行开始递推(倒数第一行每个节点的最优解是本身)
                for (int j = 0; j < nums[i].size(); ++j) {
                    nums[i][j] = (nums[i + 1][j] > nums[i + 1][j + 1] ? nums[i + 1][j] : nums[i + 1][j + 1]) + nums[i][j];
                } 
            }
            
            return nums[0][0];
        }
    };


    展开全文
  • 编程打印三角形数字图案.java

    千次阅读 2015-07-23 15:10:15
    public class C3_16 { public static void main(String[] args) { for(int i=1;i;i++) { for(int j=1;j;j++) System.out.print(" "); f
    public class C3_16
    { 
        public static void main(String[] args)
        {
            for(int i=1;i<=10;i++)
            {
                for(int j=1;j<=11-i;j++)
                    System.out.print(" ");
                for(int j=1;j<=i;j++)
                    {
                        if(i>=10) System.out.print(+i+" ");
                        else System.out.print(+i+"  ");
                    }
                    System.out.println(" ");
            }
        }
    }

    运行结果:

    这里写图片描述

    展开全文
  • 三角形数字路径最大值问题

    千次阅读 2017-04-30 21:00:02
    已知三角形数字,求选取路径,使得路径上的数字和最大? #阶梯相加 91 71 52 63 66 04 68 04 62 98 27 23 先比较4与62的大小,然后将大值加63得125放在63的位置,然后将04与62的...

    a=[
    [75],
    [95,64],
    [17,47,82],
    [18,35,87,10],
    [20, 4, 82, 47, 65],
    [19 ,1 ,23, 75 ,3, 34],
    [88, 2, 77, 73, 7, 63, 67],
    [99 ,65 ,4 ,28 ,6 ,16 ,70 ,92],
    [41, 41, 26, 56, 83, 40, 80, 70, 33],
    [41 ,48 ,72 ,33 ,47 ,32 ,37 ,16 ,94 ,29],
    [53, 71, 44 ,65 ,25, 43 ,91, 52, 97, 51, 14],
    [70 ,11 ,33 ,28 ,77 ,73 ,17 ,78 ,39 ,68 ,17 ,57],
    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
    [63 ,66 ,4 ,68 ,89 ,53 ,67 ,30 ,73 ,16 ,69, 87 ,40 ,31],
    [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53 ,60, 4, 23] ]
    已知三角形数字,求选取路径,使得路径上的数字和最大?

    #阶梯相加
    91    71    52       
    63   66    04   68    
    04   62   98   27   23

    先比较4与62的大小,然后将大值加63得125放在63的位置,然后将04与62的位置换成0。
    按此方法,进行最终会在最顶层得到一个数,为最大值。虽然不知道那个路径但是我们知道最大值。
    根据此写代码:

    def triangle(a):
        L1=len(a)#L1=4
        for i in range(L1-1,-1,-1):
            for j in range(i):
                a[i-1][j]+=max(a[i][j],a[i][j+1])
        return a[0][0]
    print(triangle(a)) 

    此方法很巧妙,给我们的思路是,我们不需要知道那个路径,但是我们可以将繁变简,最终求得最大值。

    展开全文
  • 数字三角形

    万次阅读 2021-02-28 20:27:19
    打印数字三角形,从1开始输出,第i行输出i个数,每个数字按4个位置输出 注:c语言中 %4d可以输出一个数,占据四个位置,右对齐。 输入描述: 输入一行,包含一个整数n 1 <= n <= 1000 输出描述: 输出n行,第i行...

    打印数字三角形,从1开始输出,第i行输出i个数,每个数字按4个位置输出

    注:c语言中 %4d可以输出一个数,占据四个位置,右对齐。

    输入描述:
    输入一行,包含一个整数n

    1 <= n <= 1000

    输出描述:
    输出n行,第i行,有i个数, 每个数占据四个位置。
    示例1
    输入

    4
    

    输出

       1
       2   3
       4   5   6
       7   8   9  10
    
    #include <cstdio>
    int main()
    {
    	int n,k=1;
    	scanf("%d", &n);
    	for (int i = 1; i <=n; i++)
    	{
    		for (int j = 1; j <= i; j++)
    		{
    			printf("%4d", k);
    			k++;
    		}
    		printf("\n");
    	}
    	return 0;
    }
    
    展开全文
  • python 数字三角形

    千次阅读 2019-04-24 16:06:57
    ''' 题目描述 Description 下图给出了一个数字三角形,请编写一个程序,...(3)三角形数字为0,1,…99 输入描述 Input Description 有很多个测试案例,对于每一个测试案例, 通过键盘逐行输入,第1行是输入整...
  • 数字三角形 c++

    2016-06-28 09:16:12
    数字三角形 c++
  • 数字三角形问题

    2019-11-24 19:13:37
    数字三角形问题 SDUT OJ 数字三角形问题 数字三角形问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底...
  • 动态规划——数字三角形

    千次阅读 2018-10-09 15:28:03
    作者:zengwh513 题目描述 Description 下图给出了一个数字三角形,请编写一个程序,计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。 (1)每一步可沿左斜线向下或右斜线...(3)三角形数字为0...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,688
精华内容 20,275
关键字:

三角形数字