随笔-6  评论-2  文章-0  trackbacks-0
 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 char a[36000];
 5 void rev()
 6 {
 7     int len=strlen(a),i;
 8     char t;
 9     for(i=0;i<len/2;++i)
10     {
11         t=a[i];
12         a[i]=a[len-1-i];
13         a[len-1-i]=t;
14     }
15 }//strrev()貌似不是标准库函数,囧
16 
17 void multi(int n)
18 {
19     int i,l=strlen(a),m=0,jw=0;
20     rev();
21     char t[36000];
22     for(i=0;i<l;++i)
23     {
24         t[i]=((a[i]-'0')*n+jw)%10+'0';
25         jw=((a[i]-'0')*n+jw)/10;
26     }
27     if(jw>=1000)
28     {
29         t[i]=jw%10+'0';
30         t[i+1]=(jw/10)%10+'0';
31         t[i+2]=(jw/100)%10+'0';
32         t[i+3]=jw/1000+'0';
33         t[i+4]='\0';
34     }
35     else if(jw>=100)
36     {
37         t[i]=jw%10+'0';
38         t[i+1]=(jw/10)%10+'0';
39         t[i+2]=jw/100+'0';
40         t[i+3]='\0';
41     }
42     else if(jw>=10)
43     {
44         t[i]=jw%10+'0';
45         t[i+1]=(jw/10)%10+'0';
46         t[i+2]='\0';
47     }
48     else if(jw)
49     {
50         t[i]=jw+'0';
51         t[i+1]='\0';
52     }
53     else t[i]='\0';
54     strcpy(a,t);
55     rev();
56 }//将字符串乘n,需考虑最后的进位的位数。
57 
58 int main()
59 {
60     int n;
61     while(cin>>n)
62     {
63         memset(a,0,36000);
64         a[0]='1';
65         a[1]='\0';
66         for(int i=2;i<=n;++i)multi(i);
67         cout<<a<<endl;
68     }
69     return 0;
70 }
71 

  由于一直不肯写个大整数的类,又不会用JAVA,遇到这种题目真是感到很难受。不过我今天用了一种比较耗时但确实思路简单的方法过了这道题。首先,我们必须知道10000!到底有多少位,这样才好定义合适的数组。
log10(2)+log(3)+...+log10(10000)=35659.9,所以定义一个36000的字符数组就够了。整个实现比较简单但是用了2312MS.....应该分治之类的算法会好点,最快的100MS就过了。估计是重复的反转和复制耗时了。
posted on 2010-12-06 18:22 cometrue 阅读(285) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理