2012年计算机等级考试二级Ｃ++辅导讲义（10）

会计考友

　大整数阶乘的算法思路 　　这里的大整数指大于500以上的整数，当然更大也可以。由于整数阶乘递增的很快，远大于指数式递增，对于小整数，比如20，30左右，可以直接使用比如递归的方式进行，这很基本。
' R* S" h& @* o　　但是当整数较大时，阶乘的结果很大，远非一个int或者long就能存的下的，比如1000的阶乘结果有上千位。
　　所以大整数阶乘设计的关键点就是存储大整数，当选择了存储大整数，那么整数的乘法运算也不能再依靠*了，所以还要重新设计大整数的惩罚运算。
4 @+ f1 m0 k  ]- F7 S& p  B" m　　上面是我的设计思路。网上找过相关的文章，有高手以4行代码完成了该算法，确实佩服!当然这涉及了算法的优化，不管那么多了，这里要的就是以尽量清晰地思路快速设计该算法，这是使用了STL标准库的容器。
　　下面是我的算法代码，直接贴这里了，注意看相关的注释：
　　#include
+ _1 S5 m+ l9 ~　　#include
　　using namespace std;
/ _: s1 f0 i4 ^" Z　　// 传入整数：int，和整数-1的阶乘结果，进行相乘的结果
% M+ u+ M+ V0 \* w8 b　　// 结构依然存储到容器中
' A( I: j6 X" l) ^  k( [# I　　void Calc(int num,vector &calcresult)
　　{
7 z/ |- s7 E( J( S3 R) P* @4 Q, a: t　　vector tempnum;
　　vector rest;
+ D7 Y' W" F4 m( s' j　　// 将传入的int拆分之后保存到容器中
　　do
+ o; h* K5 a4 V3 u　　{
　　tempnum.push_back(num % 10);
　　num = num / 10;
6 @! E: ~" O2 F7 ?5 w5 u  z) P　　} while (num);
　　// 将分拆之后的num进行乘法计算
4 G0 x2 C5 ]8 k, M- K
4 Q. W" M/ [$ S  J- S3 ~+ s3 O　　unsigned int i = 0,j = 0;

会计考友

</p>　　for(i = 0;i < tempnum.size();++i)
　　{
　　int carry = 0;// 存储每位计算时来自低位的进位
  c1 ?3 c# {+ t3 L　　for(j = 0;j < calcresult.size();++j)
* i' M8 u) A# Q% e9 v7 C9 n- v# W　　{
　　int bit1 = 0,bit2 = 0,res = 0;
　　bit1 = calcresult[j];
　　bit2 = tempnum;
  S) E: C+ T2 E1 v3 ~　　res = bit1 * bit2;
5 r( C3 L$ ~# C3 M8 a2 ^" g　　// 保存当前位
　　if((i+j)
* P0 K2 z2 a/ _　　{
　　// 临时结果中有对应位存在，则直接更新
　　rest[i+j] += (res + carry) % 10;
　　}
) F$ _5 a" Q  k! ]9 D: \　　else
　　{
　　// 没有对应位则需要添加
- }% D9 s- G9 C1 P) K　　rest.push_back((res+carry)%10);
　　}
　　// 有进位，则更新进位
+ N) b( C- {/ [　　carry = (res + carry) / 10;
　　}
　　// 如果计算之后还有最高位的进位，那么则直接添加进去
# H8 b, i5 |+ c% d/ g/ H1 I* R6 e　　if(carry)
　　{
　　// 保存当前位
! B# R  l2 f- V/ Z6 [7 a' _3 q1 Y# u　　if((i+j)
　　{
* N2 ?6 S; C% }& e7 ~5 N$ o3 L; g　　// 临时结果中有对应位存在，则直接更新
　　rest[i+j] += carry;
　　}
　　else
# ]) Z$ t3 C' ^) p# ]　　{
　　// 没有对应位则需要添加
　　rest.push_back(carry);
& S. z: Q6 v0 L& |" [$ a8 v# M　　}
　　}
　　}
- X5 J7 n7 ?) V' [* G( P　　// 上述计算之后，会出现有些位的数字超过了10，那是因为在处理每一位运算结果之后
' l* W& |% u( m# K( E5 P　　// 相加时地位向高位可能存在进位，上面没有考虑，所以需要进行调整
　　for(i = 0;i < rest.size();++i)
$ U; m4 o2 k  P( R/ W4 e　　{
2 H) X* S& X  X* D' ~$ S　　if(rest > 9)
　　{
　　if((i+1) != rest.size())
　　{
; Z% F9 v, a+ `9 n$ b1 F　　// 高位存在，则直接更新高位
. w) I2 L" K% Q, B) u% l$ I　　rest[i+1] += rest / 10;
　　rest = rest % 10;
& W' f  H! z2 i, c" D　　}
; Q8 r6 u: J4 ~' ]9 s% o9 j! k　　else
) a+ G# G. `3 F　　{
0 S. d3 E- F: e. j0 a6 y7 B& j# @　　// 高位不存在，则需要插入
　　rest.push_back(rest / 10);
2 \' ^) K+ i9 S3 n4 L　　rest = rest % 10;
) \1 T, M$ j% Y3 k　　}
　　}
1 u, y1 Q% [( c( }  P4 d/ _8 Q
8 b! R* \" x$ z- @7 N　　}

会计考友

</p>　　// 将计算结果存储到原来的容器中
　　calcresult.clear();
$ |8 i. s  I5 x% d! }4 f  L1 h　　for(i = 0;i < rest.size();++i)
' [% X5 v/ k- V! E8 }　　{
　　calcresult.push_back(rest);
0 w. Q% \1 o: L' x2 {4 |7 n' Y: A* ?2 p5 u　　}
　　}
3 u1 D$ j) I" Q2 [3 Y- m" r　　int main()
4 f7 t5 p9 f, g8 P# V: r8 L　　{
　　int num = 0;
8 T% C: J' _: ?% e* l　　vector calcresult;
　　// 将初值1赋进去
9 ~- G3 ~4 H( E5 }' l- Y　　calcresult.push_back(1);
+ Z7 u2 f: {" ?1 S! Y/ s　　// 获取欲求阶乘的整数

% m  }" w# V& ~. u6 Y$ j　　cout