数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中求 1+22+333+4444+... 到 n 项的和
在这个问题中，我们给定一个整数 N。我们的任务是求和数列 1 + 22 + 333 + 4444 + 55555... 到 n 项的和。
让我们来看一个例子来理解这个问题：
Input : N = 4 Output : 4800
说明 −
1 + 22 + 333 + 4444 = 4800
解题方法
解决这个问题的一个简单方法是找到该数列的通项公式，然后求到 n 项的和。使用公式计算和可以将时间复杂度降低到 O(1)。
该数列为：
1 + 22 + 333 + 4444 + 55555...
数列的和可以改写为：
$\mathrm{Sum}\:=\:1^*(\frac{10^1-1}{9})\:+\:2^*(\frac{10^2-1}{9})\:+\:3^*(\frac{10^3-1}{9})\dotsm$
提取公因式 1/9，和变为：
$\mathrm{Sum}\:=\:1/9^*\lbrace(1^*10^1-1)\:+\:(2^*10^2-2)\:+\:(3^*10^3-3)\:+\:\dotsm(n^*10^n-n)\rbrace$
$\mathrm{Sum}\:=\:1/9^{*}\lbrace1^*10^1\:+\:2^*10^2\:+\:3^*10^3\:+\:\dotsm+n^*10^n\:-\:(1+2+3+\dotsm\:n)\rbrace$
$\mathrm{Sum}\:=\:1/9^{*}\lbrace(1^*10^1\:+\:2^*10^2\:+\:3^*10^3\:+\:\dotsm+n^*10^n)\:-\:1/2(n^*(n+1))\rbrace$
项 (1*101 + 2*102 + 3*103 + ... + n*10n) 可以通过对数列的通项公式求导来解决，
1 + x + x2 + x3 + ... n*xn
因此，项 (1*101 + 2*102 + 3*103 + ... + n*10n) 可以改写为：
$\frac{n^*(10^{n+2})-(n+1)*(10^{n+1})+10}{81}$
代回和的公式中：
$\mathrm{Sum}\:=\:1/9^*\lbrace(\frac{n^*(10^{n+2})-(n+1)*(10^{n+1})+10}{81}\:-\:1/2(n^*(n+1))\rbrace$
$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace2^*(n*(10^{n+2})-(n+1)*(10^{n+1})+10)-81^*n^*(n+1)\rbrace$
$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace2^*(n*(10^{n+2})-(n+1)*(10^{n+1})+10)-81^*n^*(n+1)\rbrace$
$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace(2n*10^{n+2}-2(n+1)*10^{n+1}+20)-81n(n+1)\rbrace$
$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace10^{n+1*}(20n-2n-2)-81n^2-81n+20\rbrace$
$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace10^{n+1*}(18n-2)-81n^2-81n+20\rbrace$
示例
程序演示了我们解决方案的工作原理
#include<iostream>
#include<math.h>
using namespace std;
int calcSumNTerms(int n) {
return ( ( (18*n - 2)*(pow(10, n+1)) - 81*n*n - 81*n + 20 )/1458 );
}
int main() {
int n = 5;
cout<<"The sum of series upto n terms is "<<calcSumNTerms(n);
return 0;
}输出
The sum of series upto n terms is 60355
454 次查看
