2018-05-03

算法竞赛入门

算法的重要性人人都懂，坚持做下来的不多。曾经为了做一些高大上的项目，对一些基础知识并没有很在乎，以一种不会就百度的心态，现在越来越觉得良好的数据结构知识，有助于项目开发和对程序设计进行抽象出来。为此，现在想重新认识下算法，练习一下”内功”。

##数据类型与输入格式

#include<stdio.h>
int main(){
	printf("%d\n",11111*11111);
    printf("%d\n",111111*111111);
    printf("%d\n",111111111*111111111);
} //出现溢出
123454321
-539247567
1653732529
//当前竞赛流行的平台中，int都是32位，范围是-2的31次到2的31次-1。

1	scanf("%d%d",&a,&b);

输入12 2 和属于12 2 和输入12 换行2效果一样。scanf的输入，对空格、TAB和回车都是无关紧要的，所以按Enter键并不意味着输入的结束。

##code test

###计算e

利用公式e=2+1/2!+1/3!+1/4!+.,编写程序计算无理数e的近似值,直到最后一项小于10-7为止.

#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);//10-7次用1e-7表示。
	printf("%.7f\n",sum);
	return 0;
}

###计算阶乘之和

#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)}

#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;
}

#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进行输入输出。

###开灯问题

#include<stdio.h>
#include<string.h>
#define maxn 1010
int a[maxn];
int main(){
    memset(a,0,sizeof(a));//数组a置为0
    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是标记变量，用于输出空格格式的调整。

###蛇形数字

#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");
	}
}