77 条题解
-
0
for 循环求和
我们先看题目。
小明写出了一个数列,第 i 项 ai 的值为 i2。数列从第一项(i = 1)开始如下: 1, 4, 9, 16, 25, ... 编程求出这个数列前 n 项的和。
- 上面要求找出规律,并求前n项的和。
- 我们很容易就能找到它的规律:第一项是1 *1 第二项是 2 *2,第三项是3 *3,因此得到规律:第i项是i *i。
O(n)解法
这是大部分人所用的解法,
- 我们知道for循环有两个关键,
- 循环多少次?
- 每次循环干什么?
- 这两个问题我们都能解决,因为是遍历前n项所以,循环n次。
- 根据规律,每次循环,sum需要加上i *i。
之后用代码实现这个for循环求和即可。
O(n)代码
#include <bits/stdc++.h> using namespace std; int main() { int n,sum=0;//sum初始化为0 cin>>n; for (int i=1;i<=n;i++) {//重复执行n次 sum+=i*i;//sum+第i个数的值。 } cout<<sum;//输出总和。 return 0; }
O(1)代码
虽然O(n)代码解决这题已经绰绰有余,但是,我们永远要有一颗追求高效代码的心。
- 你是到吗?其实,这种求和是有一种求和公式的,如:求1—n项的所有数和就可以这样算
- n*(n+1)*(2 *n+1)/6
- 这是按证明写的算式。我们今天的首要任务就是,理解这个算式。
相信你看了这个视频后已经明白了原理。之后写进代码即可。
O(1)AC代码
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; cout<<n*(n+1)*(2*n+1)/6; return 0; }
信息
- ID
- 550
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 8307
- 已通过
- 4404
- 上传者