目 录
摘 要 ........................................................... 3 一． 求素数问题 .................................................. 4 1.1 问题描述 ................................................... 4 1.2采用类语言定义相关的数据类型 ................................ 4 1.3算法设计 .................................................... 4 1.4函数的调用关系图 ............................................ 4 1.5调试分析 .................................................... 5 1.6测试结果 .................................................... 5 1.7源程序（带注释） ............................................ 7 二、数据删除问题 ................................................. 8 2.1 问题描述 ................................................... 8 2.2算法设计 .................................................... 8 2.3程序调试情况： ............................................. 10 2.4源程序 ..................................................... 10 三、通过课程选修问题 ............................................ 11 3.1数据结构设计 ............................................... 11 3.2算法设计 ................................................... 12 3.3调试分析 ................................................... 14 3.4测试结果 ................................................... 14 3.5源程序（带注释） ........................................... 15 四、排序重构问题 ................................................ 25 4.1问题说明 ................................................... 25 4.2数据结构设计 ............................................... 26 4.3算法设计 ................................................... 26 4.4流程图如下： ............................................... 27 4.5调试分析 ................................................... 27
4.6测试结果 ................................................... 27 4.7 源程序（带注释） .......................................... 28 总 结 .......................................................... 32 参考文献 ........................................................ 33 致 谢 .......................................................... 34
摘 要
第一个程序为求解素数问题在求解过程中运用埃拉托色尼筛法求所有小于N的素数的方法。从建立一个整数2~N的线性表寻找i?错误！未找到引用源。的整数 第二个程序为求解数据删除问题，编写删除具有N个数据项的数组A中所有重复项的程序，返回A中仍有的数据项。对于设计程序的思路，可以从数据类型入手，如果是整型（也包括但字符），可以使用排序法，然后，输出的重复的就删去，如果是正整数，可以直接构造一个数组：int a[]={0};//全部初始化为0，然后一个一个地读入，假设读入n，则令a[n]=1表示n存在，那么下一个读入的n则与a[n]判断，如果a[n]是1，则跳过。输出时，只需要挨个判断a[]中的a[n]了，如果是1，输出n。
课程选修问题。学生需要修一定数量的课程才能毕业，而这些课程会有一些必须遵循的选修顺序。假设每个学期都开所有课程，并且学生所修课程数量不限制。给出课程和先修课程的列表，求出一个满足最小学期数要求的时间表。以你的专业情况为背景设计。
第四道为排序重构问题。具体要求是由题目给出的一个顺序序列按照题目给定的相关计算方法得到新的序列，然后对计算方法进行逆推得到新的顺序序列，由于计算方法我们得到的序列并不唯一。
关键词： 素数 数据删除 排序重构 埃拉托色尼筛法 选修顺序
3
一． 求素数问题
1.1 问题描述
埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手，寻找i?错误！未找到引用源。的整数，编程实现此算法，并讨论运算时间。
1.2采用类语言定义相关的数据类型
定义一个线性表顺序存储结构，用来求所有小于N的素数 typedef int DataType;//数据类型 typedef struct{
DataType data[maxsize]; 定义一个一维数组 int length;//线性表中实际元素的个数 }Seqlist;
1.3算法设计
用一个循环结构判断是否为素数，如果是素数则返回1，否则返回0。 int sushu(DataType &i) { int m; if(i==1) return 0; for(m=2;m if(i%m==0) return 0; }return 1；} 1.4函数的调用关系图 4 主函数 sushu 图1.1调用关系图 1.5调试分析 1 当m的值大于maxsize的值是发生越界问题，在输入m时要确保m的值要小于maxsize的值。开始界面如图所示。 图1.2开始界面 2 算法的时间复杂度O(L.length-1)+O(m)。 1.6测试结果 1 图1为输出2~200内的数 图1.3 2~200内所有的数 5