大数阶乘的函数

pgy

看来还没有一个现成的网，比如，C/C++库大全。
如果谁遇到某类编程问题，在这个网上一找，就找到了，那不是很方便！而且，也是前人经验的一个累积！

micrchaoo

1. #ifndef BIGINT_H_
   
2. #define BIGINT_H_
   
3. 
   
4. #include <iostream>
   
5. using namespace std;
   
6. 
   
7. class Error
   
8. {
   
9. public:
   
10.     Error(char *rea):_rea(rea){}
    
11.     char *what(){return _rea;}
    
12. private:
    
13.     char *_rea;
    
14. };
    
15. 
    
16. const int Max_Bit_Len= 1024;
    
17. 
    
18. class bigint
    
19. {
    
20. public:
    
21.     bigint();
    
22.     bigint(int num);
    
23.     bigint(const char *num);
    
24.     bigint(const bigint& obj);       //复制构造函数
    
25.     inline bigint operator-()const;  //取相反值
    
26.     bigint operator()()const;        //取绝对值仿函数
    
27.     int get_len()const{return len;}; //大数位数
    
28. 
    
29.     bigint operator+(const bigint& obj)const;
    
30.     bigint operator-(const bigint& obj)const;
    
31.     bigint& operator+=(const bigint& obj);
    
32.     bigint operator*(const bigint& obj)const;
    
33.     bigint operator/(const bigint& obj)const;
    
34.     bigint operator%(const bigint& obj)const;
    
35.     bool operator>(const bigint& obj)const;
    
36.     bool operator<(const bigint& obj)const;
    
37.     bool operator>=(const bigint& obj)const;
    
38.     bool operator==(const bigint& obj)const;
    
39. 
    
40.     friend std::istream& operator>>(std::istream& in,bigint& obj);
    
41.     friend std::ostream& operator<<(std::ostream& out,bigint& obj);
    
42. 
    
43. private:
    
44.     int len;
    
45.     int sign;
    
46.     int BitArray[Max_Bit_Len];
    
47. 
    
48.     void set_len();         //位数处理
    
49.     void shift(int bit);    //移位 >=0 右移 否则 左移 用于除法
    
50. };
    
51. 
    
52. #endif
    

复制代码

1. #include <cstring>
   
2. #include <cctype>
   
3. #include <string>
   
4. #include "bigint.h"
   
5. 
   
6. bigint::bigint()
   
7. {
   
8.     memset(BitArray,0x0,sizeof(BitArray));
   
9.     len=1;
   
10.     sign=1;
    
11. }
    
12. bigint::bigint(int num)
    
13. {
    
14.     if(num < 0)
    
15.     {
    
16.         sign=-1;
    
17.         num=-num;
    
18.     }
    
19.     else
    
20.         sign=1;
    
21. 
    
22.     int *ptr=BitArray;
    
23.     for(; num!=0; ptr++)
    
24.     {
    
25.         *ptr=num%10;
    
26.         num /= 10;
    
27.     }
    
28.     len=(int)(ptr-BitArray);
    
29.     len=len?len:1;
    
30.     memset(ptr,0x0,sizeof(int)*(Max_Bit_Len-len));
    
31. }
    
32. bigint::bigint(const bigint& obj)
    
33. {
    
34.     if(this!=&obj)
    
35.     {
    
36.         len=obj.len;
    
37.         sign=obj.sign;
    
38.         memcpy(BitArray,obj.BitArray,sizeof(BitArray));
    
39.     }
    
40. }
    
41. bigint::bigint(const char *num)
    
42. {
    
43.     len=strlen(num);
    
44.     sign=1;
    
45.     if(*num=='-'||*num=='+')
    
46.     {
    
47.         if(*num=='-')
    
48.             sign=-1;
    
49.         num++;
    
50.         len--;
    
51.     }
    
52.     for(int i=0;i<len;i++)
    
53.     {
    
54.         if(isdigit(*num))
    
55.             BitArray[len-i-1]=*num++ -'0';
    
56.         else
    
57.             throw Error("Input Error!");
    
58.     }
    
59.     if(len==0)
    
60.         len=1;
    
61.     memset(BitArray+len,0x0,(Max_Bit_Len-len)*sizeof(int));
    
62. }
    
63. bigint bigint::operator-()const   //-a
    
64. {
    
65.     bigint res(*this);
    
66.     res.sign=-sign;
    
67.     return res;
    
68. }
    
69. bigint bigint::operator+(const bigint& obj)const
    
70. {
    
71.     bigint res;
    
72.     if(sign==obj.sign)
    
73.     {
    
74.         res.len=0;
    
75.         int k=(len>obj.len) ? len : obj.len;
    
76.         for(int i=0,x=0; i<k||x; i++)
    
77.         {
    
78.             if(i<len)     x+=BitArray[i];
    
79.             if(i<obj.len) x+=obj.BitArray[i];
    
80.             //x+=BitArray[i]+obj.BitArray[i];
    
81.             res.BitArray[res.len++]=x%10;
    
82.             if(res.len >= Max_Bit_Len) throw Error("位数超过最大值");
    
83.             x /= 10;
    
84.         }
    
85.         res.sign=sign;
    
86.     }
    
87.     else
    
88.         res=(*this)-(-obj);
    
89.     return res;
    
90. }
    
91. bigint bigint::operator()()const  //|a|
    
92. {
    
93.     bigint res(*this);
    
94.     res.sign=1;
    
95.     return res;
    
96. }
    
97. void bigint::set_len()
    
98. {
    
99.     while(len>1 && !BitArray[len-1])
    
100.         len--;
     
101. }
     
102. bigint bigint::operator-(const bigint& obj)const
     
103. {
     
104.     bigint res;
     
105.     if(sign==obj.sign)
     
106.     {
     
107.         const bigint *max,*min;
     
108.         if((*this)()>obj())
     
109.         {
     
110.             max=this;   min=&obj;   res.sign=sign;
     
111.         }
     
112.         else
     
113.         {
     
114.             max=&obj;   min=this;   res.sign=-sign;
     
115.         }
     
116.         res.len=max->len;
     
117.         for(int i=0;i<max->len;i++)
     
118.         {
     
119.             res.BitArray[i]+= max->BitArray[i]-min->BitArray[i];
     
120.             if(res.BitArray[i] < 0)
     
121.             {
     
122.                 res.BitArray[i] += 10;
     
123.                 res.BitArray[i+1]--;
     
124.             }
     
125.         }
     
126.         res.set_len();
     
127.     }
     
128.     else
     
129.         res=(*this)+(-obj);
     
130.     return res;
     
131. }
     
132. bool bigint::operator>(const bigint& obj)const
     
133. {
     
134.     if(sign > obj.sign) return true;
     
135.     if(sign < obj.sign) return false;
     
136. 
     
137.     if(sign==1)
     
138.     {
     
139.         if(len!=obj.len) return len > obj.len;
     
140.         for(int i=len-1;i>=0;i--)
     
141.         {
     
142.             if(BitArray[i]!=obj.BitArray[i])
     
143.                 return BitArray[i] > obj.BitArray[i];
     
144.         }
     
145.     }
     
146.     else
     
147.     {
     
148.         if(len!=obj.len) return len < obj.len;
     
149.         for(int i=len-1;i>=0;i--)
     
150.         {
     
151.             if(BitArray[i]!=obj.BitArray[i])
     
152.                 return BitArray[i] < obj.BitArray[i];
     
153.         }
     
154.     }
     
155.     return false; //==
     
156. }
     
157. bool bigint::operator<(const bigint& obj)const
     
158. {
     
159.     return obj>*this;
     
160. }
     
161. bool bigint::operator>=(const bigint& obj)const
     
162. {
     
163.     return !(obj > *this);
     
164. }
     
165. bool bigint::operator==(const bigint& obj)const
     
166. {
     
167.     return (!(obj>*this))&&(!(*this>obj));
     
168. }
     
169. bigint& bigint::operator+=(const bigint& obj)
     
170. {
     
171.     *this=*this+obj;
     
172.     return *this;
     
173. }
     
174. bigint bigint::operator*(const bigint& obj)const
     
175. {
     
176.     bigint res;
     
177.     res.len=len+obj.len;
     
178.     for(int i=0;i<len;i++)
     
179.     {
     
180.         for(int j=0;j<obj.len;j++)
     
181.         {
     
182.             if(i+j >= Max_Bit_Len) throw Error("位数超过最大值");
     
183.             res.BitArray[i+j] += BitArray[i]*obj.BitArray[j];
     
184.         }
     
185.     }
     
186.     for(int i=0;i<res.len-1;i++)
     
187.     {
     
188.         res.BitArray[i+1] += res.BitArray[i]/10;
     
189.         res.BitArray[i] %= 10;
     
190.     }
     
191.     res.set_len();
     
192.     res.sign=(sign==obj.sign) ? 1 : -1;
     
193.     return res;
     
194. }
     
195. void bigint::shift(int bit)
     
196. {
     
197.     if(bit >=0)  // >=0 右移
     
198.     {
     
199.         for(int i=len+bit-1;i>=0;i--)
     
200.             BitArray[i]=(i>=bit) ? BitArray[i-bit] : 0;
     
201.     }
     
202.     else        // <0  左移
     
203.     {
     
204.         for(int i=0;i<len;i++)
     
205.             BitArray[i]=(i-bit<len) ? BitArray[i-bit] : 0;
     
206.     }
     
207.     len += bit;
     
208. }
     
209. bigint bigint::operator/(const bigint& obj)const
     
210. {
     
211.     if(obj==bigint(0))
     
212.         throw Error("Dirisor can not be zero!");//除数不能为零
     
213.     bigint did=(*this)();//取绝对值
     
214.     bigint dir=obj();
     
215.     if(dir > did) return bigint(0);
     
216.     bigint res;
     
217.     int m=len-obj.len;
     
218.     dir.shift(m);       //右移m位
     
219.     while(m>=0)
     
220.     {
     
221.         if(did >= dir)  //被除数>=除数
     
222.         {
     
223.             did =did- dir;
     
224.             res.BitArray[m]++;
     
225.         }
     
226.         else
     
227.             {
     
228.                 m--;
     
229.                 res.len++;    //???
     
230.                 dir.shift(-1);//左移一位
     
231.             }
     
232.     }
     
233.     res.set_len();
     
234.     res.sign=(sign==obj.sign) ? 1 :-1;
     
235.     return res;
     
236. }
     
237. bigint bigint::operator%(const bigint& obj)const
     
238. {
     
239.     bigint res;
     
240.     res=(*this)-((*this)/obj)*obj;
     
241.     return res;
     
242. }
     
243. std::istream& operator>>(std::istream& in,bigint& obj)
     
244. {
     
245.     string tmp;
     
246.     in>>tmp;
     
247.     obj=tmp.c_str();
     
248.     return in;
     
249. }
     
250. std::ostream& operator<<(std::ostream& out,bigint& obj)
     
251. {
     
252.     if(obj.sign==-1)
     
253.         out<<'-';
     
254.     for(int i=obj.len-1;i>=0;i--)
     
255.         out<<(obj.BitArray[i]);
     
256.     return out;
     
257. }
     
258. 
     

复制代码

1. #include <iostream>
   
2. #include "bigint.h"
   
3. using namespace std;
   
4. bigint test(unsigned);
   
5. int main(void)
   
6. {
   
7.     bigint c;
   
8.     /*bigint a("-11"),b("-11");
   
9.     c=a/b;
   
10.     cout<<c<<endl;
    
11.     cout<<c.get_len()<<endl;
    
12.     */
    
13.     c=test(458);
    
14.     cout<<c<<endl;
    
15.     cout<<c.get_len()<<endl;
    
16.     return 0;
    
17. }
    
18. bigint test(unsigned n)
    
19. {
    
20.     bigint res(1);
    
21.     for(unsigned i=2;i<=n;i++)
    
22.         res= res*i;
    
23.     return res;
    
24. }

复制代码

micrchaoo

以上为C++大数类，可以此进行阶乘

dewade

大数运算，acm入门的吧。