题目内容

最小生成树问题（限1 人完成）设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。

查看答案

搜索结果不匹配？点我反馈

更多问题

设计示例迷宫问题问题描述以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标,d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2）……测试数据迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。实现提示计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。选作内容（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。

农夫过河农民过河问题是指农民需要带一只狼、一只羊和一棵白菜到河的南岸去,需要安全运到北岸。而一条小船只能容下他和一件物品,只有农民能撑船。问农民怎么能安全过河,问题中需要涉及到狼会吃羊,羊会吃白菜,所以农民不能将这两种或三种物品单独放在河的一侧,因为没有农民的照看,狼就要吃掉羊,而羊可能又要吃掉白菜。这类问题的实质是系统的状态问题,要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。根据实际情况，对此问题分析可以得到不同的特征：一是农民和羊在河的南岸，狼和白菜在河的北岸；二是从一个状态可转到另外一个状态，而不违反狼吃羊，羊吃草的规则（例如农民自己过河或者农民带着羊过河）；三是有些状态是不安全的（例如农民一人在北岸，而其他的东西都在南岸）；四是初始状态是农民，羊，狼，白菜都在河的南岸和结束状态是农民，羊，狼，白菜都在河的北岸。实现农民过河问题，则需要找到一条合法的路径（相邻状态之间的转移合法），从开始状态到某个结束状态，路途中不能经过不安全的状态。二、实验目的概述(总体设计方案)a)利用图的有关知识来解决农民过河问题b)根据图的广度（深度）优先搜索来实现实验要求在实施此问题中，首先要为农民，狼，白菜和羊设置求状态的函数，若某一种物品在河的南岸，则返回0，若在河的的北岸，则返回1；其次是为每一种状态做测试，状态安全则返1，否则返回0。

城市链表[问题描述]将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。[基本要求]（1）给定一个城市名，返回其位置坐标；（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据。

约瑟夫生死者游戏[问题描述]约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。[基本要求]利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。[测试数据]m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。[实现提示]程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。[选作内容]向上述程序中添加在顺序结构上实现的部分