【c语言】算法竞赛入门篇

【c语言】算法竞赛入门篇

标记位：记录文章更新到哪里了
3-1 逆序输出

引言

参考书为刘汝佳先生编著的算法竞赛入门经典(第二版)，开始立足从c语言学习算法。

注：此文不再像Java语言或框架的学习一样，补充很多语句帮助理解
此处对于简单的算法一笔带过，对于较难的算法更多的是提供思路。

目录 一：程序设计入门 - 算术表达式

1-1 计算并输出1+2的值

#include
int main(){
	printf("1+2=%dn",1+2);
	return 0;
}

1-2 计算并输出8/5的值

#include
int main(){
	printf("8/5=%.1fn",8.0/5.0);
	return 0;
}

1-3 复杂的表达式计算

#include
#include
int main(){
	printf("%.8fn",1+2*sqrt(3)/(5-0.1));
	return 0;
}

- 变量及其输入

1-4 a+b问题

#include
int main(){
	int a,b;
	scanf("%d,%d",&a,&b);
	printf("a+b=%dn",a+b);
	return 0;
}

1-5 圆柱体表面积

#include
#include
int main(){
	double r,h,s1,s2,area;
	const double pi=acos(-1.0);
	scanf("%f,%f",&r,&h);
	s1=pi*r*r;
	s2=2*pi*r*h;
	area=s1+s2;
	printf("area=%.3f",area);
	return 0;
}

- 顺序结构程序设计

1-6 三位数反转

#include
int main(){
	int n;
	scanf("%d",&n);
	while(n>0){
		printf("%d",n%10);
		n/=10;
	}
	return 0;
}

1-7 变量交换-普通版本

#include
int main(){
	int a,b,temp;
	scanf("%d,%d",&a,&b);
	temp=a;
	a=b;
	b=temp;
	printf("a=%d,b=%d",a,b);
	return 0;
}

1-8 变量交换-无中转变量版

#include
int main(){
	int a,b;
	scanf("%d,%d",&a,&b);
	a=a+b;
	b=a-b;
	a=a-b;
	printf("a=%d,b=%d",a,b);
	return 0;
}

1-9 变量交换-大一学生吃瓜版

#include
int main(){
	int a,b;
	scanf("%d,%d",&a,&b);
	printf("a=%d,b=%d",b,a);
	return 0;
}

- 分支结构程序设计

1-10 鸡兔同笼

#include
int main(){
	int chicken,rabbit,head,root;
	scanf("%d,%d",&head,&root);
	if(m-2*n<0||4*2-m<0)
		printf("errors:No answer sout");
	else
		printf("chicken=%d,rabbit=%d",(head*4-root)/2),(root-2*head)/2,;
	
}

1-11 三个整数排序-直接求解版

#include
int main(){
	int num1,num2,num3;
	scanf("%d,%d,%d",&num1,&num2,&num3);
	if(num1>=num2&&num2>=num3)
			printf("%d,%d,%d",num1,num2,num3);
	if(num1>=num2&&num3>=num2)
			printf("%d,%d,%d",num1,num3,num2);
	if(num2>=num1&&num1>=num3)
			printf("%d,%d,%d",num2,num1,num3);
	if(num2>=num1&&num3>=num1)
			printf("%d,%d,%d",num2,num3,num1);
	if(num3>=num1&&num2>=num1)
			printf("%d,%d,%d",num3,num2,num1);
	if(num3>=num1&&num1>=num2)
			printf("%d,%d,%d",num3,num1,num2);
	return 0;
}

1-12 三个整数排序-仿冒泡排序

#include
int main(){
	int num1,num2,num3,temp;
	scanf("%d,%d,%d",&num1,&num2,&num3);
	if(num2
		temp=num1;
		num1=num2;
		num2=temp;
	}
	if(num3
		temp=num1;
		num1=num3;
		num3=temp;
	}
	if(num2
		temp=num2;
		num2=num3;
		num3=temp;
	}
	printf("num1=%d,num2=%d,num3=%d",num1,num2,num3);
	return 0;
}

- 注解与练习题

1-15 输入输出实验

#include
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d %dn",a,b);
	return 0;
}

习题1-1 平均数
输入三个整数，输出他们的平均数，保留三位小数

#include
int main(){
	int num1,num2,num3;
	double ave;
	scanf("%d,%d,%d",&num1,&num2,&num3);
	ave=(num1+num2+num3)/3;
	printf("ave=%.3f",ave);
	return 0;
}

习题1-2 温度
输入华氏温度f，输出对应的摄氏温度c，保留三位小数。c=5(f-32)/9

#include
int main(){
	double f,c;
	scanf("%f",f);
	printf("f=%.3f",5*(f-32)/9);
	return 0;
}

习题1-3 连续和
输入正整数n，输出1+2+…+n的值。

#include
int main(){
	int n;
	scanf("%d",&n);
	printf("%d",n*(n+1)/2)
	return 0;
}

习题1-4 正弦和余弦
输入正整数n，输出n度的正弦，余弦函数值。

#include
#include
int main(){
	const double pi=acos(-1.0);
	int n;
	printf("cos(%d)=%f,sin(%d)=%f",cos(x/180.0*pi),sin(x/180.0*pi));
	return 0;
}

习题1-5 打折
一件衣服95元，若消费满300元可打八五折。输入购买衣服件数，输出需要支付的金额。

#include
int main(){
	int n;
	double sum;
	scanf("%d",&n);
	sum=n>3?n*95*0.85:n*95;
	printf("%f",sum);
	return 0;
}

习题1-6 三角形
输入三角形3条边长度值，判断是否能为直角三角形的3个边长，如果可以，则输出yes，如果不能，则输出no。如果根本无法构成三角形，则输出not a triangle。

#include
int main(){
	int a,b,c;
	scanf("%d,%d,%d",&a,&b,&c);
	if(a+b<=c||a+c<=b||b+c<=a){
		ptintf("not a triangle");
		return;
	}
	if(a*a+b*b=c*c||c*c+b*b=a*a||a*a+c*c=b*b) 		   
	printf("yes");
	else  printf("no");
	return 0;
}

习题1-7 年份
输入年份，判断是否是闰年，如果是，则输出yes，如果不是，则输出no。

#include
int main(){
	int year;
	scanf("%d",&year);
	if((year%100!=0&&year%4==0)||year%400==0)
	printf("yes");
	else
	printf("no");
	return 0;
}

二：循环结构程序设计 - for循环

2-1 输出1，2，3，…n的值

#include
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		printf("%d",i);
	return 0
}

- while循环和do-while循环

2-2 3n+1问题

#include
int main(){
	int i,count=0;
	scanf("%d",&i);
	while(i>1){
		if(i%2==1) n=n3+1;
		else n/=2;
		count++;
	}
	printf("%d",count);
	
}

- 循环的代价

2-3 阶乘之和

#include
int main(){
	int n,sum=0;
	scanf("%d",&n);
	for(int i=0;i<=n;i++){
		int multiply=1;
		for(int j=0;j
			multiply*=j;
			sum+=multiply;
		}
	}
	printf("%dn",sum);
	return 0;
}

- 注解与练习题

习题2-1 水仙花数

#include
int main(){
	for(int i=100;i<1000;i++){
		if(i==(i%10)*(i%10)*(i%10)+(i/10%10)*(i/10%10)*(i/10%10)+(i/100)*(i/100)*(i/100)) 
		    printf("%dn",i);
	}
}

习题2-2 韩信点兵
韩信让士兵三人一排，五人一排，七人一排，看一眼排尾人数便知道总人数。输入三个非负数代表每种排尾人数，输出总人数的最小值。总人数不少于10人，不多于一百人。

#include
int main(){
	int a,b,c;
	scanf("%d,%d,%d",&a,&b,&c);
	int lock=0;
	for(i=10;i<101;i++){
		if(i%3==a&&i%5==b&&i%7==c){
			printf("%d",i);
			lock=1;
			return;
		}
	}
	if(lock==0)printf("no answer");
	return 0;
}

习题2-3 倒三角形

#include
int main(){
	int n;
	scanf("%d",&n);
	9 7 5 3 1
	for(int j=0;j
		for(int i=0;i
			printf("*");
		}
	}
	
}

三：数组和字符串 - 数组

3-1 逆序输出

- 字符数组 - 竞赛题目 - 练习 四：函数和递归 - 自定义函数和结构体 - 函数调用与参数传递 - 递归 - 竞赛题目 - 练习 五：c++和STL入门 - 从c到c++ - STL初步 - 大整数类 - 竞赛题目 - 练习 六：数据结构基础 - 再谈栈和队列 - 链表 - 树和二叉树 - 图 - 竞赛题目 - 练习 七：暴力求解法 - 简单枚举 - 枚举排列 - 子集生成 - 回溯法 - 路径寻找问题 - 迭代加深搜索 - 竞赛题目 - 练习 八：高效算法设计 - 算法分析初步 - 再谈排序与检索 - 递归与分治 - 贪心法 - 算法设计与优化策略 - 竞赛题目 - 练习 九：动态规划初步 - 数字三角形 - DAG上的动态规划 - 多阶段决策问题 - 经典模型 - 竞赛题目 - 练习 十：数学概念与方法 - 数论初步 - 计数与概率基础 - 数学专题 - 竞赛题目 - 练习 十一：图论模型与算法 - 再谈图 - 最小生成树 - 最短路径问题 - 网络流初步 - 竞赛题目 - 练习 - 总结与展望 十二：高级专题 - 选讲专题 - 难题选解 - 练习 附录A：开发环境与方法 - 命令行 - OS脚本编程入门 - 编译器和调试器