【題目鏈接】

ybt 1173：階乘和
注：一本通上這題，應(yīng)該把$n\le 50$當(dāng)做$n\le 100$來看
OpenJudge NOI 1.6 15:階乘和
洛谷 P1009 [NOIP1998 普及組] 階乘之和

【題目考點(diǎn)】

1. 高精度

考察：高精乘低精 高精加高精
高精度計(jì)算講解

【解題思路】

相應(yīng)的低精度數(shù)字求階乘和的解法如下：
ybt 1091：求階乘的和
采用其中復(fù)雜度為$O(n)$的迭代法，代碼如下：

#include <bits/stdc++.h> using namespace std; int main() {int n;cin >> n;int s = 0, a = 1;//a：某一階乘項(xiàng)的值 for(int i = 1; i <= n; ++i){a *= i;//本句運(yùn)行結(jié)束后，a的值為i! s += a;//加和變量中增加i! }cout << s;return 0; }

在本問題中，s與a應(yīng)該是高精度數(shù)字，i，n是低精度數(shù)字。a*=i為高精乘低精，s+=a為高精加高精。
該題難點(diǎn)在于分析結(jié)果位數(shù)，為數(shù)字?jǐn)?shù)組設(shè)一個合理的數(shù)組長度。（比如不知道結(jié)果位數(shù)，就設(shè)了數(shù)組長為10000，那你憑什么認(rèn)為結(jié)果一定小于10000位？總得有點(diǎn)根據(jù)吧。）
求數(shù)字位數(shù)公式：假設(shè)數(shù)字x有n位，那么$n=?lgx?+1$
假設(shè)n=50，求$1!+2!+...+50!$的位數(shù)，我們可以不斷將結(jié)果放大
$1!+2!+...+50!\le 50?50!\le 50?50^{50}=50^{51}$
求$50^{51}$的位數(shù)：$?lg50^{51}?+1=?51?lg50?+1\le ?51?lg100?+1=103$
將數(shù)字?jǐn)?shù)組長度設(shè)為105就可以滿足要求。
【注】一本通OJ上本題測試數(shù)據(jù)有誤，需要將數(shù)字?jǐn)?shù)組長度設(shè)為155才能過（我只試到155能過），否則有幾個測試點(diǎn)會報“運(yùn)行錯誤”。所以可以當(dāng)這道題中給定的$n\le 50$當(dāng)做$n\le 100$來看，這樣推算出的數(shù)據(jù)位數(shù)就沒有問題了。

【題解代碼】

解法1：使用函數(shù)與數(shù)組

本解法中，使用的高精度運(yùn)算為 a*=b和a+=b。

#include<bits/stdc++.h> using namespace std; #define N 155//一本通OJ上必須設(shè)為155才能過 洛谷、OpenJudge上設(shè)到105就能過 void Multiply(int a[], int b)//高精乘低精 a *= b {int c = 0, i;for(i = 1; i <= a[0]; ++i){a[i] = a[i]*b + c;c = a[i] / 10;a[i] %= 10; }while(c > 0){a[i] = c % 10;c /= 10;i++;}while(a[i] == 0 && i > 1)i--;a[0] = i; } void Add(int a[], int b[])//高精加高精 a += b {int c = 0, i;for(i = 1; i <= a[0] || i <= b[0]; ++i){a[i] += b[i] + c;c = a[i] / 10;a[i] %= 10;}if(c > 0)a[i] = c;while(a[i] == 0 && i > 1)i--;a[0] = i; } void showNum(int a[]) {for(int i = a[0]; i >= 1; --i)cout << a[i]; } int main() {int a[N] = {1, 1}, s[N] = {1, 0}, n;//數(shù)字a初值為1 加和s初值為0 cin >> n;for(int i = 1; i <= n; ++i){Multiply(a, i);Add(s, a);}showNum(s);return 0; }

解法2：類中重載運(yùn)算符

#include<bits/stdc++.h> using namespace std; #define N 155 struct HPN {int a[N];HPN(){memset(a, 0, sizeof(a));}HPN(char s[]){memset(a, 0, sizeof(a));a[0] = strlen(s);for(int i = 1; i <= a[0]; ++i)a[i] = s[a[0] - i] - '0';}int& operator [] (int i){return a[i];}void setLen(int i)//確定數(shù)字位數(shù){while(a[i] == 0 && i > 1)i--;a[0] = i;}void operator *= (int b)//a *= b{int c = 0, i;for(i = 1; i <= a[0]; ++i){a[i] = a[i]*b + c;c = a[i] / 10;a[i] %= 10; }while(c > 0){a[i] = c % 10;c /= 10;i++;}setLen(i); }void operator += (HPN b)//高精加高精{int c = 0, i;for(i = 1; i <= a[0] || i <= b[0]; ++i){a[i] += b[i] + c;c = a[i] / 10;a[i] %= 10;}a[i] = c;setLen(i);}void show(){for(int i = a[0]; i >= 1; --i)cout << a[i];} }; int main() {int n;cin >> n;HPN s("0"), a("1");//s = 0, a = 1 for(int i = 1; i <= n; ++i){a *= i;//高精乘低精s += a;//高精加高精}s.show();return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1173：阶乘和 | OpenJudge NOI 1.6 15 | 洛谷 P1009 [NOIP1998 普及组] 阶乘之和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。