前缀和 - 算法笔记

炒鸡简单的算法

Posted by ChungZH on 2018-10-13

前缀和是一种较为基础的算法。下面我们举例说明前缀和是什么东西。

其实可以把它理解为数学上的数列的前n项和(对于一个一维数组的前缀和)。

话不多说,上图:

gongshi

下面开始C++代码实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int main()
{
int a[7];
int b[8];
b[0] = 0;

for (int i = 1; i < 8; i++)
{
a[i] = i;
}
// 现在数组 a是这样的: 1 2 3 4 5 6 7
for (int i = 1; i < 8; i++)
{
b[i] = a[i] + b[i - 1]; // 使用公式
}

for (int i = 1; i < 8; i++)
{
cout << b[i] << " ";
}
cout << endl;
return 0;
}

结果:

1
1 3 6 10 15 21 28

前缀和这个算法很简单,最重要的就是一个公式。


如果你想学习数据结构和算法,却苦于没有简单易学的教程,那么我给你推荐下面这个课程:

AI前奏必备-数据结构与算法课 - 老九学堂

(此课程中还有Cocos2dx和前端入门课赠送。)


作者:ChungZH

审稿:未央