Posted on 2011-05-01 01:25
acpeng 阅读(267)
评论(1) 编辑 收藏 引用 所属分类:
ACM程序
貌似现在TLU的程序设计大赛举办的越来越勤了，像我这样一个codefans，怎么说也要来捧捧场，本人抛砖引玉，贴一个非官方的解题报告，仅供娱乐~~本人所贴代码都是在OJ里面通过的，所以请放心阅读~~
1：阶乘问题
对于一个任意位数的整数n，则n的位数digit=[log(10)(n)]+1;这里log(10)(x)表示以10为底的x的对数，[x]表示不超过实数x的最大整数，这个证明很容易，稍微算一下就知道了。
对于N!来说，取对数，得到log(10)(N!)=log(10)(N)+log(10)(N-1)+log(10)(N-2)+...+log(10)(2)因此，要知道N！的位数，只要求出上式右边的值，再取整加一就可。代码如下：
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:判断回文串，设置首尾指针，对值进行对比即可，简单
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:类似于二进制的转化，用 N 除以R，余数作为R进制的每一项，商作为新的N，反复循环即可。注意输出时要逆序。注意负数
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:这是一个经典问题，常用的方法是建立链表，在网上搜一下，一大堆程序，也不乏好的算法。这里贴上我写的一个循环链表算法。因为m的范围较小，所以只要int型就行了，而且不需要太巧妙的算法，O(mn)内时间复杂度都可以满足1秒以内的运行时间。不过像下面这个OJ里面(http://acm.hdu.edu.cn/showproblem.php?pid=3089)，m的范围太大(1<=m<=10^12)，所以普通算法时间太长，无法AC。我也没想到更好的算法^^，如果哪位仁兄在这里AC了，请告诉我一下，共同学习哈
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