【題目鏈接】

ybt 1172：求10000以?xún)?nèi)n的階乘
OpenJudge NOI 1.6 14:求10000以?xún)?nèi)n的階乘

【題目考點(diǎn)】

1. 高精度

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

【解題思路】

先求結(jié)果最大的位數(shù)，也就是$10000!$的位數(shù)。
已知某正整數(shù)x的的位數(shù)為n，那么有：$n=?lgx?+1$（$lgx$:以10為底x的對(duì)數(shù)）
位數(shù)為$?lg10000!?+1\le ?lg10000^{10000}?+1=?10000?lg10000?+1=?10000?4?+1=40001$
數(shù)字?jǐn)?shù)組長(zhǎng)度取40005即可。
由于求10000的階乘，每次乘的數(shù)字都是小于等于10000的數(shù)字，為低精度數(shù)字。階乘的結(jié)果為高精度數(shù)字。所以應(yīng)該使用高精乘低精。如果使用高精乘高精，算法復(fù)雜度會(huì)增大，可能會(huì)超時(shí)。

【題解代碼】

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

#include <bits/stdc++.h> using namespace std; #define N 40005 void setLen(int a[], int i) {while(a[i] == 0 && i > 1)//去除多余的0i--;a[0] = i; } 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++;}setLen(a, i); } void toNum(char s[], int a[]) {a[0] = strlen(s);for(int i = 1; i <= a[0]; ++i)a[i] = s[a[0] - i] - '0'; } void showNum(int a[]) {for(int i = a[0];i >= 1;--i)cout << a[i]; } int main() {int a[N] = {1, 1}, n;//高精度數(shù)字a初值為1 cin >> n;for(int i = 1; i <= n; ++i)Multiply(a, i);showNum(a);return 0; }

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

#include <bits/stdc++.h> using namespace std; #define N 40005 struct HPN {int a[N];//數(shù)字?jǐn)?shù)組HPN(){memset(a, 0, sizeof(a));}HPN(char s[]){memset(a, 0, sizeof(a));int len = strlen(s);for(int i = 0; i < len; ++i)a[len - i] = s[i] - '0';a[0] = len;}void setLen(int i){while(a[i] == 0 && i > 1)//去除多余的0i--;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 show(){for(int i = a[0]; i >= 1; --i)cout << a[i];} }; int main() {HPN a("1");//高精數(shù)字a初值為1 int n;cin >> n;for(int i = 1; i <= n; ++i)a *= i;//高精乘低精a.show();return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1172：求10000以内n的阶乘 | OpenJudge NOI 1.6 14:求10000以内n的阶乘的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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