Posted on 2011-05-01 01:25
acpeng 閱讀(290)
評論(1) 編輯 收藏 引用 所屬分類:
ACM程序
貌似現(xiàn)在TLU的程序設(shè)計大賽舉辦的越來越勤了，像我這樣一個codefans，怎么說也要來捧捧場，本人拋磚引玉，貼一個非官方的解題報告，僅供娛樂~~本人所貼代碼都是在OJ里面通過的，所以請放心閱讀~~
1：階乘問題
對于一個任意位數(shù)的整數(shù)n，則n的位數(shù)digit=[log(10)(n)]+1;這里log(10)(x)表示以10為底的x的對數(shù)，[x]表示不超過實(shí)數(shù)x的最大整數(shù)，這個證明很容易，稍微算一下就知道了。
對于N!來說，取對數(shù)，得到log(10)(N!)=log(10)(N)+log(10)(N-1)+log(10)(N-2)+...+log(10)(2)因此，要知道N！的位數(shù)，只要求出上式右邊的值，再取整加一就可。代碼如下：
1
#include<stdio.h>
2#include<math.h>
3int main()
4
{
5
long int data;
6 double cont;
7 while(scanf("%ld",&data)!=EOF)
8
{
9 cont=0;
10 while(data>1)
11 {
12 cont=cont+log10(data);
13 data--;
14
}
15 cont=cont+1;
16 printf("%d\n",(int)cont);
17 }
18 return 0;
19
}
20
OJ地址：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=15262:判斷回文串，設(shè)置首尾指針，對值進(jìn)行對比即可，簡單
1#include<stdio.h>
2#include<string.h>
3int main()
4{
5 int T,i,end,RetnBool;
6 char str[1000]="\0";
7 scanf("%d",&T);
8 while(T--)
9 {
10 scanf("%s",str);
11 end=(int)strlen(str);
12 end--;
13 i=0;
14 RetnBool=1;
15 while(i<=(end-i))
16 {
17 if(*(str+i)!=*(str+end-i))
18 {
19 RetnBool=0;
20 break;
21 }
22 i++;
23 }
24 if(RetnBool==1)
25 printf("yes\n");
26 else
27 printf("no\n");
28 memset(str,0,sizeof(str));
29 }
30 return 0;
31}
32
OJ地址：
http://acm.hdu.edu.cn/showproblem.php?pid=2029
3:類似于二進(jìn)制的轉(zhuǎn)化，用 N 除以R，余數(shù)作為R進(jìn)制的每一項，商作為新的N，反復(fù)循環(huán)即可。注意輸出時要逆序。注意負(fù)數(shù)
1#include<stdio.h>
2int main()
3{
4 long int N;
5 int R,i,j;
6 int data[40];
7 while(scanf("%ld%d",&N,&R)!=EOF)
8 {
9 i=0;
10 if(N<0)
11 {
12 N=-N;
13 printf("-");
14 }
15 while(N>R)
16 {
17 data[i]=N%R;
18 N=N/R;
19 i++;
20 }
21 data[i]=N;
22 for(j=i;j>=0;j--)
23 {
24 if(data[j]>=10)
25 {
26 printf("%c",'A'+data[j]-10);
27 }
28 else
29 printf("%d",data[j]);
30 }
31 printf("\n");
32 }
33 return 0;
34}
35
OJ地址：http://acm.hdu.edu.cn/showproblem.php?pid=2031
4:這是一個經(jīng)典問題，常用的方法是建立鏈表，在網(wǎng)上搜一下，一大堆程序，也不乏好的算法。這里貼上我寫的一個循環(huán)鏈表算法。因為m的范圍較小，所以只要int型就行了，而且不需要太巧妙的算法，O(mn)內(nèi)時間復(fù)雜度都可以滿足1秒以內(nèi)的運(yùn)行時間。不過像下面這個OJ里面(http://acm.hdu.edu.cn/showproblem.php?pid=3089)，m的范圍太大(1<=m<=10^12)，所以普通算法時間太長，無法AC。我也沒想到更好的算法^^，如果哪位仁兄在這里AC了，請告訴我一下，共同學(xué)習(xí)哈
1#include<stdio.h>
2#include<malloc.h>
3#include<stdlib.h>
4int m;
5int n;
6struct node *h;
7struct node
8{
9 struct node *next;
10 int data;
11};
12struct node * create(struct node *h)
13{
14 struct node *p,*q; int i;
15 h=p=q=(struct node *)malloc(sizeof(struct node));
16 p->next=NULL; p->data=1;
17 for(i=2;i<=m;i++)
18 {
19 p=(struct node *)malloc(sizeof(struct node));
20 q->next=p; p->data=i; p->next=NULL;
21 q=p;
22 }
23 p->next=h;
24 return h;
25}
26int fun(struct node *h)
27{
28 struct node *p=h,*q; int i;
29 if(n>1)
30 {
31 while(p->next!=p)
32 {
33 i=1;
34 while(i<n-1) {p=p->next; i++;}
35 q=p->next;
36 p->next=q->next;q->next=NULL;
37 free(q);
38 p=p->next;
39 }
40 }
41 else if(n==1)
42 {
43 p->data=m;
44 }
45 return p->data;
46}
47int main()
48{
49 struct node *h;
50 while(scanf("%ld%ld",&m,&n)!=EOF)
51 {
52
53 h=create(h);
54 printf("%d\n",fun(h));
55 h=NULL;
56 }
57 return 0;
58}
59
本題m<10000的OJ地址：
http://acm.cugb.edu.cn/JudgeOnline/showproblem?problem_id=1056