目录
摘 要
利用C/C++的基础知识，用面向对象程序设计的基本思路和各种算法与数据结构解决求素数问题，方程求解问题，最短字符串问题和模拟扫雷问题。通过设计巧妙的算法在dos环境下解决了相应的问题，并进行算法的复杂度分析，以对算法进行比较和改良，从而加深对课本知识的理解和动手编程的能力。
关键词：C++，算法，数组，数据结构。
1.求素数问题
埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手，寻找i˂ 的整数，编程实现此算法，并讨论运算时间。
1.1 数据结构
考虑到不需要进行频繁的删除和插入操作，所以可以采用顺序表或者数组来储存1—N的数字，本程序采用顺序表来存储操作过程中要用到的一些数据。
typedef struct Node
{int data;
int flag;
struct Node *Link;
}Node,*LinkList;
1.2 算法设计
埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。
（1）先把1删除（现今数学界1既不是素数也不是合数）。 正在上传…重新上传取消
（2）读取队列中当前最小的数2，然后把2的倍数删去。
（3）读取队列中当前最小的数3，然后把3的倍数删去。
（4）读取队列中当前最小的数5，然后把5的倍数删去。
（5）如上所述直到需求的范围内所有的数均删除或读取。
//建立一个整数2~N的线性表
//建立一个整数2~N的线性表
SeqList InList(SeqList L,int m)
{
SeqList X=L;
int i,j;
X.length=0;
if((m < 2)||(m > MaxSize))
{
printf("error!\n");
}
else
{
for(i=2,j=0;i<m;i++,j++)
{
X.data[j]=i;
X.length++;
}
return X;
}
}
//判断素数
SeqList JudgePrimeNumber(SeqList L,SeqList Q,int m)
{
int i,j,l=0,a=0,b=0;
double n;
for(i = 2;i < m;i++)
{
n = sqrt(L.data[l++]);
for(j = 2;j <= n;j++)
{
if(i % j == 0)
break;
}
if(j > n)
{
Q.data[a++]=i;
Q.length++;
}
}
return Q;
}
1.3 函数调用关系图
1.4 调试分析
1.5 测试结果
1.6源程序（带注释）
求素数问题
/*埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。
从建立一个整数2~N的表着手，寻找i<sqrt(N)的整数，编程实现此算法，并讨论运算时间。*/
#include<stdio.h>
#include<math.h>
#define MaxSize 100
#include<stdlib.h>
//构建线性表
typedef struct
{
int data[MaxSize];
int length;
}SeqList;
SeqList L,Q;
//建立一个整数2~N的线性表
SeqList InList(SeqList L,int m)
{
SeqList X=L;
int i,j;
X.length=0;
if((m < 2)||(m > MaxSize))
{
printf("error!\n");
}
else
{
for(i=2,j=0;i<m;i++,j++)
{
X.data[j]=i;
X.length++;
}
return X;
}
}
//判断素数
SeqList JudgePrimeNumber(SeqList L,SeqList Q,int m)
{
int i,j,l=0,a=0,b=0;
double n;
for(i = 2;i < m;i++)
{
n = sqrt(L.data[l++]);
for(j = 2;j <= n;j++)
{
if(i % j == 0)
break;
}
if(j > n)
{
Q.data[a++]=i;
Q.length++;
}
}
return Q;
}
//主函数
int main(void)
{
int i,N;
printf("N=");
scanf("%d",&N);
L=InList(L,N);
L=JudgePrimeNumber(L,Q,N);
for(i=0;i<L.length;i++)
{
printf("%d,",L.data[i]);
}
printf("\n");
system("pause");
}
//运算时间O(n^2)
2.方程求解问题
方程A5+B5+C5+D5+E5=F5刚好有一个满足0≤A≤B≤C≤D≤E≤F≤75的整数解。请编写一个求出该解的程序。
2.1 数据结构
int a,b,c,d,e,f;
2.2 算法设计
方程A5+B5+C5+D5+E5=F5刚好有一个满足0≤A≤B≤C≤D≤E≤F≤75的整数解。由题意可知可以设置六个循环，第一个循环F的范围在0—75，第二个循环E的范围在0—F，第三个循环D的范围在0—E，第四个循环C的范围在0—D,第五个循环B的范围在0—C，第六个循环A的范围在0—B。在设置判断成功的条件为A5+B5+C5+D5+E5=F5，即可顺利解决问题。
void calculate()
{
int a,b,c,d,e,f;
double result,temp;
for(a=0;a<=75;a++)
{
for(b=a;b<=75;b++)
{
for(c=b;c<=75;c++)
{
for(d=c;d<=75;d++)
{
for(e=d;e<=75;e++)
{
result=L.data[a]+L.data[b]+L.data[c]+L.data[d]+L.data[e];
for(f=e;f<=75;f++)
{
temp=L.data[f];
if(temp==result&&a!=0)
{
printf("A=%d B=%d C=%d D=%d E=%d F=%d\n",a,b,c,d,e,f);
}
}
}
}
}
}
}
}
2.3 函数调用关系
2.4 调试分析
2.5 测试结果
2.6 源程序（带注释）
方程求解问题
#include<stdio.h>
#include<math.h>
#define MaxSize 100
#include<stdlib.h>
//构建线性表
typedef struct
{
double data[MaxSize];
int length;
}SeqList;
SeqList L;
//建立一个0~75的5次方的线性表
void InList()
{
int i;
L.length=0;
for(i=0;i<=75;i++)
{
L.data[i]=pow(i,5);
L.length++;
}
}
void calculate()
{
int a,b,c,d,e,f;
double result,temp;
for(a=0;a<=75;a++)
{
for(b=a;b<=75;b++)
{
for(c=b;c<=75;c++)
{
for(d=c;d<=75;d++)
{
for(e=d;e<=75;e++)
{
result=L.data[a]+L.data[b]+L.data[c]+L.data[d]+L.data[e];
for(f=e;f<=75;f++)
{
temp=L.data[f];
if(temp==result&&a!=0)
{
printf("A=%d B=%d C=%d D=%d E=%d F=%d\n",a,b,c,d,e,f);
}
}
}
}
}
}
}
}
int main(void)
{
int i;
InList();
calculate();
system("pause");
return 0;
}
3.最短字符串问题
编写一个程序，从输入中读取字符串，并按长度顺序，最短字符串优先的原则输出它们。如果有若干字符串具有相同的长度，就按字母顺序输出它们。
3.1 数据结构
char A[100][100],B[100];
int i,j,k,N;
3.2 算法设计
解决字符串问题可以从字符串函数入手，字符串函数包含在头文件为“string.h”的文件中。输入的字符串可以保存在二维数组中，比较字符串的长短可以调用strlen（）函数，对于长度相同的字符串，可以用strcmp（）函数进行比较。用循环比较完字符串后在保存进数组，在利用循环进行输出就可以解决问题了
void main()
{
char A[100][100],B[100];
int i,j,k,N;
printf("输入字符串的个数\n");
scanf("%d",&N);
printf("输入字符串数组，输入一个后按Enter再输入：\n");
for(i=0;i<N;i++)
scanf("%s",&A[i]);
printf("输入的源字符串组:\n");
for(i=0;i<N;i++)
printf("%s\n",A[i]);
for(i=0;i<N-1;i++)
for(j=i+1;j<N;j++)
{
if(strlen(A[i])>strlen(A[j]))
{
strcpy(B,A[i]);
strcpy(A[i],A[j]);
strcpy(A[j],B);
} //如果字符串aa[i]的长度大于aa[j]的长度，交换输出
if(strlen(A[i])==strlen(A[j]))
{ //比较字符串中字母的顺序
for(k=0;k<strlen(A[i]);k++)
{
if(A[i][k]<A[j][k])
break;
if(A[i][k]>A[j][k])
{
strcpy(B,A[i]);
strcpy(A[i],A[j]);
strcpy(A[j],B);
break;
}
}
} //如果字符串长度相等，按字母顺序输出
}
printf("输出处理后的字符串数组:\n");
for(i=0;i<N;i++)
printf("%s\n",A[i]);
system("pause");
}3.3 函数调用关系
3.4 调试分析
3.5测试结果
3.6 源程序（带注释）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void main()
{
char A[100][100],B[100];
int i,j,k,N;
printf("输入字符串的个数\n");
scanf("%d",&N);
printf("输入字符串数组，输入一个后按Enter再输入：\n");
for(i=0;i<N;i++)
scanf("%s",&A[i]);
printf("输入的源字符串组:\n");
for(i=0;i<N;i++)
printf("%s\n",A[i]);
for(i=0;i<N-1;i++)
for(j=i+1;j<N;j++)
{
if(strlen(A[i])>strlen(A[j]))
{
strcpy(B,A[i]);
strcpy(A[i],A[j]);
strcpy(A[j],B);
} //如果字符串aa[i]的长度大于aa[j]的长度，交换输出
if(strlen(A[i])==strlen(A[j]))
{ //比较字符串中字母的顺序
for(k=0;k<strlen(A[i]);k++)
{
if(A[i][k]<A[j][k])
break;
if(A[i][k]>A[j][k])
{
strcpy(B,A[i]);
strcpy(A[i],A[j]);
strcpy(A[j],B);
break;
}
}
} //如果字符串长度相等，按字母顺序输出
}
printf("输出处理后的字符串数组:\n");
for(i=0;i<N;i++)
printf("%s\n",A[i]);
system("pause");
}
4. 扫雷问题
有些个人计算机会带有一个名为Minesweeper的游戏。该游戏界面是一个网格，网格中的有些方块是雷。编写一个程序以读取文件，该文件中存放着网格中的行数、列数以及网格本身。网格会含有一些标记为o的方块，这些就是雷。其他方块不是雷，将会标记上问号（？）。程序的输出就是输出这个网格。雷依然会标记成o，而那些不含雷的方块会替换成一个数字，以表明邻近雷的个数。最大数字将是8。
4.1 数据结构
int a[10][10]; //定义数组存放文件里的数据
int i,j;
4.2算法设计
编写一个程序以读取文件，该文件中存放着网格中的行数、列数以及网格本身。网格会含有一些标记为o的方块，这些就是雷。其他方块不是雷，将会标记上问号（？）。程序的输出就是输出这个网格。雷依然会标记成o，而那些不含雷的方块会替换成一个数字，以表明邻近雷的个数。最大数字将是8。在编程中我们用二维数组来表示网格，由于雷的数目最大为8。所以我们可以用9来表示雷。通过计算不是9的位置周围的“雷”的个数来给出提示数目。
void ReadIn() //设置网格函数
{int a[10][10]; //定义数组存放文件里的数据
int i,j;
ofstream ofile; //定义文件输出流对象
ofile.open("D:/data",ios::out); //文件以输出方式打开(内存数据输出到文件)
for(int c=1;c<101;c++)
{
ofile<<0<<" ";
if(c%10==0)
ofile<<endl;
}
ofile.close();
ifstream infile; //定义文件输入流对象
infile.open("D:/data",ios::in); //文件以输入方式打开(文件数据输入到内存)
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
infile>>a[i][j]; //把文件数据存到二维数组
}
infile.close();
int c=0;
for(i=0;i<10;i++) //网格输出到屏幕
for(j=0;j<10;j++)
{cout<<a[i][j]<<" ";
c++;
if(c%10==0)
cout<<endl;}
}
void SetMine(int flag) //设置地雷位置函数
{int i,j,count;
int c=0;
int a[10][10];
if(flag==1)
count=20;
if(flag==2)
count=40;
if(flag==3)
count=80;
ifstream infile; //文件输出
infile.open("D:/data",ios::in);
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
infile>>a[i][j]; //把文件数据存到二维数组
}
infile.close();
for(int n=1;n<=count;n++) //随即产生雷的位置
{i=rand()%10; //rand()函数用来产生随机数
j=rand()%10;
while(a[i][j]==9)
{i=rand()%10;
j=rand()%10;
}
a[i][j]=9;
}
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{cout<<a[i][j]<<" "; //输出到屏幕
c++;
if(c%10==0)
cout<<endl; }
c=0;
ofstream ofile; //文件输入
ofile.open("D:/data1",ios::out);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{ofile<<a[i][j]<<" "; //将二维数组的值写到文件里
c++;
if(c%10==0)
ofile<<endl;}
ofile.close();
}
void SetPoint() //设置提示
{int i,j,c=0;
int a[10][10];
ifstream infile; //文件输出
infile.open("D:/data1",ios::in);
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
infile>>a[i][j]; //把文件数据存到二维数组
}
infile.close();
if(a[0][0]!=9) //设置四个顶点的提示
a[0][0]=(a[0][1]+a[1][0]+a[1][1])/9;
if(a[0][9]!=9)
a[0][9]=(a[0][8]+a[1][8]+a[1][9])/9;
if(a[9][0]!=9)
a[9][0]=(a[8][0]+a[8][1]+a[9][1])/9;
if(a[9][9]!=9)
a[9][9]=(a[8][8]+a[8][9]+a[9][8])/9;
for(j=1;j<9;j++) //设置除顶点的四条边
{
if(a[i][j]!=9)
a[0][j]=(a[0][j+1]+a[0][j-1]+a[1][j]+a[1][j+1]+a[1][j-1])/9;
if(a[i][j]!=9)
a[9][j]=(a[8][j]+a[8][j-1]+a[8][j+1]+a[9][j+1]+a[9][j-1])/9;
}
for(i=1;i<9;i++)
{
if(a[i][j]!=9)
a[i][0]=(a[i+1][0]+a[i-1][0]+a[i][1]+a[i-1][1]+a[i+1][1])/9;
if(a[i][j]!=9)
a[i][9]=(a[i-1][9]+a[i+1][9]+a[i+1][8]+a[i][8]+a[i-1][8])/9;
}
for(i=1;i<9;i++)
for(j=1;j<9;j++)
{
if(a[i][j]!=9)//设置内部的点
{
if(a[i][j-1]==9)
a[i][j]++;
if(a[i][j+1]==9)
a[i][j]++;
if(a[i-1][j]==9)
a[i][j]++;
if(a[i-1][j+1]==9)
a[i][j]++;
if(a[i-1][j-1]==9)
a[i][j]++;
if(a[i+1][j]==9)
a[i][j]++;
if(a[i+1][j+1]==9)
a[i][j]++;
if(a[i+1][j-1]==9)
a[i][j]++;
}
}
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{if(a[i][j]==9)
a[i][j]=0;
cout<<a[i][j]<<" ";
c++;
if(c%10==0)
cout<<endl;}
c=0;
ofstream ofile; //文件输入
ofile.open("D:/data2",ios::out);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{if(a[i][j]==9)
a[i][j]=0;
ofile<<a[i][j]<<" ";
c++;
if(c%10==0)
ofile<<endl;}
ofile.close();
}
4.3函数调用关系
4.4 调试分析
4.5 测试结果
4.6 源程序(带注释)
扫雷问题
#include<iostream>
#include<fstream>
#include<stdlib.h>
using namespace std;
void ReadIn() //设置网格函数
{int a[10][10]; //定义数组存放文件里的数据
int i,j;
ofstream ofile; //定义文件输出流对象
ofile.open("D:/data",ios::out); //文件以输出方式打开(内存数据输出到文件)
for(int c=1;c<101;c++)
{
ofile<<0<<" ";
if(c%10==0)
ofile<<endl;
}
ofile.close();
ifstream infile; //定义文件输入流对象
infile.open("D:/data",ios::in); //文件以输入方式打开(文件数据输入到内存)
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
infile>>a[i][j]; //把文件数据存到二维数组
}
infile.close();
int c=0;
for(i=0;i<10;i++) //网格输出到屏幕
for(j=0;j<10;j++)
{cout<<a[i][j]<<" ";
c++;
if(c%10==0)
cout<<endl;}
}
void SetMine(int flag) //设置地雷位置函数
{int i,j,count;
int c=0;
int a[10][10];
if(flag==1)
count=20;
if(flag==2)
count=40;
if(flag==3)
count=80;
ifstream infile; //文件输出
infile.open("D:/data",ios::in);
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
infile>>a[i][j]; //把文件数据存到二维数组
}
infile.close();
for(int n=1;n<=count;n++) //随即产生雷的位置
{i=rand()%10; //rand()函数用来产生随机数
j=rand()%10;
while(a[i][j]==9)
{i=rand()%10;
j=rand()%10;
}
a[i][j]=9;
}
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{cout<<a[i][j]<<" "; //输出到屏幕
c++;
if(c%10==0)
cout<<endl; }
c=0;
ofstream ofile; //文件输入
ofile.open("D:/data1",ios::out);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{ofile<<a[i][j]<<" "; //将二维数组的值写到文件里
c++;
if(c%10==0)
ofile<<endl;}
ofile.close();
}
void SetPoint() //设置提示
{int i,j,c=0;
int a[10][10];
ifstream infile; //文件输出
infile.open("D:/data1",ios::in);
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
infile>>a[i][j]; //把文件数据存到二维数组
}
infile.close();
if(a[0][0]!=9) //设置四个顶点的提示
a[0][0]=(a[0][1]+a[1][0]+a[1][1])/9;
if(a[0][9]!=9)
a[0][9]=(a[0][8]+a[1][8]+a[1][9])/9;
if(a[9][0]!=9)
a[9][0]=(a[8][0]+a[8][1]+a[9][1])/9;
if(a[9][9]!=9)
a[9][9]=(a[8][8]+a[8][9]+a[9][8])/9;
for(j=1;j<9;j++) //设置除顶点的四条边
{
if(a[i][j]!=9)
a[0][j]=(a[0][j+1]+a[0][j-1]+a[1][j]+a[1][j+1]+a[1][j-1])/9;
if(a[i][j]!=9)
a[9][j]=(a[8][j]+a[8][j-1]+a[8][j+1]+a[9][j+1]+a[9][j-1])/9;
}
for(i=1;i<9;i++)
{
if(a[i][j]!=9)
a[i][0]=(a[i+1][0]+a[i-1][0]+a[i][1]+a[i-1][1]+a[i+1][1])/9;
if(a[i][j]!=9)
a[i][9]=(a[i-1][9]+a[i+1][9]+a[i+1][8]+a[i][8]+a[i-1][8])/9;
}
for(i=1;i<9;i++)
for(j=1;j<9;j++)
{
if(a[i][j]!=9)//设置内部的点
{
if(a[i][j-1]==9)
a[i][j]++;
if(a[i][j+1]==9)
a[i][j]++;
if(a[i-1][j]==9)
a[i][j]++;
if(a[i-1][j+1]==9)
a[i][j]++;
if(a[i-1][j-1]==9)
a[i][j]++;
if(a[i+1][j]==9)
a[i][j]++;
if(a[i+1][j+1]==9)
a[i][j]++;
if(a[i+1][j-1]==9)
a[i][j]++;
}
}
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{if(a[i][j]==9)
a[i][j]=0;
cout<<a[i][j]<<" ";
c++;
if(c%10==0)
cout<<endl;}
c=0;
ofstream ofile; //文件输入
ofile.open("D:/data2",ios::out);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{if(a[i][j]==9)
a[i][j]=0;
ofile<<a[i][j]<<" ";
c++;
if(c%10==0)
ofile<<endl;}
ofile.close();
}
int main()
{
cout<<"------布雷前-----"<<endl;
ReadIn();
cout<<"------布雷位置-----"<<endl;
SetMine(2);
cout<<"------输出网格----"<<endl;
SetPoint();
system("pause");
return 0;}
总结
经过本次课程设计，发现做软件真的需要做很多工作，不仅仅是敲代码。
首先，必须要有需求分析。就拿这次的题目来说，一个清晰的需求分析能让我省去很多工作，能让我把代码写的更清晰，让我的代码能有更好的重用性，以此简化程序。而这次的题目其实也算不上需求分析，只能算是功能分析吧。从界面到用户登陆判断，从增删改查基本功能到文件读写。如果能够把代码细化，把基本功能都封装成函数，这样应该会提高代码的重用性。
其次，有了清晰的需求分析，还要有注释。注释也很重要，特别是写过之后重用和测试代码时，都必须得看。否则就不得不将已写好的封装函数从头到尾再看一遍，再理解，这样很浪费时间。有了注释，就可以省去这些重新理解函数的时间，可以提高效率。
再次，写注释是为了使函数更简单的被理解。而写注释之前，必须要测试这段代码的可行性。必须要尽可能多的考虑会出现的情况，对不希望出现的情况予以相对的措施或者提示。这样在代码重用的时候也可以放心的重用，而不必因为代码写的不够完善而再来修改，这样也会浪费很多时间。
最后，程序的测试。一个完善的程序应该经得起测试。自己的程序写得好不好，最终得看测试。如果输入了非法的输入或者操作，程序是否能够正常运行？还是会像这次一输入错误就会死循环？这是程序的健壮性。做好以上几个方面，程序基本就做好了。但是任何一个程序都不可能没有BUG，金无足赤人无完人。如果要追求完美，就不得不锲而不舍，定期得到用户的反馈然后修复相关问题。就像微软一样，总是会在问题出现之后就发布漏洞补丁。
已测试完美运行，大学期末课设，运行无bug