算法的重要性人人都懂,坚持做下来的不多。曾经为了做一些高大上的项目,对一些基础知识并没有很在乎,以一种不会就百度的心态,现在越来越觉得良好的数据结构知识,有助于项目开发和对程序设计进行抽象出来。为此,现在想重新认识下算法,练习一下”内功”。
##数据类型与输入格式
1 2 3 4 5 6 7 8 9 10
| #include<stdio.h> int main(){ printf("%d\n",11111*11111); printf("%d\n",111111*111111); printf("%d\n",111111111*111111111); } 123454321 -539247567 1653732529
|
输入12 2 和属于12 2 和输入12 换行2效果一样。scanf的输入,对空格、TAB和回车都是无关紧要的,所以按Enter键并不意味着输入的结束。
##code test
###计算e
利用公式e=2+1/2!+1/3!+1/4!+.,编写程序计算无理数e的近似值,直到最后一项小于10-7为止.
1 2 3 4 5 6 7 8 9 10 11 12 13
| #include<stdio.h> int main(){ int i = 2; double sum = 2.0; int temp = 1; do{ temp = temp*i; sum +=1.0/temp; ++i; }while((1.0/temp)>=1e-7); printf("%.7f\n",sum); return 0; }
|
###计算阶乘之和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| #include<stdio.h> #include<time.h> int main(){ long sum = 0; int n; long factorial; int i = 1; scanf("%d",&n); do{ factorial = 1;//每执行一次循环体,都要重新声明并初始化。 for(int j = 1;j<=i;j++){ factorial*= j; } sum+=factorial; }while(++i<=n&&n<=1000000); printf("%ld\n",sum); printf("Time used =%.2f\n",(double)clock()/CLOCKS_PER_SEC);//计时器,输出所有时间 return 0; }
|
###数据统计fopen
while(scanf(“%d”,&x)==1)是什么意思 相当于 while(1){scanf(“%d”,&x)}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include<stdio.h> #define INF 1000000000 #define path_in "in.txt" #define path_out "out.txt" int main(){ FILE *fin, *fout; fout=stout; fin=fopen(path_in,"wt+"); if(fin==NULL) { printf("文件打不开\n"); return 0; } fout = fopen(path_out,"wt+"); if(fout == NULL) return 0; int x, n = 0,min = INF, max = -INF, s = 0; while (fscanf(fin,"%d",&x)==1) { s += x; if(x < min) min = x; if(x > max) max = x; n++; } fprintf(fout,"%d %d %.3f\n", min, max, (double)s/n); fclose(fin); fclose(fout); return 0; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #define LOCAL #include<stdio.h> #define INF 1000000000 #define path_in "in.txt" #define path_out "out.txt" int main(){ #ifdef LOCAL freopen(path_in,"r",stdin); freopen(path_out,"w",stdout); #endif int x, n = 0,min = INF, max = -INF, s = 0; while (scanf("%d",&x)==1) { s += x; if(x < min) min = x; if(x > max) max = x; n++; } printf("%d %d %.3f\n", min, max, (double)s/n); return 0; }
|
重定向的部分被写在了#ifdef 和 #endif中。 只有定义了LOCAL,才编译两条freopen语句。
中间结果可以写在注释中。好处:一旦需要时,把注释符号去掉即可。
本机测试时使用重定向方式读写文件。如果比赛要求读写标准输入输出,只需要在提交之前删除#define LOCAL即可。
**在算法竞赛中,如果不允许使用重定向方式读写数据,应使用fopen和fscanf/fprintf进行输入输出。
###开灯问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include<stdio.h> #include<string.h> #define maxn 1010 int a[maxn]; int main(){ memset(a,0,sizeof(a)); int p,t,first; first = 0; scanf("%d%d",&t,&p); for(int i=1;i<=p;i++){ for(int j=1;j<=t;j++){ if(j%i==0){ a[j] = !a[j]; } } } for(int i=1;i<=t;i++){ if(a[i]){ if(first){ printf(" "); printf("%d",i); }else{ first=1; printf("%d",i); } } } return 0; }
|
menset(a,0 sizeof(a))的作用是把数组a清零,它在string.h中定义。first是标记变量,用于输出空格格式的调整。
###蛇形数字
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include<stdio.h> #include<string.h> int main(){ int n,x,y,hxnum; scanf("%d",&n); int a[n][n]; memset(a,0,sizeof(a)); x=0;y=n-1;hxnum=1; a[x][y] = hxnum; while(hxnum<n*n){ while(x<n-1&&!a[x+1][y]){ a[++x][y]=++hxnum; } while(y>0&&!a[x][y-1]){ a[x][--y]=++hxnum; } while(x>0&&!a[x-1][y]){ a[--x][y]=++hxnum; } while(y<n-1&&!a[x][y+1]){ a[x][++y]=++hxnum; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ printf("%3d ",a[i][j]); } printf("\n"); } }
|
###刽子手游戏