WZ℡T 2018-12-18 21:55 采纳率: 50%
浏览 368
已采纳

大佬们帮我看看 回溯递归我运用还不太会

问题描述
  (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
  径,使该路径所经过的数字的总和最大。
  ●每一步可沿左斜线向下或右斜线向下走;
  ●1<三角形行数≤100;
  ●三角形中的数字为整数0,1,…99;

  .
  (图3.1-1)
输入格式
  文件中首先读到的是三角形的行数。

  接下来描述整个三角形
输出格式
  最大总和(整数)
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30

  • 写回答

1条回答 默认 最新

  • threenewbee 2018-12-18 16:12
    关注

    递归,就是分解问题
    对于一个最简单的三角形,它只有1层,那么只有2个走法,往左和往右。比如说
    2
    45
    那么就是2->4和2->5
    对于再大一点的三角形
    8
    27
    452
    那么我们有两条路径分别是8>2和8->7,之后的问题就转换成了之前已经解决的问题了。
    因此我们可以推出如下递归的解法
    int foo(三角形 t)
    {
    如果三角形是2层,那么返回它顶部到左边和右边中最大的那条
    如果三角形是2层以上的,那么首先计算
    a = foo(第二行左边构成的三角形);
    b = foo(第二行右边构成的三角形);
    然后返回它顶部到a和b中最大的那条。
    }

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题