输入整数n,输出求和6+66+666+6666......前n个数的和.
时间: 2024-01-12 11:03:02 浏览: 96
算法1:暴力枚举
直接枚举前n个数,依次计算出每个数,然后累加求和。
时间复杂度:$O(n)$
C++ 代码
```cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long sum = 0;
int num = 6;
for (int i = 1; i <= n; i++) {
sum += num;
num = num * 10 + 6;
}
cout << sum << endl;
return 0;
}
```
算法2:数学公式
观察数列的规律,可以发现每一项都是由前一项乘以10再加上6得到的,即:
$$a_n = a_{n-1} \times 10 + 6$$
进一步地,我们可以将数列展开,得到:
$$a_n = 6 \times (\underbrace{1 + 10 + 10^2 + \cdots + 10^{n-2}}_{n-1}) + 6 \times 10^{n-1}$$
其中,括号中的部分是一个等比数列求和,可以用等比数列求和公式求出:
$$\sum_{i=1}^{n-1} 10^{i-1} = \frac{10^{n-1}-1}{9}$$
将其代入到原式中,得到:
$$a_n = \frac{6}{9} \times (10^{n}-1) + 6 \times 10^{n-1}$$
最终的求和公式为:
$$S_n = \sum_{i=1}^{n} a_i = \sum_{i=1}^{n} (\frac{6}{9} \times (10^{i}-1) + 6 \times 10^{i-1}) = \frac{2}{3} \times (10^{n+1}-n-11)$$
时间复杂度:$O(1)$
C++ 代码
```cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long sum = 2 * pow(10, n + 1) / 3 - n - 11;
cout << sum << endl;
return 0;
}
```