C语言蓝桥杯数字三角形
时间: 2023-09-21 16:12:51 浏览: 66
题目描述
下面的数字金字塔由数字0~9构成。
0
1 2 1
2 3 4 3 2
3 4 5 6 5 4 3
4 5 6 7 8 7 6 5 4
其中第k行包含k个数字,数字之间用空格分隔。
如图所示的数字金字塔有5行,它的高度为5。
请编写一个程序,计算出从金字塔顶至底部的所有路径中,数字之和最大的那条路径所经过的数字之和。
【输入格式】
第一行是一个整数n,表示数字金字塔的高度。
接下来n行,按照数字金字塔的格式,输入数字金字塔中的数字0~9。
【输出格式】
输出一个整数,表示从金字塔顶至底部的所有路径中,数字之和最大的那条路径所经过的数字之和。
【输入样例】
5
0
1 2
2 3 4
3 4 5 6
4 5 6 7 8
【输出样例】
27
【样例说明】
从顶至底部有以下几条路径:
0->1->2->3->4,路径上数字之和为0+1+2+3+4=10;
0->1->3->5->7,路径上数字之和为0+1+3+5+7=16;
0->1->3->5->8,路径上数字之和为0+1+3+5+8=17;
0->1->3->6->8,路径上数字之和为0+1+3+6+8=18;
0->2->4->5->7,路径上数字之和为0+2+4+5+7=18;
0->2->4->5->8,路径上数字之和为0+2+4+5+8=19;
0->2->4->6->8,路径上数字之和为0+2+4+6+8=20;
其中,数字之和最大的是最后一条,其和为27。
相关问题
蓝桥杯杨辉三角形c语言
蓝桥杯是中国最大的IT竞赛之一,每年都会吸引大量的学生参与。杨辉三角形是蓝桥杯中常见的题目之一,它是一个由数字构成的三角形,满足以下规律:
1. 第一行只有一个数字1。
2. 第二行有两个数字1。
3. 从第三行开始,每个数字都是它上方两个数字之和。
下面是一个用C语言实现杨辉三角形的示例代码:
```c
#include <stdio.h>
int main() {
int rows, coef = 1;
printf("请输入要打印的行数:");
scanf("%d", &rows);
for (int i = 0; i < rows; i++) {
for (int space = 1; space <= rows - i; space++) {
printf(" ");
}
for (int j = 0; j <= i; j++) {
if (j == 0 || i == 0) {
coef = 1;
} else {
coef = coef * (i - j + 1) / j;
}
printf("%4d", coef);
}
printf("\n");
}
return 0;
}
```
这段代码首先会让用户输入要打印的行数,然后使用两个嵌套的循环来打印杨辉三角形。外层循环控制行数,内层循环用来打印每一行的数字。在内层循环中,使用了组合公式来计算每个数字的值。
c语言蓝桥杯算法讲解
以下是关于C语言蓝桥杯算法的讲解:
1. 蓝桥杯算法题目类型
蓝桥杯算法题目主要分为以下几类:数学题、递推题、搜索题、贪心题、动态规划题、图论题等。
2. 数学题
数学题是蓝桥杯中出现频率最高的一类题目,主要考察对数学知识的掌握和应用能力。常见的数学题目有:最大公约数、最小公倍数、质数判断、进制转换、排列组合等。
3. 递推题
递推题是指通过已知的一些条件,推导出后续的结果。递推题目通常需要使用循环结构来实现。常见的递推题目有:斐波那契数列、汉诺塔、青蛙跳等。
4. 搜索题
搜索题是指在一个状态空间中寻找目标状态的过程。搜索题目通常需要使用递归或循环结构来实现。常见的搜索题目有:深度优先搜索、广度优先搜索、回溯法等。
5. 贪心题
贪心算法是指在每一步选择中都采取当前状态下最优的选择,从而希望导致结果是全局最优的算法。贪心题目通常需要使用排序等方法来实现。常见的贪心题目有:背包问题、活动安排等。
. 动态规划题
动态规划是一种将复杂问题分解成小问题来解决的优化技术。动态规划题目通常需要使用递推或循环结构来实现。常见的动态规划题目有:最长上升子序列、最大子段和等。
7. 图论题
图论是研究图的性质和图之间关系的数学分支。图论题目通常需要使用图的遍历、最短路径等算法来实现。常见的图论题目有:最短路径、最小生成树等。