C++ 数字三角形代码实现 |21xrx.com

C++ 数字三角形代码实现

2023-06-26 12:12:44 深夜i 14 0

C++ 数字三角形代码实现

数字三角形是一个非常有趣的数学问题，它可以用来训练程序员的逻辑思维和编程能力。本文将介绍使用 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++ 实现数字三角形代码的具体步骤，希望能对大家的学习和开发有所帮助。

上一篇: idea打包java可执行jar包

下一篇: C++中的栈定义

评论区

相似文章