数字三角形是一个非常有趣的数学问题，它可以用来训练程序员的逻辑思维和编程能力。本文将介绍使用 C++ 实现数字三角形的代码。

数字三角形问题是这样的：给定一个数字三角形，每个位置有一个数字，从顶部出发，每次可以走到下一行的相邻位置，求出从顶部到底部的路径中数字和最大的路径，并输出该路径上的数字。

下面是一个数字三角形的示例：

  7
 3 8
8 1 0
2 7 4 4

使用 C++ 实现数字三角形的解法主要有两种，分别是递归和动态规划。这里介绍使用动态规划实现数字三角形的代码。

先定义一个二维数组 `triangle`，其中第 `i` 行第 `j` 列的元素表示数字三角形中第 `i` 行第 `j` 列的数字。再定义一个二维数组 `dp`，其中第 `i` 行第 `j` 列的元素表示从数字三角形的顶部到第 `i` 行第 `j` 列的数字的最大路径和。接下来，使用以下代码实现动态规划的递推过程：

for (int i = 0; i < n; i++) {
  for (int j = 0; j <= i; j++) {
    if (i == 0) {
      dp[i][j] = triangle[i][j];
    } else if (j == 0) {
      dp[i][j] = dp[i-1][j] + triangle[i][j];
    } else if (j == i) {
      dp[i][j] = dp[i-1][j-1] + triangle[i][j];
    } else {
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
    }
  }
}

最后，我们需要找到从顶部到底部的路径中数字和最大的路径，并输出该路径上的数字。使用以下代码实现：

int maxSum = -1;
for (int i = 0; i < n; i++) {
  if (dp[n-1][i] > maxSum) {
    maxSum = dp[n-1][i];
    maxIndex = i;
  }
}
cout << "The maximum sum of the path is " << maxSum << endl;
vector<int> path;
path.push_back(triangle[n-1][maxIndex]);
int i = n-2, j = maxIndex;
while (i >= 0) {
  if (j == 0) {
    path.push_back(triangle[i][j]);
    j++;
  } else if (j == i+1) {
    path.push_back(triangle[i][j-1]);
    j--;
  } else {
    if (dp[i][j-1] > dp[i][j]) {
      path.push_back(triangle[i][j-1]);
      j--;
    } else {
      path.push_back(triangle[i][j]);
      j++;
    }
  }
  i--;
}
reverse(path.begin(), path.end());
cout << "The path is ";
for (int k = 0; k < path.size(); k++) {
  cout << path[k] << " ";
}

完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100;
int triangle[MAXN][MAXN];
int dp[MAXN][MAXN];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      cin >> triangle[i][j];
    }
  }
  // dynamic programming
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      if (i == 0) {
        dp[i][j] = triangle[i][j];
      } else if (j == 0) {
        dp[i][j] = dp[i-1][j] + triangle[i][j];
      } else if (j == i) {
        dp[i][j] = dp[i-1][j-1] + triangle[i][j];
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
      }
    }
  }
  // find max sum path and output the path
  int maxSum = -1;
  int maxIndex = -1;
  for (int i = 0; i < n; i++) {
    if (dp[n-1][i] > maxSum) {
      maxSum = dp[n-1][i];
      maxIndex = i;
    }
  }
  cout << "The maximum sum of the path is " << maxSum << endl;
  vector<int> path;
  path.push_back(triangle[n-1][maxIndex]);
  int i = n-2, j = maxIndex;
  while (i >= 0) {
    if (j == 0) {
      path.push_back(triangle[i][j]);
      j++;
    } else if (j == i+1) {
      path.push_back(triangle[i][j-1]);
      j--;
    } else {
      if (dp[i][j-1] > dp[i][j]) {
        path.push_back(triangle[i][j-1]);
        j--;
      } else {
        path.push_back(triangle[i][j]);
        j++;
      }
    }
    i--;
  }
  reverse(path.begin(), path.end());
  cout << "The path is ";
  for (int k = 0; k < path.size(); k++) {
    cout << path[k] << " ";
  }
  cout << endl;
  return 0;
}

以上就是使用 C++ 实现数字三角形代码的具体步骤，希望能对大家的学习和开发有所帮助。

相似文章
• C++递归实现数字三角形打印
  C++是一种非常流行的编程语言，它可以用于各种不同类型的编程任务。其中，递归是C++中非常重要的一种编程方法，它可以帮助程序员更加高效地编写代码。
  
  
• C++数字三角形
  数字三角形是一个经典的算法题目，涉及到了动态规划的思想。在本文中，我们将介绍如何使用C++语言解决数字三角形问题。
  
  
• C++编写数字三角形式输出：1 2 2 3 3 3
  在C++编程中，数字三角形式输出是一个经常练习的题目。具体来说，就是给定一串数字序列，按照一定规则输出数字的三角形。例如，给定序列为1,
  
  
• C++实现数字三角形打印
  C++是一种高级编程语言，广泛用于各种领域的开发中。其中，数字三角形打印是一种常见的编程问题，通过使用循环和控制语句等技术实现。下面就来介绍一下如何使用C++实现数字三角形的打印。
  
  
• C++数字三角形代码实现
  数字三角形是一种经典的算法题目，也是C++编程中常见的题目之一。在数字三角形问题中，我们需要在一个由数字组成的三角形中找到从顶部到底部数字和最大的一条路径。下面我们将介绍如何在C++中实现数字三角形问题的解决方法。
  
  
• C++ 数字三角形代码实现
  数字三角形是一个非常有趣的数学问题，它可以用来训练程序员的逻辑思维和编程能力。本文将介绍使用
  
  
• C++实现数字三角形的输入方法
  数字三角形是一个常见的数学问题，对于程序员来说也是一个常见的编程问题。使用C++语言来实现数字三角形的输入方法是一项非常实用的技能。接下来，我们将探讨一下C++实现数字三角形的输入方法的过程和具体步骤。
  
  
• C++编程实现数字三角形
  数字三角形是一种常见的数学问题，也是编程中常见的算法练习题。在这篇文章中，我们将介绍如何使用C++编写一个解决数字三角形问题的程序。
  
  
• C++ 实现数字三角形输出
  C++语言是一种高级编程语言，它可以用于编写各种类型的程序，包括数字三角形的输出。数字三角形是指由数字组成的三角形，数字之间的排列规则可以根据需求进行调整。下面将介绍如何使用C++实现数字三角形的输出。
  
  
• C语言122333三角形
  C语言122333三角形
  
  
• Java数字三角形代码实现教程
  Java数字三角形代码实现教程
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政