Posted on 2010-08-30 17:39
lzh525 阅读(720)
评论(0) 编辑 收藏 引用 所属分类:
big num
/*
一个大整数的问题。首先想到了字符串处理的方法，将乘法换成除法来做；如下代码1实现提交后果然超时。后来发现不止如此，还有一些问题处理错误.,后来转换思路终于在代码2下AC了此题；
*/
/* 代码1*/
1
#include<iostream>
2#include<string.h>
3using namespace std;
4const int MAX=35665;
5char a[MAX],b[MAX];
6int lena,lenb;
7
8void init(char *n,int &m)
9
{
10
int i;
11 for(i=0;i<MAX;i++)
12 n[i]='0';
13 n[0]='1';
14 m=1;
15
}
16
17void turn(char *n,int m)
18{
19 int i;
20 char tmp;
21 for(i=0;i<m/2;i++)
22
{
23 tmp=n[i];
24 n[i]=n[m-i-1];
25 n[m-i-1]=tmp;
26
}
27}
28
29void add(char *a,char *b)
30{
31 int i,carry;//存储进位数
32 char c;
33 carry=0;
34 for(i=0;i<=lena;i++)
35 {
36 c=a[i];
37 a[i]=((carry+(c-'0')+(b[i]-'0'))%10)+'0';
38 carry=(carry+(c-'0')+(b[i]-'0'))/10;
39 }
40 if(a[lena]!='0')
41 lena++;
42}
43
44void copy(char *a,char *b)
45{
46 int i;
47 for(i=0;i<=lena;i++)
48 b[i]=a[i];
49 lenb=lena;
50}
51
52void multiply(char *a,int n)
53{
54 int i;
55 for(i=1;i<=n;i++)
56 add(a,b);
57 copy(a,b);
58}
59
60int main()
61{
62 int n,k;
63 while(cin>>n)
64 {
65 if(n==0||n==1)
66 {
67 cout<<"1\n";
68 continue;
69 }
70 init(a,lena);
71 init(b,lenb);
72 for(k=2;k<=n;k++)
73 {
74 multiply(a,k-1);
75 }
76 turn(a,lena);
77 a[lena]='\0';
78 cout<<a<<endl;
79 }
80 return 0;
81}
82
//大整数问题，用整型数组来存放。为了节约时间，将10进制乘法转为10000进制乘法（关键）.......
/* 代码2*/
1
2#include<iostream>
3using namespace std;
4const int M=8915;
5int p[M];
6
7void init()
8{
9 int i;
10 for(i=1;i<M;i++)
11 p[i]=0;
12 p[1]=1;
13 p[0]=1;
14}
15
16void multy( int *a,int k)//乘法函数//////////////////
17{
18 int i,carry=0,tmp;//carry:乘法的进位数
19 for(i=1;i<=a[0]+1;i++)
20 {
21 tmp=a[i]*k+carry;//开始时由于经验主义错误，误将乘法问题处理成加法问题（ tmp=（a[i]+carry)*k）
22 a[i]=tmp%10000;
23 carry=tmp/10000;
24 }
25 if(a[a[0]+1]!=0)
26 a[0]++;
27}
28
29int main()
30{
31 int i,n,first;
32 while(cin>>n)
33 {
34 init();
35 for(i=2;i<=n;i++)
36 multy(p,i);
37 first=1;
38 for(i=p[0];i>=1;i--)
39 {
40 if(first)//小问题，整型数组最后一位不超过四位时应忽略前导0
41 {
42 cout<<p[i];
43 first=0;
44 continue;
45 }
46 printf("%04d",p[i]); //输出关键，当后面的整型数组中小于四位时要输出前导0 ""%04d""是关键
47 }
48 cout<<endl;
49 }
50 return 0;
51}