算法程序设计实验报告.docx
《算法程序设计实验报告.docx》由会员分享，可在线阅读，更多相关《算法程序设计实验报告.docx（15页珍藏版）》请在冰点文库上搜索。
算法程序设计实验报告
《程序设计》课程设计
姓名：
王
学号：
班级：
软件工程00班
指导教师：
王会青
成绩：
2010年6月
实验一.构造可以使n个城市连接的最小生成树
专业：
__软件工程___班级：
__软件姓名：
_王___学号：
_
完成日期：
_2010/6/26________
一、【问题描述】
给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
1城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
2显示出城市间道路网的邻接矩阵。
3最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。
4输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal算法→执行Prim算法→输出最小生成树
二、【问题分析】
1.抽象数据类型结构体数组的定义：
#ifndefADJACENCYMATRIXED程图
创建用邻接矩阵表示的城市道路网
输入城市数、
道路数
输入城市名[i]
输入表示道路的两个城市及道路值[i][j].adj
返回OK
Prim算法
化辅助数组closeEdge
for（i=1;i<;++i）
求下一个城市k=Minimum（closeEdge,
输出找到的道路
标记城市，避免重复
输出总耗费
4.数据类型定义
为了用邻接矩阵表示图G，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。
并且在图中还定义一个用来存放城市的一维数组及int型的城市数级道路数。
用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。
这样就建立起了一个城市到城市之间的道路网。
4.程序主要模块
说明：
该程序共含5个模块，本人负责其中2个模块构造：
***************LocateVex（MGraphG,VertexTypev）****************
StatusLocateVex（MGraphG,VertexTypev）;
{
while（strcmp[i],v））{i++;}
返回i；
}
****************CreateUDN*************************
{
输入城市数、道路数；
for（i=0;i<城市数;++i）输入城市名；
for（i=0;i<城市数;++i）
for（j=0;j<城市数;++j）
初始化邻接矩阵：
道路值=INFINITY;
for（i=0;i<城市数;++i）
for（j=0;j<城市数;++j）
输入两个城市表示道路，输入道路值；
}
PRIM算法
**************************MiniSpanTree_PRIM*********
voidMiniSpanTree_PRIM（MGraphG,VertexTypeu）
{
定义辅助数组：
closedgecloseEdge;
初始化：
strcpy（closeEdge[j].adjvex,u）;
closeEdge[j].lowcost=[k][j].adj;
for（i=1;i<;++i）
{
在其余个城市中找到离辅助数组中标记的道路最小值；
显示找到的道路；
标记新找到的城市；
}
}
**********************Minimum*****************
StatusMinimum（closedgecloseEdge,intn）
{
在辅助数组中找到道路值最小的道路的两点城市：
if（（closeEdge[i].lowcost!
=0）&&（minTemp>closeEdge[i].lowcost））
返回该城市在G中的位置
}
三、【功能实现】
#include<>
#include<>
#include<>
#include<>
#include""
#include""
#include""
#include""
#include""
#include""
#include""
MGraphG;=UDN;
inti,j,k;
VertexTypev1,v2;
VRTypew;
printf（"构造可以使N个城市连接的最小生成树\n"）;
printf（"请输入城市数、道路数（至少6个城市，10条道路）：
"）;
cin>>>>;
for（i=0;i<;++i）dj=INFINITY;
nfo=NULL;
}
}
printf（"请输入一条道路连接的两个城市名及权值:
\n"）;
for（k=0;k<;++k）dj=w;owcost!
=0）&&（minTemp>closeEdge[i].lowcost））
{
minTemp=closeEdge[i].lowcost;
flag=i;
}
}
returnflag;
}
voidMiniSpanTree_PRIM（MGraphG,VertexTypeu）
{
djvex,u）;
closeEdge[j].lowcost=[k][j].adj;
}
}
cout<<"\n\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\\\n";
cout<<"|用Prim算法求最小生成树的各条边依次为：
\n-----";
closeEdge[k].lowcost=0;owcost=MIN{closeEdge[vi].lowcost|closeEdge[vi].lowcost>0,vi∈V-U}
cout<<'<'<';owcost;
closeEdge[k].lowcost=0;djcloseEdge[j].lowcost=[k][j].adj;
}
}
}
cout<<"\n|总代价：
"<cout<<"+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^/\n";
}问题描述】
某次科研调查时得到了n个自然数，每个数均不超过00（*109）。
已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
2【设计需求及分析】
（1）设计要求
原始数据保存在文件中，文件包含n+1行。
第1行是整数n（1<=n<=200000），表示自然数的个数；第2~n+1行每行一个自然数。
结果保存在文件count的尾部，其中结果包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。
每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
（2）设计思路
首先必须有文件的打开和关闭语句，将文件的内容读取到数组a[]中，然后对数组进行排列和对比，计数。
最终输出数据和次数。
并写入文件的尾部。
A[]为容纳数据的数组，fopen为文件打开函数，fscanf为文件读取函数，然后进行冒泡排序。
排序之后的内容由while设置条件，用if进行判断。
在不等于时，中间嵌套了一个while循环，进行往后的排查。
最后输出数据和次数。
下面是关键步骤：
FILE*fp=fopen（"","a+"）;【设计功能的实现】
#include<>intmain（）{
inta[100];心得体会】
本次实验使我对于文件的打开和关闭语句有了更深的理解。
有打开必须有关闭。
同时在这次的设计中，我学习到了用泛洪算法解决实际问题的基本思维和步骤。
使我对算法的层次性更加清楚，更加加深了对算法的理解。
实验三．送货
专业：
__软件工程___班级：
__软件姓名：
_王_学号：
_
完成日期：
_2010/6/26________
1.【问题描述】
小明希望设计一个方案，从编号为1的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。
输入数据格式
输入的第一行包含两个整数n,m（1≤n≤10,n-1≤m≤20），表示交叉路口的数量和街道的数量，交叉路口从1到n标号。
接下来m行，每行两个整数a,b，表示和标号为a的交叉路口和标号为b的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。
两个路口之间最多有一条街道。
输出输出格式
如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p1,p2,p3,...,pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。
如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2最小，依此类推。
如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。
测试数据一
输入：
输出：
45
12
13
14
24
34
124134
输出说明：
城市的地图和小明的路径如下图所示。
测试数据二
输入：
输出：
46
12
13
14
24
34
23
-1
输出说明：
城市的地图如下图所示，不存在满足条件的路径。
2【问题分析】
该算法使用欧拉回路，对于欧拉图，从一个节点出发，从某个节点开始，然后查出一个从这个出发回到这个点的环路径。
这种方法不保证每个边都被遍历。
如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。
这样直至所有的边都被遍历。
这样，整个图就被连接到一起了。
具体步骤:
1。
如果此时与该点无相连的点，那么就加入路径中
2。
如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。
3。
处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。
4。
这个其实是个递归过程。
3【功能实现】
#include
#include
#include
#include
#include
#include<>
usingnamespacestd;
constintmaxn=10005;
stackst;
vectorvec[maxn];
boolmap[maxn][maxn];
intvis[maxn];
intcp[maxn];
intn,m;
voidpd（inta）
{
cp[a]=1;
vector:
:
iteratorit;
for（it=vec[a].begin（）;it!
=vec[a].end（）;it++）
{
if（!
cp[*it]）
pd（*it）;
}
}
voiddfs（inta）
{
vector:
:
iteratorit;
for（it=vec[a].begin（）;it!
=vec[a].end（）;it++）
{
if（!
map[a][*it]）
{
map[a][*it]=1;
map[*it][a]=1;
dfs（*it）;
（*it）;
}
}
}
voidprt（）
{
（1）;
while（!
（））
{
ush_back（b）;
vec[b].push_back（a）;
vis[a]++;
vis[b]++;
}
intflag=0;
pd
（1）;
for（inti=1;i<=n;++i）
{
if（cp[i]==0）
flag=1;
else
break;
}
if（flag）
printf（"-1\n"）;
else
{
for（inti=1;i<=n;++i）
{
sort（vec[i].begin（）,vec[i].end（））;
if（vis[i]%2==1）
++num;
}
if（num==0||num==2）
{
if（num==2）
{
if（vis[1]%2==1）
{
dfs
（1）;
prt（）;
}
else
printf（"-1\n"）;
}
else
{
dfs
（1）;
prt（）;
}
}
else
{
printf（"-1\n"）;
}
}
system（"Pause"）;
return0;
}
4【实验结果】
5【心得体会】
通过这个实验，我掌握了欧拉回路的基本思想。
明白了用欧拉算法解决实际问题的具体步骤。
而且明白了用算法解决实际问题的思维方法。
实验4.消除类游戏
专业：
__软件工程___班级：
__软件姓名：
_王__学号：
_
完成日期：
_2010/6/28_______
1【问题描述】
消除类游戏是深受大众欢迎的一种游戏，游戏在一个包含有n行m列的游戏棋盘上进行，棋盘的每一行每一列的方格上放着一个有颜色的棋子，当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。
当有多处可以被消除时，这些地方的棋子将同时被消除。
现在给你一个n行m列的棋盘（1≤n,m≤30），棋盘中的每一个方格上有一个棋子，请给出经过一次消除后的棋盘。
请注意：
一个棋子可能在某一行和某一列同时被消除。
输入数据格式：
输入的第一行包含两个整数n,m，用空格分隔，分别表示棋盘的行数和列数。
接下来n行，每行m个整数，用空格分隔，分别表示每一个方格中的棋子的颜色。
颜色使用1至9编号。
输出数据格式：
输出n行，每行m个整数，相邻的整数之间使用一个空格分隔，表示经过一次消除后的棋盘。
如果一个方格中的棋子被消除，则对应的方格输出0，否则输出棋子的颜色编号。
【测试数据】
为方便调试程序，可将输入数据先写入一个文本文件，然后从文件读取数据处理，这样可避免每次运行程序时都要从键盘输入数据。
测试数据一
输入：
输出：
45
22312
34514
23213
22244
22302
34504
23203
00044
输出说明：
棋盘中第4列的1和第4行的2可以被消除，其他的方格中的棋子均保留。
测试数据二
输入：
输出：
45
22312
31111
23213
22333
22302
30000
23203
22000
输出说明：
棋盘中所有的1以及最后一行的3可以被同时消除，其他的方格中的棋子均保留。
2【问题分析】
3【功能实现】
#include""
#include
#include<>
usingnamespacestd;
intmain（）
{
intm,n,i,j;
inttemp;
cin>>n>>m;
temp=m;
m=n;
n=temp;
int*map=newint[m*n];
int*mark=newint[m*n];
int*tmap=map;
int*tmark=mark;
intdif=0;
//输入
for（i=0;ifor（j=0;jcin>>*（tmap+i*n+j）;
for（i=0;ifor（j=0;j{
//横行
if（（tmap+2-map）%n!
=0||（tmap+1-map）%n!
=0）
if（*（tmap）==*（tmap+1）&&*（tmap+1）==*（tmap+2））
{
dif=tmap-map;
*（tmark+dif）=0;
*（tmark+dif+1）=0;
*（tmark+dif+2）=0;
}
//竖列
if（tmap+2*n-mapif（*（tmap）==*（tmap+n）&&*（tmap+n）==*（tmap+2*n））
{
dif=tmap-map;
*（tmark+dif）=0;
*（tmark+dif+n）=0;
*（tmark+dif+2*n）=0;
}
tmap=map+（j+1）+i*n;
}
//输出
cout<tmap=map;
for（i=0;ifor（j=0;jif（*（tmark+i*n+j）==0）
*（tmap+i*n+j）=0;
for（i=0;i{
for（j=0;jcout<<*（tmap+i*n+j）<<"";
cout<}
system（"pause"）;
return0;
}
4【实验结果】
5【心得体会】
在该实验中，我掌握了求相同行以及相同列的数字是否相同的计算方法。
先采用排序然后将相同的消去，最终得到实验结果。
升级会员 