数字三角形是一个非常有趣的数学问题，它可以用来训练程序员的逻辑思维和编程能力。本文将介绍使用 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++ 实现数字三角形输出
  C++语言是一种高级编程语言，它可以用于编写各种类型的程序，包括数字三角形的输出。数字三角形是指由数字组成的三角形，数字之间的排列规则可以根据需求进行调整。下面将介绍如何使用C++实现数字三角形的输出。
  
  
• C语言122333三角形
  C语言122333三角形
  
  
• Java数字三角形代码实现教程
  Java数字三角形代码实现教程
  
  

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