算法程序设计实验报告

《程序设计》课程设计

姓 名：王

学 号班 级：软件工程00班

指导教师：王会青

成 绩：

2010年6月 实验一?构造可以使n个城市连接的最小生成 树

专业：—软件工程 班级：—软件:_王 学号：完成日期：_2010/6/26

一、 【问题描述】

给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法

建立最小生成树，并计算得到的最小生成树的代价 。

1城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个

城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。

2显示出城市间道路网的邻接矩阵。

3最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。

4输入城市数、道路数t输入城市名t输入道路信息t执行 Kruskal算法宀执行Prim算法宀输

出最小生成树

二、 【问题分析】

抽象数据类型结构体数组的定义：

#ifndef ADJACENCYMATRIXED//防止该头文件被重复引用

#define ADJACENCYMATRIXED //而引起的数据重复定义

#define INFINITY 32767 // 最大值

#define MAX_VERTEX_NUM 20 // 最大顶点个数

typedef int VRType; // 权值，即边的值

typedef char InfoType; //附加信息的类型，后面使用时会定义成一个指针

typedef char VertexType[MAX_VERTEX_NUM]; // 顶点类型

typedef enum {DG=1, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网 }

typedef struct ArcCell

{

VRType adj; //VRType是顶点关系类型。对无权图，用 1或0表示相邻否；对带

权图，则为权值类型。

InfoType* info; //该弧关系信息的指针

}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量

AdjMatrix

arcs;

//邻接矩阵

int vexnum, arcnum;

//图的当前顶点数和弧数

GraphKi nd

}MGraph;

ki nd;

//图的种类标志

typedef struct

{

VertexType adjvex;

VRType lowcost;

}closedge[MAX_VERTEX_NUM];

//普里姆算法辅助数组的定义

#en dif

//结束if

2程序模块

MGraph G;

int main (i nt argc, char * argv[]);

Status LocateVex(MGraph G, VertexType v);

Status CreateUDN(MGraph & G); void DisplayNet(MGraph G);

void Mi niSpa nTree_KRUSKAL(MGraph G);

//网G,唯一的全局变量

//主函数

//判断城市v在网G中的位置

//创建网G的邻接矩阵

//以邻接矩阵的形式显示网 G

//最小生成树的Kruskal算法

void Mi niSpa nTree_PRIM(MGraph G, VertexType u); // Status Minim um(closedge closeEdge, int n); //Prim

最小生成树的Prim算法

算法中求下一个城市的函数

void DeleteI nfo(MGraph & G);

//释放堆存上动态申请的空间

流程图

创建用邻接矩阵表示的城市道路网

输入城市数 G.vexnum、

道路数G.arcnum

输入城市名G.vexs[i]

输入表示道路的两个城市及道路值

G.arcs[i][j].adj

返回0K

Prim算法

化辅助数组closeEdge

for (i=1; i<G.vex num; ++i)

求下一个城市 k = Minimu m(closeEdge,

G.vex num)

输出找到的道路

标记城市，避免重复

输出总耗费

数据类型定义

为了用邻接矩阵表示图 G ，先是定义二维数组的每一个元素含道路值然后在图的定义中定义

int型的城市数一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及

int型的城市数

用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。

这样就建立起了一个城市到城市之间的道路网。

4. 程序主要模块

说明：该程序共含 5 个模块，本人负责其中 2 个模块构造： ***************LocateVex(MGraph G, VertexType v)**************** Status LocateVex(MGraph G, VertexType v);

{

while (strcmp(G.vexs[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********* void MiniSpanTree_PRIM(MGraph G, VertexType u) {

定义辅助数组： closedge closeEdge; 初始化： strcpy(closeEdge[j].adjvex, u);

closeEdge[j].lowcost = G.arcs[k][j].adj;

for (i=1; i<G.vexnum; ++i) {

在其余 G.vexnum-1 个城市中找到离辅助数组中标记的道路最小值； 显示找到的道路；

标记新找到的城市；

}

}

********************** Minimum*****************

Status Minimum(closedge closeEdge, int n)

{

在辅助数组中找到道路值最小的道路的两点城市：

if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost)) 返回该城市在 G 中的位置

}

三、【功能实现】

#include <iostream.h>

#include <stdio.h>

#include <string.h>

#include <windows.h>

#include "TypeDefine.h"

#include "AdjacencyMatrix.h"

#include "InitializeFunction.h"

#include "MiniSpanTree_KRUSKAL.h"

#include "MiniSpanTree_PRIM.h"

#include "DisplayNet.h"

#include "DeleteInfo.h"

MGraph G;//

MGraph G;

// 全局变量 G

int main(int argc, char * argv[]);// 主函数

Status LocateVex(MGraph G, VertexType v);// 判断城市 v 在网 G 中的位置

Status CreateUDN(MGraph &G);// 创建网 G 的邻接矩阵

void DisplayNet(MGraph G);// 以邻接矩阵的形式显示网 G

void MiniSpanTree_KRUSKAL(MGraph G);// 最小生成树的 Kruskal 算法

void MiniSpanTree_PRIM(MGraph G, VertexType u);// 最小生成树的 Prim 算法

Status Minimum(closedge closeEdge, int n);//Prim 算法中求下一个城市的函数

void DeleteInfo(MGraph &G);// 释放堆存上动态申请的空间

int main(int argc, char * argv[])

{

CreateGraph(G);

DisplayNet(G);

MiniSpanTree_KRUSKAL(G);

MiniSpanTree_PRIM(G, G.vexs[0]);

DeleteInfo(G);

cout<<endl<<endl;

system("pause");

return 0;

}

//intializeFunction.h

Status CreateDG(MGraph &G){return 0;};

Status CreateDN(MGraph &G){return 0;};

Status CreateUDG(MGraph &G){return 0;};

Status CreateUDN(MGraph &G);

Status LocateVex(MGraph G, VertexType v) {

// 判断输入的顶点 v 在 G 中的位置。

// 根据顶点的类型，可重载此函数。目前为 char int i=0;

while (strcmp(G.vexs[i], v)) {i++;}

return i;

}

Status CreateGraph(MGraph &G)

{

// 采用数组(邻接矩阵)表示法，构造图 G.

G.kind = UDN; // 默认构造无向网

/* printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");

printf("|1:

有向图 2: 无向图 3: 有向网 4: 无向网 \n");

printf("| 请选择 :[ ]\b\b");

scanf("%d", &G.kind);

printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");*/

switch (G.kind)

{

case DG: return CreateDG(G);

// 构造有向图 G

case DN: return CreateDN(G);

// 构造有向网 G

case UDG: return CreateUDG(G);

// 构造无向图 G

case UDN: return CreateUDN(G);

// 构造无向网 G

default : return ERROR;

}

}//CreateGraph

printf("

printf(" 共 %3d条道路，第 %3d条道路：", G.arcnum,k+1);

Status CreateUDN(MGraph &G) {

// 采用数组(邻接矩阵)表示法，构造图 G.

int i, j, k;

VertexType v1, v2;

VRType w;

\n");printf(” 构造可以使N个城市连接的最小生成树

\n");

printf(" 请输入城市数、道路数 (至少 6个城市， 10条道路) ： "); cin>>G.vexnum>>G.arcnum;

for (i=0; i<G.vexnum; ++i) // 构造顶点向量

{

printf(" 请输入第 %d 个城市名(共 %d 个) :", i+1, G.vexnum); cin>>G.vexs[i];

}

for (i=0; i<G.vexnum; ++i) // 初始化邻接矩阵

{

for (j=0; j<G.vexnum; ++j)

{

G.arcs[i][j].adj = INFINITY;

// G.arcs[i][j].info = NULL;

}

}

printf(" 请输入一条道路连接的两个城市名及权值 :\n");

for (k=0; k<G.arcnum; ++k) // 构造邻接矩阵

{

cin>>v1>>v2>>w;// 输入一条边依附的顶点及权值i

cin>>v1>>v2>>w;

// 输入一条边依附的顶点及权值

i = LocateVex(G, v1);

//确定v1、v2在G中的位置

j = LocateVex(G, v2);

G.arcs[i][j].adj =

G.arcs[i][j].adj = w;

//弧＜v1,v2＞的权值

G.arcs[j][i] =

G.arcs[j][i] = G.arcs[i][j];

// 置<v1,v2> 的对称弧 <v2,v1>

return OK;

}//CreateUDN

//MiniSpan Tree PRIM.h

Status Minimum(closedge closeEdge, int n)

{

int i, flag, minTemp = INFINITY;

for (i=0; i<n; ++i)

{

if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost))

{

minTemp = closeEdge[i].lowcost;

flag = i;

return flag;

void MiniSpanTree_PRIM(MGraph G, VertexType u)

// 用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T ，输出 T 的各条边。

// 记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义见 "AdjacencyMatrix.h" int i, j, k, totalCost=0; closedge closeEdge; k = LocateVex(G, u);

for (j=0; j<G.vexnum; ++j) // 辅助数组初始化

{

if (j != k)

{

strcpy(closeEdge[j].adjvex, u); closeEdge[j].lowcost = G.arcs[k][j].adj;

}

}

cout<<"| 用 Prim 算法求最小生成树的各条边依次为： \n ";

closeEdge[k].lowcost = 0; // 初始， U={u};

for (i=1; i<G.vexnum; ++i) // 选择其余 G.vexnum-1 个顶点

{

k = Minimum(closeEdge, G.vexnum); // 求出 T 的下一个结点：第 k 顶点

// 此时 closeEdge[k].lowcost = MIN{closeEdge[vi].lowcost | closeEdge[vi].lowcost >

0, vi € V-U}

cout<<'<'<<closeEdge[k].adjvex<<','<<G.vexs[k]<<'>'; // 输出生成树的边

totalCost += closeEdge[k].lowcost;

closeEdge[k].lowcost = 0; // 第 k 顶点并入 U 集

for (j=0; j<G.vexnum; ++j)

// 新顶点并入

// 新顶点并入 U 后重新选

if (G.arcs[k][j].adj < closeEdge[j].lowcost)

择最小边

strcpy(closeEdge[j].adjvex, G.vexs[k]);

closeEdge[j].lowcost = G.arcs[k][j].adj;

}

}

}

cout<<"\n| 总代价："<<totalCost<<e ndl;

cout<<"+AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

}//Mi niSpa nTree

四、 【实 例 测 试 及 运 行 结 果】

乱4 /W4 ”444 Z444 W矢4 W仮 、

:用叶5算法求最小生成树的各条边依次为士

<cs.乙2Xcs*cd><c&yy><yy>sy><yy,hyXcs-,hh><cd, Id>

；总代价i 385

AAAA AAAA AAAAAAA AAAA AAAA AAAA A A A A A A A A AAA A A 鼻

￥臂In

城

r值1 i ! L 1 '■ :tz

￥

臂

In

城

r

值

1 i ! L 1 '■ :tz" / c y 1 G h s h 2R% 使嫌 名

以"个个个卡个个个佛牺艸』cdgzshh須舸皿22沖 PT?pfrUD 6 OD s B 8 6 8 E : t ■- F r t -h k = 个陀踣昭路路陷踣花踣籬路膜

一道霁7書道谊道ii T _? 1 T -.1 T -1 T

」沪莎￥力V bT;[r;-1牛.-1￥甲孑甲-T.T卡孑羊 勲个个个个个个个个E亠,?* ?卞k*?"*

W12 3 4 5 6 7 8 城- 入人入入入人人AAA' 触壽辂谕钳输 请溝谓普丄rflalgRlis哇IV1共共共共共共共头共W共W

監 ￥dd3ryll2

c V- 1 G h s h 2

5 d s d d u*sfszv-d e G c 1 h c e z h D

5 4 & 7375 I ? I

12945S7B90 12

ILL

^iKfeM路黑K路路路路路踣 22-2222222 2 22

1- 1 i

五、【心得体会】

通过本周的课程设计，我有不少收获。既巩固和加深了对数据结构的理解，认识到《数据结 构》是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。

而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料，

所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的

课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通 过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。

在以后的学习过程中我将要注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、

写程序的过程要考虑周到，严密。

　3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的

学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。 5、在课余时间里多写程序，

熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。

实验二：统计数字

专业：

软件工程 班级： 软件 ： 王 学号完成日期：_2010/6/28_

1.【问题描述】

某次科研调查时得到了 n个自然数，每个数均不超过 1500000000 ( 1.5*109 )。已知不相同的数不

超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统 计结果。

2【设计需求及分析】

(1)设计要求

原始数据保存在文件 count.in 中，文件包含n+1行。第1行是整数n(1<=n<=200000)，表示自然

数的个数；第2~ n+1行每行一个自然数。

结果保存在文件count的尾部，其中结果包含 m行(m为n个自然数中不相同数的个数)，按照自 然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空 格隔开。

(2)设计思路 首先必须有文件的打开和关闭语句，将文件的容读取到数组 计数。最终输出数据和次数。并写入文件的尾部。

A[]为容纳数据的数组，

a[]中，然后对数组进行排列和对比,

序之后的容由while设置条件，用 往后的排查。最后输出数据和次数。

　下面是关键步骤：

FILE* fp=fope n("cou nt.txt","a+");

if(fp==NULL) {

printf(" 无文件");

return -1; }

for(i=0;i<9;i++) {

fscan f(fp,"%d",&a[i]);

fscanf(fp,"\n”); }

int j,t;

for (i=1;i<9;i++)

for(j=0;j<9-i;j++) if(a[j]>a[j+1]){

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

for(i=0;i<9;i++) {

fopen为文件打开函数，

if进行判断。

//

//

//

//

fscanf为文件读取函数，然后进行冒泡排序。排 在不等于时，中间嵌套了一个 while循环，进行

用只读/的方式打开文件

若没有文件则返回一1

读取文件

冒泡排序

count=1;

if (a[i]!=a[i+1]) { printf("%d\t%d\n",a[i],count); fprintf(fp,"%d\t%d\n",a[i],a[i]); i++;

对数字的循环查找和控制条件，}

对数字的循环查找和控制条件，

if(a[i] == a[i + 1])

{

while(a[i] == a[i + 1])

{

count++;

i++; }

}

}

( 3)输出输入格式

输入时，为竖行依此输入文件，且为数字。且为 9 个以的数字。

　输出时，分为两行，第一列为数 据，第二列为次数。

　3. 【设计功能的实现】

#include <stdio.h> int main() {

int a[100]; //FILE* fp=fopen("count.txt","a+"); //

int a[100]; //

FILE* fp=fopen("count.txt","a+"); //

printf(" 无文件 "); // for(i=0;i<9;i++) { fscanf(fp,"%d",&a[i]); //

int j,t;

for (i=1;i<9;i++)

for(j=0;j<9-i;j++) if(a[j]>a[j+1]) { //

t=a[j];

a[j]=a[j+1];

a[j+1]=t; }

printf(" 结果为： \n 数据 结果 \n"); for(i=0;i<9;i++) {

count=1;

if(a[i]!=a[i+1]) { printf("%d\t%d\n",a[i],count); printf(fp,"%d\t%d\n",a[i],a[i]); i++;

}

if(a[i] == a[i + 1])

{

while(a[i] == a[i + 1])

{

创建容纳文件数据的数组 int i;

用只读 / 的方式打开文件 if(fp==NULL) { 若没有文件则返回— 1 return -1; }

读取文件 fscanf(fp,"\n"); }

冒泡排序

int count;

count++;

i++；

}

printf("%d\t%d\n", a[i], count);

fprin tf(fp,"%d\t%d\n", a[i], count);

}

}

fclose(fp); // 关闭文件

return 0;

}

4.【实例测试及运行结果】

敦据结果

TOC \o "1-5" \h \z 2 3

2

1

100 2

濡按任意键继续?…

【心得体会】

本次实验使我对于文件的打开和关闭语句有了更深的理解。有打开必须有关闭。同时在这次 的设计中，我学习到了用泛洪算法解决实际问题的基本思维和步骤。使我对算法的层次性更加清 楚，更加加深了对算法的理解。

实验三?送货

专业：

软件工程 班级： 软件：王 学号完成日期： 2010/6/26

1.【问题描述】

小明希望设计一个方案，从编号为 1的交叉路口出发，每次必须沿街道去往街道另一端的路

口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。

输入数据格式

输入的第一行包含两个整数 n, m(1 w n< 10, n-1 < m< 20)，表示交叉路口的数量和街道的数

量，交叉路口从1到n标号。

接下来m行，每行两个整数 a, b，表示和标号为a的交叉路口和标号为 b的交叉路口之间有 一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。

输出输出格式

如果小明可以经过每条街道正好一次，则输出一行包含 m+1个整数P1, p 2, p 3, ..., p m+1,表

示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输 出字典序最小的一种方案，即首先保证 P1最小，P1最小的前提下再保证 P2最小，依此类推。

如果不存在方案使得小明经过每条街道正好一次，则输出一个整数 -1。

测试数据

输入：

输出：

4 5

1 2 4 1 3 4

1 2

1 3

1 4

2 4

3 4

输出说明：城市的地图和小明的路径如下图所示。

输入：

输出：

4 6

-1

1 2

1 3

1 4

2 4

3 4

2 3

输出说明：城市的地图如下图所示，不存在满足条件的路径。

2【问题分析】

该算法使用欧拉回路，对于欧拉图，从一个节点出发，从某个节

点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证 每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条 边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样, 整个图就被连接到一起了。

具体步骤：

1。如果此时与该点无相连的点，那么就加入路径中

2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没

有相连的点

3。 处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的 操作，并把删除的点加入到路径中去。

4。 这个其实是个递归过程。

3【功能实现】

#inelude <iostream>

#inelude <stack>

#inelude <veetor>

#include《algorithm〉

#inelude <estdio>

#in elude <win dows.h>

using namespaeestd;

const int maxn=10005;

staek< int > st;

vectorv int > vee[maxn];

bool map[max n][max n];

int vis[maxn];

int ep[maxn];

int n,m;

void pd( int a)

{

ep[a]=1;

vectorv int >::iterator it;

for (it=vec[a].begin();it!=vec[a].end();it++)

{

if (!ep[*it])

pd(*it);

}

}

void dfs( int a)

{

vectorv int >::iterator it;

for (it=vec[a].begin();it!=vec[a].end();it++)

{

if (!map[a][*it])

{ map[a][*it]=1; map[*it][a]=1; dfs(*it); st.push(*it);

}

}

}

void prt()

{

st.push(1);

while (!st.empty())

{

//printf("%d ",st.top()); int ss=st.top();

st.pop();

printf( "%d " ,ss);

}

}

int main()

{

int num=0; //memset(cp,0,sizeof(cp)); //memset(vis,0,sizeof(vis)); //memset(map,0,sizeof(map)); for (int i=0;i<maxn;++i)

{

cp[i]=vis[i]=0;

}

scanf( "%d %d",&n,&m);

int a,b;

for (int i=0;i<m;++i)

{

scanf( "%d %d",&a,&b); vec[a].push_back(b); vec[b].push_back(a); vis[a]++;

vis[b]++;

}

int flag=0;

pd(1);

for (int i=1;i<=n;++i)

{

if (cp[i]==0)

flag=1;

else

break ;

}

if (flag)

printf( "-1\n" );

else

{

for (int i=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" );

return 0;

4【实验结果】

5【心得体会】

通过这个实验，我掌握了欧拉回路的基本思想。明白了用欧拉算法解决

实际问题的具体步骤。而且明白了用算法解决实际问题的思维方法。

实验4.消除类游戏

专业： _软件工程_ 班级： —软件:—王_ 学号：完成日期：_2010/6/28_ _

1【问题描述】

消除类游戏是深受大众欢迎的一种游戏，游戏在一个包含有 n行m列的游戏棋盘上进行，棋

盘的每一行每一列的方格上放着一个有颜色的棋子，当一行或一列上有连续三个或更多的相同颜 色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。

现在给你一个n行m列的棋盘(1 < n,mw 30)，棋盘中的每一个方格上有一个棋子，请给出经 过一次消除后的棋盘。

请注意：一个棋子可能在某一行和某一列同时被消除。

输入数据格式：

输入的第一行包含两个整数 n, m，用空格分隔，分别表示棋盘的行数和列数。接下来 n行,

每行m个整数，用空格分隔，分别表示每一个方格中的棋子的颜色。颜色使用 1至9编号。

输出数据格式：

输出n行，每行m个整数，相邻的整数之间使用一个空格分隔，表示经过一次消除后的棋盘。

如果一个方格中的棋子被消除，则对应的方格输出 0,否则输出棋子的颜色编号。

【测试数据】

为方便调试程序，可将输入数据先写入一个文本文件，然后从文件读取数据处理，这样可避 免每次运行程序时都要从键盘输入数据。

测试数据

输入：

输出：

4 5

2 2 3 0 2

2 2 3 1 2

3 4 5 0 4

3 4 5 1 4

2 3 2 0 3

2 3 2 1 3

0 0 0 4 4

2 2 2 4 4

输出说明：

棋盘中第4列的1和第4行的2可以被消除，其他的方格中的棋子均保留。

测试数据二

输入：

输出：

4 5

2 2 3 0 2

2 2 3 1 2

3 0 0 0 0

3 1 1 1 1

2 3 2 0 3

2 3 2 1 3

2 2 0 0 0

2 2 3 3 3

输出说明：

棋盘中所有的1以及最后一行的3可以被同时消除，其他的方格中的棋子均保留。

2【问题分析】

3【功能实现】

#i nclude "stdafx.h"

#in elude <iostream>

#in elude <win dows.h>

using namespacestd;

int main()

{

int m, n, i ,j;

int temp;

cin >> n >> m;

temp = m;

m = n;

n = temp;

int * map = new int [m * n];

int * mark = new int [m * n];

int * tmap = map;

int * tmark = mark;

int dif = 0;

//输入

for ( i = 0 ; i < m ; i++ )

for (j = 0; j < n; j++)

cin >> *(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) && * (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 + 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【心得体会】

在该实验中，我掌握了求相同行以及相同列的数字是否相同的计算方法。

先采用排序然后将相同的消去，最终得到实验结果。