SPOJ - 24. Small factorials 大数相乘的运用
发布时间:2020-12-14 03:37:22 所属栏目:大数据 来源:网络整理
导读:有是一个大数相乘的题目的运用,用C++嘛,这里纯手工打造大数相乘。创建一个class,然后使用hash表,查表就是常数的效率了。 You are asked to calculate factorials of some small positive integers. Input An integer t,1=t=100,denoting the number of t
有是一个大数相乘的题目的运用,用C++嘛,这里纯手工打造大数相乘。创建一个class,然后使用hash表,查表就是常数的效率了。 You are asked to calculate factorials of some small positive integers. InputAn integer t,1<=t<=100,denoting the number of testcases,followed by t lines,each containing a single integer n,1<=n<=100. OutputFor each integer n given at input,display a line with the value of n! Example
Sample input:
4 1 2 5 3 Sample output: 1 2 120 6 手工打造,我觉得尽管题目有限制数据,自己还是习惯地检验一下好,养成优良习惯。 100的阶乘是个非常非常大的数,所以这里使用string实现大数相乘了。 #include <iostream> #include <vector> #include <string> #include <assert.h> #include <algorithm> using namespace std; class BigNum { string table[101]; string numToStr(int n) { if (0 == n) return "0"; string s; while (n) { s.push_back(n % 10 + '0'); n /= 10; } reverse(s.begin(),s.end()); return s; } public: BigNum() { table[0] = "0",table[1] = "1"; for (int i = 2; i < 101; i++) { table[i] = bigMultiply(numToStr(i),table[i-1]); } cout<<endl; } string bigMultiply(string a,string b) { if (a.empty() || b.empty() || '0' == a[0] || '0' == b[0]) return "0"; string c(a.size() + b.size(),'0'); for (int i = a.size() - 1; i >= 0 ; i--) { int carry = 0; int an = a[i]-'0'; for (int j = b.size() - 1; j >= 0 ; j--) { int bn = b[j] - '0'; int sum = an * bn + carry + c[i+j+1] - '0'; carry = sum / 10; c[i+j+1] = sum % 10 + '0'; } if (carry) c[i] += carry; } if (c.size() && '0' == c[0]) c.erase(c.begin()); return c; } void SmallFactorialRun() { int T = 0,N = 0; cin>>T; while (T--) { cin>>N; assert(0<N && N<101); cout<<table[N]<<endl; } } }; int main() { BigNum bgn; bgn.SmallFactorialRun(); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |