資料結構
網路
關係資料庫管理系統 (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 次檢視
