用蛮力算法实现数塔问题C语言

蛮力算法（也称为暴力算法）是一种简单直接的解决问题的方法，它通过穷举所有可能的解来找到最优解。数塔问题是一个经典的动态规划问题，可以使用蛮力算法来解决。

数塔问题描述如下：给定一个由整数组成的数塔，从塔的顶部出发，在每一层只能选择相邻的两个数字中的一个数字，一直走到底层，要求找出一条路径，使得路径上经过的数字之和最大。

以下是用蛮力算法实现数塔问题的C语言代码：

#include <stdio.h>

#define MAX_SIZE 100

int maxSum(int tower[MAX_SIZE][MAX_SIZE], int n) {
    int maxSum = 0;
    int path[MAX_SIZE][MAX_SIZE] = {0}; // 用于记录路径上的数字

    // 从底层往上计算每个位置的最大和
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            // 选择相邻两个数字中较大的一个，并加上当前位置的数字
            int maxChild = (tower[i + 1][j] > tower[i + 1][j + 1]) ? tower[i + 1][j] : tower[i + 1][j + 1];
            tower[i][j] += maxChild;
            path[i][j] = maxChild; // 记录路径上的数字
        }
    }

    // 打印路径
    printf("路径：\n");
    int row = 0, col = 0;
    printf("%d ", tower[row][col]);
    for (int i = 0; i < n - 1; i++) {
        if (path[row][col] == tower[row + 1][col]) {
            row++;
        } else {
            row++;
            col++;
        }
        printf("%d ", tower[row][col]);
    }
    printf("\n");

    maxSum = tower[0][0];
    return maxSum;
}

int main() {
    int n;
    int tower[MAX_SIZE][MAX_SIZE];

    printf("请输入数塔的层数：");
    scanf("%d", &n);

    printf("请输入数塔的数字：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &tower[i][j]);
        }
    }

    int result = maxSum(tower, n);
    printf("最大和为：%d\n", result);

    return 0;
}

以上代码中，`maxSum`函数使用动态规划的思想，从底层往上计算每个位置的最大和，并记录路径上的数字。最后，通过打印路径和返回最大和来得到结果。