程序设计综合实践PPT课件

1、程序设计综合实践程序设计综合实践程序设计综合实践程序设计综合实践程序设计综合实践程序设计综合实践课程简介v1.课程的目的与意义 重要实践性环节 通过本课程，学生可以了解数据结构、算法分析与设计的基本方法与基本原理 提高学生对于复杂工程问题分析问题、解决问题，从而运用所学知识解决实际问题的能力 为今后参加ACM竞赛、中国高校团体程序设计大赛-天梯赛，从事实际工作打下坚实基础程序设计综合实践程序设计综合实践课程简介v2.主要内容 第一讲：程序设计基础与竞赛入门 第二讲：数组与字符串 第三讲：递归与分治 第四讲：暴力求解 第五讲：回溯 第六讲：排序检索 第七讲：贪心算法 第八讲：综合程序设计综合实践

2、程序设计综合实践课程简介v3.考核方法 线下练习和线上考试（不准携带资料）结合v4.参考书目 1刘汝佳.算法竞赛入门经典（第二版）.清华大学出版社,2014年 2赵端阳,刘福庆等.算法分析与设计.清华大学出版社,2015年 3俞勇.ACM国际大学生程序设计竞赛.清华大学出版社,2013年 4赵端阳,吴艳等.ACM大学生程序设计竞赛.北京邮电大学出版社,2016年 1程序设计综合实践程序设计综合实践课程简介v5.学习练习网站 浙江大学（ZJU）：http:/ 浙江大学（ZJU）:https:/ 北京大学（PKU）： 杭州电子科技大学(HDU)：http:/ 浙江工业大学

3、（ZJUT）：http:/程序设计综合实践程序设计综合实践课程简介v6.调试工具vDev C+ (推荐使用5.10版，可以适用于64位和32位的Windows) https:/ (最新版本16.01，用于各种Windows的版本)v https:/ 第一讲：程序设计基础与竞赛入门 第二讲：数组与字符串 第三讲：递归与分治 第四讲：暴力求解 第五讲：回溯 第六讲：排序检索 第七讲：贪心算法 第八讲：综合程序设计综合实践程序设计综合实践教学目标 （1）掌握C、C+语言的基础知识并能用于编写程序； （2）能够熟练使用DEVC、VC+等程序设计竞赛常用IDE进行程序的编写与调试。 （3）理解算法竞赛中

4、的程序三部曲：输入、计算、输出，并理解算法竞赛中对输入输出的严格规定； （4）记住算法竞赛的目标及其对程序的要求；程序设计综合实践程序设计综合实践教学内容v一.从算法竞赛角度看程序设计v二.ACM入门v三.天梯赛入门程序设计综合实践程序设计综合实践一、从算法竞赛角度看程序设计-程序三部曲v例题1-1：v圆柱体的表面积 输入底面半径r和高h，输出圆柱体的表面积，保留3位小数，格式见样例。 样例输入： 3.5 9 样例输出： Area = 274.889#include #includeint main()const double pi =acos(-1.0);double r,h,s1,s2,s

5、;scanf(%lf%lf,&r,&h);s1=pi*r*r;s2=2*pi*r*h;s=s1*2.0+s2;printf(Area = %.3fn,s);return 0;程序三部曲：输入，计算，输出程序设计综合实践程序设计综合实践一、从算法竞赛角度看程序设计v 提示1-4：在算法竞赛中，输入前不要打印提示信息。输出完毕后应立即终止程序，不要等待用户按键，因为输入输出过程都是自动的，没有人工干预。v 提示1-5：在算法竞赛中，不要使用头文件conio.h，包括getch()、clrscr()等函数。一般输出格式非常严格，多一个或者少一个字符都不可以。v 提示1-6:在算法竞赛

6、中，每行输出均以回车符结束，包括最后一行特别说明，每行的行首不能有空格，行末通常可以有多余空格。另外，输出的每两个数或者字符串之间应以单个空格隔开。程序设计综合实践程序设计综合实践#includeint main()int a,b,c;scanf(%d%d%d,&a,&b,&c);if(ab&bc) printf(%d %d %dn,a,b,c) ;if(ac&cb) printf(%d %d %dn,a,c,b) ;if(ba&ac) printf(%d %d %dn,b,a,c) ;if(bc&ca) printf(%d %d %dn

7、,b,c,a) ;if(ca&ab) printf(%d %d %dn,c,a,b) ;if(cb&ba) printf(%d %d %dn,c,b,a) ;如果输入：1 1 1 则错误！提示1-18：算法竞赛的目标是编程对任意输入均得到正确的结果，而不仅是样例数据。#includeint main()int a,b,c,t;scanf(%d %d %d,&a,&b,&c);if(ab) t=a;a=b;b=t;if(ac) t=a;a=c;c=t;if(bc) t=b;b=c;c=t;printf(%d %d %dn,a,b,c) ;return 0;

8、一、从算法竞赛角度看程序设计-分支结构v例题1-5：v三整数排序v输入3个整数，从小到大排序后输出。v样例输入：v20 7 33v样例输出：v7 20 33程序设计综合实践程序设计综合实践一、从算法竞赛角度看程序设计-for循环v例题2-1：vaabbv输出所有形如aabb的4位完全平方数（即前两位数字相等，后两位数字也相等）。#include#includeint main()for(int a=1;a=9;a+) for(int b=0;b=9;b+) int n=a*1100+b*11; int m=floor(sqrt(n)+0.5); if(m*m=n) printf(%dn,n);

9、return 0;提示2-7：浮点运算可能存在误差。在进行浮点数比较时，应考虑浮点误差。程序设计综合实践程序设计综合实践一、从算法竞赛角度看程序设计-break、continuev例题2-1：vaabbv输出所有形如aabb的4位完全平方数（即前两位数字相等，后两位数字也相等）。#includeint main()for(int x=1;x+)int n=x*x;if(n9999)break;int hi=n/100;int lo=n%100;if(hi/10=hi%10&lo/10=lo%10)printf(%dn,n); return 0;程序设计综合实践程序设计综合实践一、从算法

10、竞赛角度看程序设计-while循环#includeint main() int n; int count=0; scanf(%d,&n); while(n1) if(n%2=1) n=n*3+1; else n/=2; count+; / printf(%d,n); printf(%dn,count); return 0; /* 当输入987654321时，输出1；这是明显的乘法溢出问题 int 整数的大小是：-21474836482147483648 即：-231231-1之间 然而题目中的n的值的范围在109，所以会溢出 如何决这一问题 ？ */ 程序设计综合实践程序设计综合实践一

11、、从算法竞赛角度看程序设计-while循环/正确代码#include#includeint main() long long int n; int count=0; scanf(%lld,&n); while(n1) if(n%2=1) n=n*3+1; else n/=2; count+; printf(%dn,count); return 0;程序设计综合实践程序设计综合实践一、从算法竞赛角度看程序设计v本节练习题：v1.习题2-2v2.习题2-4程序设计综合实践程序设计综合实践二、ACM入门v1.ACM简介 简称ACM竞赛由美国计算机协会 (ACM) 主办的一项程序设计算法类 旨

12、在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力。 强调算法的高效性，不仅要解决一个指定的问题，而且必须以最佳的方式解决该问题； 它涉及知识面广，与大学计算机专业本科和研究生课程直接相关，如程序设计、离散数学、组合数学、数据结构和算法分析等，对数学要求特别高。程序设计综合实践程序设计综合实践二、ACM入门v2.竞赛规则 时间为5个小时，一般有68道试题，由同队的三名选手使用同一台计算机协作完成。 完成一道试题后，参赛队可将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。 程序运行不正确是指出现以下4

13、种情况之一：运行出错(run-timeerror)；运行超时(time-limitexceeded)；运行结果错误(wronganswer)；运行结果输出格式错误(presentationerror)。程序设计综合实践程序设计综合实践二、ACM入门v2.竞赛规则 竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。 总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交不通过会罚时20分钟)。 总决赛可以使用的程序设计语言包括C，C+及Java，也可以使用其它语言。程序设计综合实践程序设计综合实践

14、二、ACM入门v3. 竞赛的要求及重要性 竞赛的参赛对象是本专科学生，不限制年级与专业。 难度高，强度大，并不是所有人都适合参加。 想要参加ACM竞赛的学生需要精通计算机科学的内容、强烈的兴趣，并且耐得住寂寞。 ACM的奖项较少，含金量较高。 对于就业，尤其是对于进入大型的IT或者软件公司，ACM竞赛有着很大的帮助。 对于考取研究生来说，能增加面试的成功率。程序设计综合实践程序设计综合实践二、ACM入门v4.国国( (省省) )内开展较好的高校内开展较好的高校 清华大学、北京大学 浙江大学、复旦大学、上海交通大学、中山大学、北京航天航空大学 北京邮电大学、电子科技大学 郑州大学、河南理工大学

15、郑州轻工业学院、南阳理工学院程序设计综合实践程序设计综合实践二、ACM入门v5.我校的开展情况程序设计综合实践程序设计综合实践二、ACM入门-基本的输入输出v1.输入不说明有多少个Input Block,以EOF为结束标志 题目： 参见：HDOJ_1089 http:/ 说明：EOF是一个预定义的常量，等于-1程序设计综合实践程序设计综合实践二、ACM入门-基本的输入输出v源码：#include int main() int a,b; while(scanf(%d %d,&a, &b) != EOF) printf(%dn,a+b); 程序设计综合实践程序设计综合实践二、ACM

16、入门-基本的输入输出v2.输入一开始就会说有N个Input Block,下面接着是N个Input Block。 参见：HDOJ_1090 http:/ 本类输入解决方案(C语法)scanf(%d,&n) ; for( i=0 ; in ; i+ ) . 程序设计综合实践程序设计综合实践二、ACM入门-基本的输入输出v3.输入不说明有多少个Input Block,但以某个特殊输入为结束标志。 参见：HDOJ_1091 http:/ 本类输入解决方案(C语法) while(scanf(%d,&n)&n!=0 ) . 程序设计综合实践程序设计综合实践二、ACM入门-基本的输入

17、输出v本节练习题 http:/ http:/ http:/ http:/ http:/ http:/ http:/ 团体程序设计天梯赛是中国高校计算机大赛的竞赛版块之一，赛旨在提升学生计算机问题求解水平，增强学生程序设计能力，培养团队合作精神，提高大学生的综合素质，同时丰富校园学术气氛，促进校际交流，提高全国高校的程序设计教学水平。v 比赛重点考查参赛队伍的基础程序设计能力、数据结构与算法应用能力，并通过团体成绩体现高校在程序设计教学方面的整体水平。v 竞赛题目均为在线编程题，比赛时长3小时，由搭建在网易服务器上的PAT在线裁判系统自动评判。难度分3个梯级：基础级、进阶级、登顶级。以个人独立竞技、团体计分的方式进行排名。v 每年3月份，各校最多允许派3