代写C#Fitness、C++、代做C++、迷宫问题链表

日期：2018-05-02 08:55

11.迷宫问题

1.问题描述：

迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶

盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障

碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路

以到达出口。以一个 m×n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障

碍，前进的方向有 4 个，分别是上、下、左、右。设计一个程序，对任意设定的

迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

2.实现要求：

⑴ 设计数据结构存储迷宫；

⑵ 实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程

序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫

中的一个坐标，d 表示走到下一坐标的方向。

⑶ 编写递归形式的算法，求得迷宫中所有可能的通路；

⑷ 以方阵形式输出迷宫及其通路。

3.测试数据

迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。

1 2 3 4 5 6 7 8

0 0 1 0 0 0 1 0

0 0 1 0 0 0 1 0

0 0 0 0 1 1 0 1

0 1 1 1 0 0 1 0

17 / 43

0 0 0 1 0 0 0 0

0 1 0 0 0 1 0 1

0 1 1 1 1 0 0 1

1 1 0 0 0 1 0 1

1 1 0 0 0 0 0 0

4.实现提示：

计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向

进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，

直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，

则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标

为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一

圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的

搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处

可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原

路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找

到一条通路，或无路可走又返回到入口点。

在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出

的栈来保存从入口到当前位置的路径。

可以将迷宫定义成一个二维数组，则每个点有 4 个试探方向，如当前点的坐标

是(x, y)，与其相邻的 4 个点的坐标都可根据与该点的相邻方位而得到，规定试

探顺序为顺时针方向，将这 4 个方向的坐标增量放在一个结构数组 move[4]中，

在 move 数组中，每个元素由两个域组成：x 表示横坐标增量，y 表示纵坐标增

量。这样会很方便地求出从某点(x，y)按某一方向 v (0≤v≤3) 到达新点（i，j）

的坐标：i=x+move[v].x ； j=y+move[v].y。

18 / 43

12.成绩排序

1.问题描述

假设某年级有 4 个班，每班有 40 名同学。本学期有 5 门课程考试，每门课

程成绩是百分制。假定每个同学的成绩记录包含：学号、各门课程的成绩共 6

项，其中学号是一个 12 位的字符串(参照同学们的学号)，每个学生都有唯一的

学号，并且这 4 个班的成绩分别放在 4 个数组中，完成以下操作要求：

⑴ 编写一个成绩生成函数，使用随机数方法，利用随机函数生成学生的各

门课程的成绩（每门课程的成绩都是 0∽100 之间的整数），通过调用该函数生

成全部学生的成绩；

⑵ 编写一个平均成绩计算函数，计算每个同学的平均成绩并保存在成绩数

组中；

⑶ 用希尔排序法对 4 个班的成绩按每个同学的平均成绩的以非递增方式

进行班内排序；

⑷ 用堆排序法对 4 个班的成绩按每个同学的平均成绩的以非递增方式进

行班内排序；

(5) 用快速排序法对 4 个班的成绩按每个同学的平均成绩的以非递增方式

进行班内排序；

(6) 用基数排序法对 4 个班的成绩按每个同学的平均成绩的以非递增方式

进行班内排序；

⑸ 设计一个菜单，至少具有上述操作要求的基本功能。

2.测试数据

由同学们自定。

19 / 43

13.运动会分数统计系统

1.问题描述

参加运动会有 n 个学校，学校编号为 1……n。比赛分成 u 个男子项目，和 w

个女子项目。项目编号为男子 1……u，女子 u+1……u+w。不同的项目取前五名

或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：

5、3、1；哪些取前五名或前三名由学生自己设定。（u<=20,w<=20）

2.基本要求

(1)可以输入各个项目的前三名或前五名的成绩；

(2)能统计各学校总分，

(3)可以按学校编号、学校总分、男女团体总分排序输出；

(4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前

三或前五名的学校。

规定：输入数据形式和范围：20 以内的整数（如果做得更好可以输入学校的

名称，运动项目的名称）

输出形式：有中文提示，各学校分数为整型

界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相

关的功能要求。

存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数

据要存储在数据文件中。（数据文件的数据读写方法等相关内容在 c 语言程序设

计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；

3.测试数据

要求使用 1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程

序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

20 / 43

14.停车场管理系统

1．问题描述

利用堆栈和队列实现一个停车场管理系统；

设停车场是一个可以停放 n 辆汽车的狭长通道，且只有一个大门可以供车辆

进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到

达的第一辆车放在停车场的最里面）。如果停车场已放满 n 辆车，则后来的车只

能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一

辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必

须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。

每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留

在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在

便道上等待的车辆次序。

2．基本要求

编制一程序模拟该停车场的管理。车辆的信息包括：汽车到达/离去标志、

车牌号、到达/离去时刻等。按照从终端读入的数据序列进行模拟管理。每辆车

需要三个数据，其中车辆数据为：A 表示到达，D 表示离去，E 表示程序结束。

假设车辆牌照为整型数据，进场或离场时间同样为整型数据。对每一组输入数据

进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停

车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在

便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。

停车场管理系统主要实现以下几个功能：

(1)根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。

(2)该程序设计能够通过车牌号查到该车辆在停车场或便道中的位置。

(3)当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。实现停车

场的调度功能。

3．测试数据

假设 n=2 或者 3（可以自己设置测试数据）

（A，1，5）

21 / 43

（A，2，10）

（D，1，15）

（A，3，20）

（A，4，25）

（A，5，30）

（D，2，35）

（D，4，40）

（E，0，0）

4．实现提示

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，

也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示

一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。