算法程序设计实验报告.docx

1、算法程序设计实验报告程序设计课程设计姓 名：王学 号：班 级：软件工程00班指导教师： 王会青 成 绩：2010年6月实验一.构造可以使n个城市连接的最小生成树专业：_软件工程_ 班级：_软件 姓名：_王_ 学号：_完成日期：_2010/6/26_一、【问题描述】给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。2 显示出城市间道路网的邻接矩阵。3 最小生成树中包括的边及其权值，并显示得

2、到的最小生成树的总代价。4 输入城市数、道路数输入城市名输入道路信息执行Kruskal 算法执行 Prim 算法输出最小生成树二、【问题分析】1.抽象数据类型结构体数组的定义：#ifndef ADJACENCYMATRIXED 程图创建用邻接矩阵表示的城市道路网输入城市数、道路数输入城市名i输入表示道路的两个城市及道路值ij.adj返回 OKPrim算法化辅助数组closeEdgefor (i=1; i; +i)求下一个城市k = Minimum(closeEdge, 输出找到的道路标记城市，避免重复输出总耗费4.数据类型定义为了用邻接矩阵表示图 G ，先是定义二维数组的每一个元素含道路值然后

3、在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int 型的城市数级道路数。用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。这样就建立起了一个城市到城市之间的道路网。4. 程序主要模块说明：该程序共含5个模块，本人负责其中2个模块构造：*LocateVex(MGraph G, VertexType v)*Status LocateVex(MGraph G, VertexType v); while (strcmpi, v) i+; 返回 i；* CreateUDN* 输入城市数、道路数； for (i=0; i城市数; +i) 输入城市

4、名； for (i=0; i城市数; +i) for(j=0; j城市数; +j) 初始化邻接矩阵：道路值= INFINITY; for (i=0; i城市数; +i) for(j=0; j城市数; +j) 输入两个城市表示道路，输入道路值；PRIM算法* MiniSpanTree_PRIM*void MiniSpanTree_PRIM(MGraph G, VertexType u) 定义辅助数组：closedge closeEdge; 初始化：strcpy(closeEdgej.adjvex, u); closeEdgej.lowcost = kj.adj; for (i=1; i clos

5、eEdgei.lowcost) 返回该城市在 G 中的位置三、【功能实现】#include #include #include #include #include #include #include #include #include #include #include MGraph G; = UDN; int i, j, k; VertexType v1, v2; VRType w; printf( 构造可以使N个城市连接的最小生成树n); printf(请输入城市数、道路数(至少6个城市，10条道路)：); cin; for (i=0; i; +i) dj = INFINITY; nfo

6、= NULL; printf(请输入一条道路连接的两个城市名及权值:n); for (k=0; k closeEdgei.lowcost) minTemp = closeEdgei.lowcost; flag = i; return flag;void MiniSpanTree_PRIM(MGraph G, VertexType u) djvex, u); closeEdgej.lowcost = kj.adj; coutnn+n; cout 0, viV-U coutcloseEdgek.adjvex,k; owcost; closeEdgek.lowcost = 0; dj closeEd

7、gej.lowcost) djvex, k); closeEdgej.lowcost = kj.adj; coutn|总代价：totalCostendl; cout+/n;问题描述】 某次科研调查时得到了n个自然数，每个数均不超过00（*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。 2【设计需求及分析】 （1）设计要求 原始数据保存在文件中，文件包含n+1行。第1行是整数n(1=n=200000)，表示自然数的个数；第2n+1行每行一个自然数。 结果保存在文件count的尾部，其中结果包含m行（m为n个自然数中不相同

8、数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 (2)设计思路 首先必须有文件的打开和关闭语句，将文件的内容读取到数组a中，然后对数组进行排列和对比，计数。最终输出数据和次数。并写入文件的尾部。 A为容纳数据的数组，fopen为文件打开函数，fscanf为文件读取函数，然后进行冒泡排序。排序之后的内容由while设置条件，用if进行判断。在不等于时，中间嵌套了一个while循环，进行往后的排查。最后输出数据和次数。 下面是关键步骤： FILE* fp=fopen(,a+); 【设计功能的实现】 #include int main(

9、) int a100; 心得体会】 本次实验使我对于文件的打开和关闭语句有了更深的理解。有打开必须有关闭。同时在这次的设计中，我学习到了用泛洪算法解决实际问题的基本思维和步骤。使我对算法的层次性更加清楚，更加加深了对算法的理解。实验三送 货专业：_软件工程_ 班级：_软件 姓名：_王_ 学号：_完成日期：_2010/6/26_1.【问题描述】小明希望设计一个方案，从编号为1的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。输入数据格式输入的第一行包含两个整数n, m(1n10, n-1m20)，表示交叉路口的数量和街道的数量，交

10、叉路口从1到n标号。接下来m行，每行两个整数a, b，表示和标号为a的交叉路口和标号为b的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。输出输出格式如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p1, p2, p3, ., pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2最小，依此类推。如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。测试数据一输入：输出：4 51 21 31 42 43 41 2

11、4 1 3 4输出说明：城市的地图和小明的路径如下图所示。测试数据二输入：输出：4 61 21 31 42 43 42 3-1输出说明：城市的地图如下图所示，不存在满足条件的路径。2【问题分析】 该算法使用欧拉回路，对于欧拉图，从一个节点出发，从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。具体步骤:1。如果此时与该点无相连的点，那么就加入路径中2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。

12、3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。4。这个其实是个递归过程。3【功能实现】#include #include #include #include #include#include using namespace std; const int maxn=10005; stack st; vector vecmaxn; bool mapmaxnmaxn; int vismaxn; int cpmaxn; int n,m; void pd(int a) cpa=1; vector:iterator it; for(it=veca.begi

13、n();it!=veca.end();it+) if(!cp*it) pd(*it); void dfs(int a) vector:iterator it; for(it=veca.begin();it!=veca.end();it+) if(!mapa*it) mapa*it=1; map*ita=1; dfs(*it); (*it); void prt() (1); while(!() ush_back(b); vecb.push_back(a); visa+; visb+; int flag=0; pd(1); for(int i=1;i=n;+i) if(cpi=0) flag=1;

14、 else break; if(flag) printf(-1n); else for(int i=1;i=n;+i) sort(veci.begin(),veci.end(); if(visi%2=1) +num; if(num=0|num=2) if(num=2) if(vis1%2=1) dfs(1); prt(); else printf(-1n); else dfs(1); prt(); else printf(-1n); system(Pause); return 0; 4 【实验结果】5【心得体会】 通过这个实验，我掌握了欧拉回路的基本思想。明白了用欧拉算法解决实际问题的具体步骤

15、。而且明白了用算法解决实际问题的思维方法。 实验4.消除类游戏 专业：_软件工程_ 班级：_软件 姓名：_王_ 学号：_完成日期：_2010/6/28_1【问题描述】消除类游戏是深受大众欢迎的一种游戏，游戏在一个包含有n行m列的游戏棋盘上进行，棋盘的每一行每一列的方格上放着一个有颜色的棋子，当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。现在给你一个n行m列的棋盘(1n,m30)，棋盘中的每一个方格上有一个棋子，请给出经过一次消除后的棋盘。请注意：一个棋子可能在某一行和某一列同时被消除。输入数据格式：输入的第一行包含两个整数

16、n, m，用空格分隔，分别表示棋盘的行数和列数。接下来n行，每行m个整数，用空格分隔，分别表示每一个方格中的棋子的颜色。颜色使用1至9编号。输出数据格式：输出n行，每行m个整数，相邻的整数之间使用一个空格分隔，表示经过一次消除后的棋盘。如果一个方格中的棋子被消除，则对应的方格输出0，否则输出棋子的颜色编号。【测试数据】为方便调试程序，可将输入数据先写入一个文本文件，然后从文件读取数据处理，这样可避免每次运行程序时都要从键盘输入数据。测试数据一输入：输出：4 52 2 3 1 23 4 5 1 42 3 2 1 32 2 2 4 42 2 3 0 23 4 5 0 42 3 2 0 30 0 0

17、 4 4输出说明：棋盘中第4列的1和第4行的2可以被消除，其他的方格中的棋子均保留。测试数据二输入：输出：4 52 2 3 1 23 1 1 1 12 3 2 1 32 2 3 3 32 2 3 0 23 0 0 0 02 3 2 0 32 2 0 0 0输出说明：棋盘中所有的1以及最后一行的3可以被同时消除，其他的方格中的棋子均保留。2【问题分析】3【功能实现】#include #include #include using namespace std;int main() int m, n, i ,j; int temp; cin n m; temp = m; m = n; n = tem

18、p; int * map = new intm * n; int * mark = new intm * n; int * tmap = map; int * tmark = mark; int dif = 0;/输入 for ( i = 0 ; i m ; i+ ) for (j = 0; j *(tmap + i * n + j); for (i = 0; i m; i+) for (j = 0; j n; j+) /横行 if (tmap + 2 - map) % n != 0 | (tmap + 1 - map) % n != 0) if (*(tmap) = *(tmap + 1)

19、& * (tmap + 1) = *(tmap + 2) dif = tmap - map; *(tmark + dif) = 0; *(tmark + dif + 1) = 0; *(tmark + dif + 2) = 0; /竖列 if (tmap + 2 * n - map m * n | tmap + n - map m * n) if (*(tmap) = *(tmap + n) & * (tmap + n) = *(tmap + 2 * n) dif = tmap - map; *(tmark + dif) = 0; *(tmark + dif + n) = 0; *(tmark

20、 + dif + 2 * n) = 0; tmap = map + (j+1) + i * n; /输出 cout endl; tmap = map; for (i = 0; i m; i+) for (j = 0; j n; j+) if (* (tmark + i * n + j) = 0) *(tmap + i * n + j) = 0; for (i = 0; i m; i+) for (j = 0; j n; j+) cout *(tmap + i * n + j) ; cout endl; system(pause); return 0;4【实验结果】5【心得体会】 在该实验中，我掌握了求相同行以及相同列的数字是否相同的计算方法。先采用排序然后将相同的消去，最终得到实验结果。