C++课程设计.docx

1、C+课程设计（一）算法分析用分治算法解平面最接近点对问题：一维的情形： S中的n个点为x轴上的n个实数x1,x2,.,xn。最接近点对即为这n个实数中相差最小的2个实数。我们可以先将x1,x2,.,xn排好序，然后，用一次线性扫描就可以找出最接近点对。对这种一维的简单情形，我们尝试用分治法来求解，并希望能推广到二维的情形。图1 一维情形的分治法假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1=xS|xm；S2=xS|xm。这样一来，对于所有pS1和qS2有pq。递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设=min|p1-p2|,|q1-q2|，S中的最接近点对

2、或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。如图1所示。我们注意到，如果S的最接近点对是p3,q3，即|p3-q3|，则p3和q3两者与m的距离不超过，即|p3-m|，|q3-m|m。从而使S1和S2分别位于直线l的左侧和右侧，且S=S1S2 。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离1和2。现设=min(1,2)。若S的最接近点对(p,q)之间的距离d(p,q)则p和q必分属于S1和S2。不妨设pS1，qS2。那么p和q距直线l的距离均小于。因此，我们若用P

3、1和P2分别表示直线l的左边和右边的宽为的2个垂直长条，则pS1，qS2，如图2所示。图2 距直线l的距离小于的所有点在一维的情形，距分割点距离为的2个区间(m-,m(m,m+中最多各有S中一个点。因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些，此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这n2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者，则必有d(p,q)。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个

4、2的矩形R中，如图3所示。图3 包含点q的2的矩形R由的意义可知P2中任何2个S中的点的距离都不小于。由此可以推出矩形R中最多只有6个S中的点。事实上，我们可以将矩形R的长为2的边3等分，将它的长为的边2等分，由此导出6个（/2）（2/3）的矩形。如图4(a)所示。图4 矩形R中点的稀疏性若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个2的小矩形中有2个以上S中的点。设u,v是这样2个点，它们位于同一小矩形中，则因此d(u,v)5/6 。这与的意义相矛盾。也就是说矩形R中最多只有6个S中的点。图4(b)是矩形R中含有S中的6个点的极端情形。由于这种稀疏性质，对于P1中任一点p，P2中最

5、多只有6个点与它构成最接近点对的候选者。因此，在分治法的合并步骤中，我们最多只需要检查6n/2=3n对候选者，而不是n2/4对候选者。我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点，但是我们并不确切地知道要检查哪6个点。为了解决这个问题，我们可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S的点按其y坐标排好序，则对P1中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P1

6、中每一点最多只要检查P2中排好序的相继6个点。（二）程序代码学生成绩系统的原代码#include#include#include#include using namespace std;#define T 2 /T代表两个学期#define C 4 /C代表四个班级#define P 30 /P代表每个班级最多为30人#define S 5 /S代表学生的5门课程int N=0; /定义N为一个全局变量，用来储存实际从键盘输入的班级人数class Stu /定义一个Stu类private: string termT,clasTC,nameTCP; int scoreTCPS,totalTCP,

7、averageTCP,peopleTC;public: void setsco(); /用来完成按学期，按班级对学生成绩的录入 void mendsco(); /用来完成按学期，按班级对学生成绩的修改 void add(int n,int m); /用来完成对某个班级进行增加学生的成绩 void reduce(int n,int m);/用来完成对某个班级进行减少学生 void mend(int n,int m);/用来完成对学生成绩的修改 void tongji();/用来完成统计学生的总分和平均分，并按平均分对学生进行排序 void find();/用来完成对学生成绩的查找，以及不及格科目

8、和学生名单 void print();/用来完成按班级输入成绩 void save();/用来保存学生的成绩;void Stu:setsco() int i,j,k,l=0; for(i=0;iT;i+) couttermi;/输入学期 for(j=0;jC;j+) coutclasij;/输入班级 coutN; peopleij=N; cout请输入这个班级N个同学的姓名和成绩:endl; for(k=0;kN;k+) coutnameijk;/输入学生的姓名 coutscoreijkl+;/输入学生的分数 coutscoreijkl+; coutscoreijkl+; coutscorei

9、jkl+; coutscoreijkl+; l=0; void Stu:mendsco() int i,j,choice=1; coutsetw(30)1:term0endl;/输出学期供选择 coutsetw(30)2:term1endl; couti; coutsetw(30)1:clasi-10endl;/输出班级供选择 coutsetw(30)2:clasi-11endl; coutsetw(30)3:clasi-12endl; coutsetw(30)4:clasi-13endl; coutj; while(choice) coutsetw(30)1:添加人数endl; coutse

10、tw(30)2:减少人数endl; coutsetw(36)3:修改学生的成绩endl; coutsetw(30)0:回主菜单endl; coutchoice; switch(choice) case 1:add(i-1,j-1);break;/调用add(int n,int m)函数 case 2:reduce(i-1,j-1);break;/调用reduce(int n,int m)函数 case 3:mend(i-1,j-1);break;/调用mend(int n,int m)函数 case 0:break; default:cout错了,请重新输入一个数据(0-3):;break;

11、void Stu:add(int n,int m) int i,l=0,number,temp;/number用来储存需要添加的人数 coutnumber; temp=peoplenm; peoplenm=peoplenm+number;/该班的人数加上number cout请输入这number个学生的名字和成绩:endl; for(i=temp;ipeoplenm;i+) coutnamenmi;/输入学生的姓名 coutscorenmil+; coutscorenmil+; coutscorenmil+; coutscorenmil+; coutscorenmil+; l=0; void

12、Stu:reduce(int n,int m) int i,j,k,number,l=0,flag1,flag2=0;/number为需要减少的人数 string flag;/flag用来储存从键盘输入的学生的名字 coutnumber; cout请输入这number个学生的姓名:endl; for(i=0;inumber;i+) flag1=0; flag2=peoplenm; cout请输入第i+1flag; for(j=0;jpeoplenm;j+) if(namenmj=flag) for(k=j;kpeoplenm-1;k+) namenmk=namenmk+1;/把后面学生的名字递

13、补到前面来 scorenmkl=scorenmk+1l; l+; scorenmkl=scorenmk+1l; l+; scorenmkl=scorenmk+1l; l+; scorenmkl=scorenmk+1l; l+; scorenmkl=scorenmk+1l; l+; l=0; peoplenm-;/执行完上面的内容后，该班的人数减一 else flag1+; if(flag1=flag2) cout这个学生不存在,请重新输入!endl; i-; void Stu:mend(int n,int m) int i,j=0,l; string flag;/用来储存学生的姓名 coutf

14、lag;/从键盘输入学生的姓名 for(i=0;ipeoplenm;i+) l=0; if(namenmi=flag) cout该学生的成绩如下endl;/输出学生的原来的成绩 cout汇编语言:; coutscorenmil+endl; cout离散数学:; coutscorenmil+endl; cout数字逻辑:; coutscorenmil+endl; cout+语言:; coutscorenmil+endl; cout大学英语:; coutscorenmil+endl; l=0; cout现在请输入该生现在的新成绩:endl; coutscorenmil+; coutscorenmi

15、l+; coutscorenmil+; coutscorenmil+; coutscorenmil+; else j+; if(j=peoplenm) cout该学生不存在，请下次再重新输入!; void Stu:tongji() int i,j,k,l,m,n,flag=0; string flag1; coutsetw(30)1:term0endl;/输出学期供选择 coutsetw(30)2:term1endl; couti; coutsetw(30)1:clasi-10endl;/输出班级供选择 coutsetw(30)2:clasi-11endl; coutsetw(30)3:cla

16、si-12endl; coutsetw(30)4:clasi-13endl; coutj; i-; j-; for(k=0;kpeopleij;k+) for(l=0;lS;l+) totalijk+=scoreijkl; averageijk=totalijk/S; coutsetw(30)termiclasij成绩单endl; cout姓名setw(10)汇编语言setw(11)离散数学setw(11)数字逻辑setw(11)+语言setw(11)大学英语setw(8)总分setw(8)平均分setw(6)排名endl; for(m=0;mpeopleij-1;m+) for(n=0;na

17、verageijn+1) swap(averageijn,averageijn+1); swap(nameijn,nameijn+1); for(l=0;lS;l+) swap(scoreijnl,scoreijn+1l); for(k=0;kpeopleij;k+) coutnameijk; for(l=0;lS;l+) coutsetw(10)scoreijkl; coutsetw(10)totalijksetw(10)averageijksetw(6)+flagendl; void Stu:find() int i,j=0,l,m,n,flag1,flag2=0; string flag

18、; coutsetw(30)1:term0endl;/输出学期供选择 coutsetw(30)2:term1endl; coutn; coutsetw(30)1:clasn-10endl;/输出班级供选择 coutsetw(30)2:clasn-11endl; coutsetw(30)3:clasn-12endl; coutsetw(30)4:clasn-13endl; coutm; n-; m-; coutflag; /从键盘输入需要查找学生的姓名 for(i=0;ipeoplenm;i+) l=0; if(namenmi=flag) cout该学生的成绩如下endl; cout汇编语言:;

19、 coutscorenmil+endl; cout离散数学:; coutscorenmil+endl; cout数字逻辑:; coutscorenmil+endl; cout+语言:; coutscorenmil+endl; cout大学英语:; coutscorenmil+endl; else j+; /如果找不到该学生，J就加一 l=0; if(j=peoplenm) cout该学生不存在，请下次再重新输入!endlendl; cout不及格的情况如下:endl; for(i=0;ipeoplenm;i+) flag1=0; if(scorenmil60) cout汇编语言:scorenm

20、ilendl; flag1+; l+; if(scorenmil60) cout离散数学:scorenmilendl; flag1+; l+; if(scorenmil60) cout数字逻辑:scorenmilendl; flag1+; l+; if(scorenmil60) cout+语言:scorenmilendl; flag1+; l+; if(scorenmil60) cout大学英语:scorenmilendl; flag1+; l=0; if(flag1) cout以上为namenmi同学不及格的科目.endl; else flag2+; if(!flag2) cout该班没有不

21、及格的人.endl;void Stu:save() int i,j,k,l,m; ofstream out(成绩系统.txt);/学生的成绩将保存在成绩系统.txt中 for(i=0;iT;i+) outsetw(40)termiendl;/将学期进行保存 for(j=0;jC;j+) outsetw(40)clasijendl;/对班级进行保存 out姓名setw(14)汇编语言setw(14)离散数学setw(14)数字逻辑setw(14)+语言setw(14)大学英语endl; for(l=0;lpeopleij;l+) m=0; outnameijl;/对学生的姓名进行保存 for(k=0,m=10;kS;k+) outsetw(m)scoreijlk; m=m+2;/对学生的成绩进行保存 outendl; outendl; cout学生的成绩已经成功地保存了!endl;void Stu:print() int i,j,k,l; coutsetw(30)1:term0endl;/输出学期供选择 coutsetw(30)2:term1endl;