算法与编程实践内容安排-6.doc

2011年6月短学期实验上机时间是6.24-7.5（周末除外）。每天为4学时，其中，7.5是2个学时。本次短学期的具体安排如下，评分事项见表格下方。班级地点时间教师#100811中心机房3176.24-7.5下午13:30-16:30（周末除外）陆宇#100812中心机房3176.24-7.5下午13:30-16:30（周末除外）朱芳#100813中心机房3216.24-7.5下午13:30-16:30（周末除外）应娜#100814中心机房3216.24-7.5下午13:30-16:30（周末除外）岳恒立#100815中心机房3216.24-7.5下午13:30-16:30（周末除外）吕秋云#100831中心机房3176.24-7.5上午8:00-11:00（周末除外）孙闽红#100851中心机房3176.24-7.5上午8:00-11:00（周末除外）周洋#100841中心机房3216.24-7.5上午8:00-11:00（周末除外）简志华#100842中心机房3216.24-7.5上午8:00-11:00（周末除外）沈雷评分规则是：l 要求学生每天到机房，特殊情况需要有书面说明，教师每次点名，到课成绩占10%。l 根据平常学生的问问题，编程情况及表现，给出平时分数，占10%。l 学生必须完成（1）编程实现”统计字母频率”、 “指示灯控制”、“进制转换”中2道。 （2）编程实现“鸽笼原理”、“大数运算”、“四则运算”、“约瑟夫问题” 、“数字游戏”、“寻找基数”中2道。按学生的实际编程能力打分，一般为5分制，鼓励学生自己编写的程序，这部分占70%。l 实验报告需要描述4道题目的设计思路，关键源代码，以及实验心得，报告必须在最后一天实验时上交，可以手写，可以打印，占10%。题1. 统计字母的使用频率一、题目：统计字母的使用频率二、目的与要求1 目的：通过编写程序统计字母的使用频率，培养学生综合利用C语言进行程序设计的能力，熟悉字符串的操作方法，加强函数的运用，提高软件系统分析能力和程序文档建立、归纳总结的能力。2 基本要求：1）要求用C语言编程，在Visual C+环境下调试完成；2）要求按照程序功能分成几个功能模块来实现，各个功能模块分别使用函数来完成；3）要求应用本课所讲授的程序设计语言知识来解决问题三、设计方法和基本原理1 课题功能描述本程序的功能，就是要统计英文字母的使用频率。2 问题详细描述为统计英文字母的使用频率，输入一个不包括空格的由英文字母组成的字符串，长度不超过200个字符。统计26个英文字母的使用频率，不区分大小写。最后按使用频率从大到小输出字母（小写字母）和使用频率（出现的次数）。3 问题的解决方案按照程序要求，本程序应采用模块化设计方法,设计几个功能模块。例如（仅供参考）：l 将字符串中的大写字母转换为小写字母l 统计输入的字符串中字母的使用频率l 按使用频率从大到小进行排序主函数中控制输入、函数调用和输出。四、主要技术问题的描述根据三的分析，主要问题在于：1) 为统计字母的使用频率，定义一个长度为26的int数组存放所统计的各个字母的使用频率。2) 在统计字母的使用频率时，不要使用if语句或switch语句，利用字母的ASCII码与数组元素下标之间的关系来求得。3) 按使用频率从大到小进行排序时，建议使用指针数组更为方便。五、创新要求实现程序功能后，可进行创新设计：1) 使用多文件，即主函数和各个函数分别存放在不同的.c文件中，在头文件中进行函数原型声明。2) 读入一篇英文文档，并对其进行字母频率分析。题2.指示灯控制问题描述： N盏灯排成一排，从1到N按顺序依次编号。有N个人也从1到N依次编号。第一个人（1号）将灯全部关闭。第二个人（2号）将凡是2和2的倍数的灯打开。第三个人（3号）将凡是3和3的倍数的灯做相反的处理（如果该灯为打开的，则将它关闭；如果该灯为关闭的，则将它打开）。以后的人都和3号一样，将凡是与自己编号相同的灯，以及是自己编号倍数的灯做相反处理。请编写程序实现。要求：程序中要显示每一个人所做工作的过程，例如：当第i个人操作时，则显示将i和i的倍数的灯做相反的处理过程；当第N个人操作之后，显示灯的最后状态。（建议：采用图形法，显示每一盏灯，并为每一盏灯加边框，用不同的颜色显示开灯或关灯）。 例如：当输入N为7时； 当第一个人操作时 则输出结果为： 第1盏灯是黑的 第2盏灯是黑的 第3盏灯是黑的 第4盏灯是黑的 第5盏灯是黑的 第6盏灯是黑的 第7盏灯是黑的 当第二个人操作时 则输出结果为： 第1盏灯是黑的 第2盏灯是亮的 第3盏灯是黑的 第4盏灯是亮的 第5盏灯是黑的 第6盏灯是亮的 第7盏灯是黑的 当第三个人操作时 则输出结果为： 第1盏灯是黑的 第2盏灯是亮的 第3盏灯是亮的 第4盏灯是亮的 第5盏灯是黑的 第6盏灯是黑的 第7盏灯是黑的 当第七个人操作时 则输出结果为： 第1盏灯是黑的 第2盏灯是亮的 第3盏灯是亮的 第4盏灯是黑的 第5盏灯是亮的 第6盏灯是亮的 第7盏灯是亮题3.进制转换课程设计任务书一、题目：自然数的进制转换二、目的与要求1 目的：通过编写对自然数进行不同进制转换程序，培养学生综合利用C语言进行程序设计的能力，熟悉字符串的操作方法，加强函数的运用，提高软件系统分析能力和程序文档建立、归纳总结的能力。2 基本要求：1）要求用C语言编程，在Visual C+环境下调试完成；2）要求按照程序功能分成几个功能模块来实现，各个功能模块分别使用函数来完成；3）要求应用本课所讲授的程序设计语言知识来解决问题.三、设计方法和基本原理1 课题功能描述本程序的功能，就是实现自然数的十进制、二进制、八进制、十六进制转换。即根据用户选择的进制和输入的数据，转换得到该数所对应的十进制、二进制、八进制和十六进制数。2 问题详细描述程序运行时，首先由用户选择输入数据所使用的进制，如：欢迎使用进制转换程序！ 1. 十进制 2. 二进制 3. 八进制 4. 十六进制 0. 退出请选择输入数据的进制：用户选择后，再输入数据，如选择3（八进制），则显示：请输入八进制数据：输入数据后，程序进行转换，最后输出该数所对应的十进制、二进制、八进制和十六进制数。如输出：转换结果： 十进制 21809 二进制 101010100110001 八进制 52461 十六进制 55313 问题的解决方案实际上，C语言在输入输出时可直接输入或输出各种进制的数，本题目是为了提高学生的编程能力，所以要自己编程来实现数制的转换。根据问题的描述，使用字符数组来存放输入的数据，转换后的数据也存放到字符数组中，按字符串进行输入和输出。注意：问题的解决方案有很多，下面给出的仅供同学们参考。按照程序要求，每次要将数据转换成各种进制，因此将输入数据（字符数组中）先转换成十进制数（long），再将其转换成各种进制并存入相应的字符数组中，最后输出。本程序应采用模块化设计方法,设计几个功能模块。例如（仅供参考）：l 检验输入数是否合法（例八进制数中只能出现07）l 将数据（字符数组中）转换成十进制数（long）l 将十进制数（long）转换成某种进制数据（字符数组中）还可以把这几个模块中都使用的字符与数字之间的转换作为独立模块，供上面的模块调用。例如（仅供参考）：l 字符转数字l 数字转字符主函数中控制输入、函数调用和输出。四、主要技术问题的描述根据三的分析，主要问题在于：1) 单个字符与数字的转换在字符转数字时，09只需减去0即可，要考虑到af和AF的转换（十六进制数）。同样的，数字转字符时，要考虑到1015的转换与09不同。2) 将数据（字符数组中）转换成十进制数（long）时，采用的算法是：按当前数制的位权进行多项式展开相加，即得到对应的十进制数。3) 将十进制数（long）转换成某种进制数据（字符数组中）时，采用除留余数法：将十进制数除以转换进制的位权，保留余数（存到字符数组中），商继续除，直到商为零；然后将字符数组中的内容求头逆序，即得到转换数据。其中求逆序也可用一个独立模块来实现。五、创新要求实现程序功能后，可进行创新设计：1) 使用多文件，即主函数和各个函数分别存放在不同的.c文件中，在头文件中进行函数原型声明；2) 本程序实现的是自然数的不同进制的转换，可进一步实现带小数的转换；3) 实现负数的转换题4.鸽笼原理一、题目：序列小游戏 二、目的与要求 1 目的： （1）让学生体会到鸽巢原理（或抽屉原理）的乐趣并使学生更加系统地理解和掌握C语言的函数间参数传递方法、数组和指针的应用等编程技巧。培养学生综合利用C语言进行科学计算，使学生将所学知识转化为分析和设计简单实际问题的能力，学会查资料和工具书。 （2）提高学生建立程序文档、归纳总结的能力。2 基本要求： （1）要求用C语言编程，在Visual C+环境下调试完成；（2）要求按照程序功能分成几个功能模块来实现，各个功能模块分别使用函数来完成；（3）要求应用本课所讲授的程序设计语言知识来解决问题. 三、设计方法和基本原理 1 课题功能描述 任意给定5个数字，其中必定存在3个数字已经有序（或者升序，或者降序），找出这5个数字中最长的升序或降序序列。 例如：1，7，5，3，9。则1，7，9，1，5，9，1，3，9都是最长的升序序列； 而7，5，3是最长的降序序列。 再如：1，3，2，5，7。最长的升序序列为1，3，5，7和1，2，5，7。 2 问题的解决方案： 自动生成各种可能的序列，对于5个数字所有可能的序列为： 0,1,2,3、0,1,2,4、0,1,3,4、0,2,3,4、1,2,3,4 0,1,2、0,1,3、0,2,3、1,2,3 0,1,4、0,2,4、1,2,4 1,3,4 2,3,4、0,3,4 考察各种可能的序列是否升序或是降序，若是则打印； 四、创新要求 在基本要求达到后，进行创新设计，10个数据，必定会有至少4个数据已经有序（或升序或降序），找出最长的升序或降序序列。题5. 大数运算题目：两个大数的加减乘除编程计算两个大整数（每个大数最多包含1000位数字）的加减乘除运算结果（除不尽时只给出商的整数部分）。输入：第一行包含了总的计算次数。接下来的每一行分别给出不同的两个大数。输出：输出结果中，对每一次计算都以Scenario #i:开始，其中的i是从1开始的第i次计算，紧接着按照“运算符:结果”的形式输出每种情况中两个数的加减乘除结果，对每一次计算都以一个空白行结束。输入样例：210000000000000 900000000000055 5样例输出Scenario #1：+:19000000000000-:1000000000000*:90000000000000000000000000/:1Scenario #2：+:60-:50*:275/:11题6. 四则运算一、题目：四则运算二、目的与要求1 目的：通过编写四则运算程序，培养学生综合利用C语言进行程序设计的能力，熟悉字符串的操作方法，加强函数的运用，提高软件系统分析能力和程序文档建立、归纳总结的能力。2 基本要求：1）要求用C语言编程，在Visual C+环境下调试完成；2）要求按照程序功能分成几个功能模块来实现，各个功能模块分别使用函数来完成；3）要求应用本课所讲授的程序设计语言知识来解决问题.三、设计方法和基本原理1 课题功能描述本程序的功能，就是实现数的加减乘除四则运算，如自动计算3+5*8的结果。2 问题详细描述程序运行时，首先提示用户输入四则运算表达式(表达式中最多有3个运算符，数据范围为1-100的整数)；输入结束后，程序自动进行计算并给出结果。如：输入13-10+5/8时输出3.625。3 问题的解决方案注意：问题的解决方案有很多，下面给出的仅供同学们参考。该问题主要注意四则运算的优先级问题：乘除运算比加减运算优先级高，同级运算按从左到右的顺序运算。本程序应采用模块化设计方法,设计几个功能模块。例如（仅供参考）：l 字符串解析函数（将输入字符串分解成数和运算符）l 将数据（字符数组中）转换成十进制数（long）l 判读是否存在高优先级运算符，若存在首先计算其运算结果并保存。l 同级运算按先后顺序进行。四、创新要求实现程序功能后，可进行创新设计：1) 使用多文件，即主函数和各个函数分别存放在不同的.c文件中，在头文件中进行函数原型声明；2) 在程序中增加自动出题功能及自动批卷功能3） 不限定运算符个数4） 允许括号运算的存在。题7. 约瑟夫问题基本要求 有1至 N编号的N 个人按顺时针方向围坐一圈，每人持有一个密码（正整数），一开始以正整数m作为报数上限值，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的报数上限值，从他的顺时针方向上的下一个人开始重新报数，如此下去，直至所有的人全部出列为止，要求产生记录出列顺序的表。如N = 7，每个人的密码依次是：3，1，7，2，4，8，4，m的值为20，则出列顺序为6，1，4，7，2，3，5。所有人用一个循环单链表表示，表中每个结点代表一个人，按出列次序依次将结点从循环单链表中删除，并按顺序存放在一个单链表中，链表的每个结点包括三个字段：code代表密码，no代表人的编号，link是指向下一个结点的指针。在主函数中，用堆分配的方法建立Josephus对象。循环展开对问题的求解。扩展：在n个人的Josephus问题中，如果事先知道每个人的密码，求处于哪个位置，获胜的概率最大？题8. 数字游戏玲玲喜欢通过玩数字游戏的方式来加深别人对她的印象。她最喜欢的一个数字游戏是让人给出一个数N，然后她会立即说出N的阶乘最末尾有多少个连续的零。很显然，这会让别人会对她印象深刻，因为，一般来说N!是一个非常大的数。例如，N为100时，100!会比地球上所有原子的数目还要大，但玲玲可以很快说出100!末尾有连续24个0。但是，她的一些朋友通常不是以10为进制的。这时，玲玲却不知道该怎么修改她的技巧来适应这些朋友了。问题：给出一个进制b和一个数n，计算当采用b进制时，n!末尾有多少个连续的0。例如，当b=2和n=5时，由于5!=120=1111000(2)，结果应该为3.输入：第一行包含了总的计算次数。接下来的每一行给出了不同情况下的问题中的两个数b(2 b 1 000)和n(1 n 1 000 000)，这两个数都是10进制的。输出：输出结果中，对每一次计算都以Scenario #i:开始，其中的i是从1开始的第i次计算。然后打印一行，输出：当采用b进制时，n!末尾有多少个连续的0（以十进制形式）。对每一次计算都以一个空白行结束。输入样例：3 2 5 10 100 45 10000 对样例的正确输出：Scenario #1: 3 Scenario #2: 24 Scenario #3: 2498 题9. 寻找基数问题描述： 同一个数会由于采用不同的基数而使得其表现的形式是完全不一样的，在我们的学习中，我们熟悉的基数有10进制、12进制、60进制、2进制、8进制和16进制。比如数据12，如果我们用2进制表示，则它就是1100；如果用3进制表示就是110；如果用8进制表示则是14。我们的编程