程序设计实训专题讲座

一、程序设计训练目的和教学要求“C程序设计训练”是在学习“C语言程序设计”课程之后进行的一个实践教学环节，程序设计训练的目的是：1．进一步培养学生结构化程序设计的思想，加深对高级语言基本语言要素和控制结构的理解；2．针对C语言中的重点和难点内容进行训练，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格。3．掌握C语言的编程技巧和上机调试程序的方法。4．掌握程序设计的常用算法及模块化程序设计方法。5.掌握项目与工程设计的基本方法。本程序设计训练是利用C语言理论和实验课中学到的编程知识和编程技巧，通过布置具有一定难度、一定编程量的程序设计训练题目，使学生通过程序设计训练掌握高级编程语言的知识和编程技术，掌握程序设计的思想和方法，具备利用计算机求解实际问题的能力。二、程序设计训练的基本要求设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包括上级操作规范）。本程序设计训练的基本步骤与要求是：1．问题分析及解决方案框架确定充分地分析和理解问题本身，弄清要求做什么（Whattodo?）。在确定解决方案框架过程中（Howtodo?），考虑怎样使程序结构清晰、合理、简单和易于调试，并确定每个函数的简单功能，以及函数之间的调用关系。2．详细设计和编码确定算法的主要流程，再此基础上进行代码设计（Coding），每个明确的功能模块程序一般不超过60行，否则要进一步划分。3．上机前编写程序与检查上机前程序检查可有效提高调试效率，减少上机调试程序时的无谓错误。程序检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，把程序中的明显错误事先排除。4．上机调试程序5．完成程序设计训练报告①问题描述：题目要解决的问题是什么。②设计设计算法：主要算法思想，用流程图表示。实现注释：各项功能的实现程度。调试报告：调试过程中遇到的主要问题，是如何解决的；对设计和编码的回顾讨论和分析；改进设想；经验和体会等。③如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含其他测试数据和运行输出。三、程序设计训练的内容见程序设计训练题目（共8题）。要求都能编写程序和运行，但验收时，1~5题中任抽一道题，6~8题中任抽一道题，并提交所抽中的两题的实验报告。四、程序设计训练安排1、课堂教学（1周，8学时）。用于讲授程序设计的方式方法，包括原问题的分析、算法设计、程序编写以及调试等，内容从基本程序设计到项目的实现，以及程序设计文档的编制方法。a)程序设计的基本方法b)程序代码的规范（最佳实践法）c)工程方法论d)项目实践2、训练辅导（2周，20学时）(8月24号~下学期开学现场辅导：以2个自然班为教学班，每天2课时现场辅导，每教学班一名教师配一名助教。3、测试（1周，4学时）学生从3类（见训练内容）题中，各选择一道，提前写好设计训练报告，现场编写（断网、断U盘）程序，独立完成，根据完成情况予以评分。五、考核方式与评分办法通过程序实现、总结报告和学习态度综合考评，并结合学生的动手能力，独立分析解决问题的能力和创新精神。成绩分优、良、中、及格和不及格五等。考核标准包括：1．程序设计的正确性，程序结构是否合理、编程风格（50%）。2．学生的工作态度、动手能力、创新精神及出勤率（30%）。3．总结报告（20%）。六、程序设计报告的封面程序设计基础课程实训题目：院系：专业班级：姓名：学号：指导老师：七、训练报告的格式一、目的和要求二、设计内容三、运行环境四、设计步骤五、流程图六、源代码七、运行结果八、总结八、部分训练题目算法分析1、日历问题问题描述在我们现在使用的日历中,闰年被定义为能被4整除的年份，但是能被100整除而不能被400整除的年是例外，它们不是闰年。例如：1700,1800,1900和2100不是闰年，而1600,2000和2400是闰年。给定从公元2000年1月1日开始逝去的天数，你的任务是给出这一天是哪年哪月哪日星期几。输入数据输入包含若干行，每行包含一个正整数，表示从2000年1月1日开始逝去的天数。输入最后一行是−1,不必处理。可以假设结果的年份不会超过9999。输出要求对每个测试样例，输出一行，该行包含对应的日期和星期几。格式为“YYYY-MM-DDDayOfWeek”,其中“DayOfWeek”必须是下面中的一个：Sunday,Monday,Tuesday,Wednesday,Thursday,FridayandSaturday“。（1）确定某年的第一天是星期几？intday(intyear)//求某年的第一天是星期几{longa,b;if(year=2000){a=2000-year;b=6-(a+a/4-a/100+a/400)%7;returnb;}else{a=year-2000;b=(a+1+(a-1)/4-(a-1)/100+(a-1)/400)%7+6;returnb%7;}}（2）求出2000年1月1日是星期几Y=day(2000)（3）求从2000年1月1日开始逝去的天数days除以7的余数Z=days%7（4）求days是星期几x=(y+z)%7（5）利用字符数组输出下标x所对应的星期英文名（6）求days的年月日Year=2000month=1day=1利用循环while(days){days--;day++…}如果day达到某月的最后一天，day=1,month++如果month=12,day=31,则year++,month=1,day=1但要考虑闰年问题2、生理周期问题描述人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。输入数据输入四个整数：p,e,i和d。p,e,i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d是给定的时间，可能小于p,e,或i。所有给定时间是非负的并且小于365,所求的时间小于等于21252。输出要求从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。解题思路：假设从当年的第一天开始数，第x天三个高峰值同时出现，符合要求的x必须在[d+1,21252]之间，并且同时满足三个条件（1）(x-p)%23==0(2)(x-e)%28==0(3)(x-i)%33==0于是可以用三种方法解决问题。方法一slzq.c：（1）设置数组m表示三个周期的长度intm[3]={23,28,33}（2）设置数组a表示体力、情感和智力高峰出现的时间从键盘输入a（3）计算出三者高峰同时出现的时间ans=0;for(j=0;j3;j++){intt=M/m[j];ext_gcd(t,m[j]);ans=(ans+t*x*a[j])%M;}其中:M=m[0]*m[1]*m[2]t=M/m[i],i=0,1,2x由下面函数求出（4）设置全局变量x，yintx,y;voidext_gcd(inta,intb){intt;if(b==0){x=1;y=0;}else{ext_gcd(b,a%b);t=x;x=y;y=t-a/b*y;}}（5）调用ext_gcd(t,m[i]),求出x（6）ansd执行下面循环while(ans=d){ans+=M;}（7）ans-d为所求的结果(d为给定的时间，从键盘输入)方法二slzq1.c：a[0],a[1],a[2]分别代表p,e,i，表示体力、情感、智力出现最大值的时间m[0],m[1],m[2]分别表示三个的周长M=1;for(j=0;j3;j++)M*=m[j];for(j=d+1;j=M;j++)if((j-a[0])%m[0]==0)break;for(;j=M;j=j+m[0])if((j-a[1])%m[1]==0)break;for(;j=M;j=j+m[0]*m[1])if((j-a[2])%m[2]==0)方法三slzq2.cM=m[0]*m[1]*m[2];for(j=d+1;j=M;j++){x=(j-a[0])%m[0]==0;y=(j-a[1])%m[1]==0;z=(j-a[2])%m[2]==0;if(x&&y&&z)printf(“%d\n”,j-d);3、约瑟夫问题问题描述约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再从出圈的下一个开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。输入数据每行是用空格分开的两个整数，第一个是n,第二个是m(0m,n300)。最后一行是：00输出要求对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号（1）选用所用的解决问题的方法可以使用数组、循环链表、结构数组（2）用数组解决问题建立一个一维数组a,a[1]~a[n]存放n个人的编号，对n个人按1,2,…,m的顺序报数，报数为m的人保存到a[0]中，后面的人往前移动一个位置，报数的人数减1，再重复下去，最后a[1]中的值就是所求的值。s1=1;for(i=n;i=2;i--){s1=(s1+m-1)%i;if(s1==0)s1=i;w=a[s1];for(j=s1;ji;j++)a[j]=a[j+1];a[i]=w;（3）用循环链表解决问题将n个人的编号建立一个循环链表，通过报数，删除要离开的结点，当链表中剩下一个结点时，即为所求的值。（4）用结构数组解决问题structmonkey{intno;//猴子编号intnext;//下一个猴子编号};structmonkeylink[N];//n个猴子信息count=0;//出圈人数h=n;while(countn-1){i=0;while(i!=m){h=link[h].next;if(link[h].no)i++;}link[h].no=0;count++;//离开的猴子值为0，数目加1}最后结构中值不为0的即为所求的值。4、恺撒Caesar密码题目描述JuliusCaesar生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是Caesar军团中的一名军官，需要把Caesar发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F），其他字符不变，并且消息原文的所有字母都是大写的。密码字母：ABCDEFGHIJKLMNOPQRSTUVWXYZ原文字母：VWXYZABCDEFGHIJKLMNOPQRSTU输入数据最多不超过100个数据集组成。每个数据集由3部分组成：起始行：START密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息结束行：END在最后一个数据集之后，是另一行：ENDOFINPUT输出要求每个数据集对应一行，是Caesar的原始消息。（1）输入字符串密码（2）解密是字母，则key值减5，减5后若不是字母，加26#defineisletter(c)(((c)='a'&&(c)='z')||((c)='A'&&(c)='Z'))voidDenc(constchar*str,char*out,intkey){inti