C语言实践6教案.docVIP

丽 水 学 院 教 案 课 程 名 称 ： C语言程序实践 课 程 代 码 ： 10座机电话号码 10座机电话号码 授课专业班级 ： 网091本、网092本 授 课 教 师 ： 应震 院 别 ： 计算机与信息学院 2010年 02月 28日 一、授课题目（教学章、节或主题） ACM入门—简单题 二、教学时间安排 上课2学时 上机实验8学时 三、教学目的、要求 了解和掌握ACM简单算法题的解题思路和解题过程。 四、教学重点和难点 重点：规律题、字符串、贪心和分治算法 难点：规律题、贪心和分治算法 五、教学方法及手段 教学方法课堂教学主要使用讲授法和演示法，再增加适量的讨论法。实验教学主要以演示法+实验法。教学手段以多媒体课件播放和示例程序演示。 六、教学过程设计 1．内容引入 ACM的题目会涉及到一些算法，如果不用算法则问题无法解决。 2．内容的组织 主要的内容框架：（六类简单算法） 数学题 规律题 排序题 字符串题 分治 贪心 每类算法主要讲解解题要点并通过例题加深对该类题目的认识。 详细的讲解内容： （1）数学题的解题思路 数学题主要是把问题理解清楚，特别是其中的数学关系。 特别大的数字主要看题目的内容会不会溢出。如果溢出可以用LONG 32位，不行再加个LONG 64位。在VC下不支持，在GC++中支持。 用浮点数也要考虑精度和输出的位数。 例题：鸡兔同笼 问题描述 一个笼子里面关了鸡和兔子（鸡有2 只脚，兔子有4 只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物？ 输入数据 第1 行是测试数据的组数n，后面跟着n 行输入。每组测试数据占1 行，包括一个正整数a a 32768 。 输出要求 n 行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2 个0。 输入样例 2 3 20 输出样例 0 0 5 10 解题思路 这个问题可以描述成任给一个整数 N，如果N 是奇数，输出0 0，否则如果N 是4 的倍数，输出N / 4 N / 2，如果N 不是4 的倍数，输出N/4+1 N/2。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了 参考程序 #include void main int nCases, i, nFeet; //nCases 表示输入测试数据的组数，nFeet 表示输入的脚数。 scanf %d, nCases ; for i 0; i nCases; i++ scanf %d, nFeet ; if nFeet %2 ! 0 // 如果有奇数只脚，则输入不正确， // 因为不论2 只还是4 只，都是偶数 printf 0 0\n ; else if nFeet%4 ! 0 //若要动物数目最少，使动物尽量有4 只脚 //若要动物数目最多，使动物尽量有2 只脚 printf %d %d\n, nFeet / 4 + 1, nFeet / 2 ; else printf %d %d\n, nFeet / 4, nFeet / 2 ; （2）规律题的解题思路 确定系统中的规律 可以通过查看输出结果的方式查找规律，有些题目可能要好几个数据后有规律。 一般1S的题目而且看起来可以用循环解决的要考虑规律 一般1S可以循环1000万次左右。 例题：数字序列 问题描述 一个数字序列由以下公式定义 f 0 7, f 1 11, f n f n - 1 + f n - 2 输入数据 测试用例由多行构成，每行由1个数字n， 2 n 1,000,000 . 注意数字很大。 输出要求 每个测试用例输出一行，如果f n 能被3整除则输出“YES”，否则输出“NO”。 输入样例 2 3 4 输出样例 YES NO NO 解题思路 本题如果直接用递归做肯定超时，只能去发现题目的规律。 先用递归程序求出n 2..20时值，值如下所示： 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 从上面的数字可以发现规律n 2，6，10，14，18能被3整除。知道规律后程序就非常简单了。 再计解省赛的五行题目，该题目的规则是N/2。 （3）排序的解题思路 选择适用的算法，注意问题规模 注意边界情况，排序结果的次序。? 一般的排序算法的时间复杂度为O（N2），比较好的排序算法时间复杂度为O（Nlog2N） 例题：DNA排序 问题描述 序列“未排序程度”的一个计算方式是元素乱序的元素对个数。