程序与算法综合设计课程设计指导书-2013(3)

例如（17，27，37...70，71，72，73...）

题7：布尔表达式（90分）

目的：本课程设计是求中缀算术表达式真值问题。求中缀算术表达式值的问题是数据结构中栈的一个典型应用。通过本题，学生应掌握中缀表达式和后缀表达式的转换方法和后缀表达式求值问题。 题目：布尔表达式真值问题

要求：已知某种类型的布尔表达式由“V”、“F”、“！”、“&”和“|”组成，其中，“V”代表真值True，“F”代表真值False，“！”代表逻辑非运算，“&”代表逻辑或运算。并且，运算符“！”、“&”和“|”的优先级为：“！”最高，“|”最低，“&”介于“！”和“|”之间。你的任务是，计算给定布尔表达式的真值。

例如，布尔表达式“(V|V)&F&(F|V)”的真值为“F”.

题8：谣言传播（90分）

目的：通过本课程设计，应使学生掌握如何用图结构解决实际问题的能力，加深对于图结构的理解和认识。掌握图的存储方法和关于图的经典算法。提高学生的程序设计能力。

题目：谣言传播问题

要求：股票经纪人往往对谣言很敏感，你老板希望你能找到一个好方法向他们散布谣言，从而使他在股市占有战术优势。为了达到最有效果，需要谣言传播的尽量快。不幸的是，股票经纪人只相信从他们信任的信源传播来的消息，因此，在你散布谣言之前，需要对他们的联系网进行详细考察。对于一个股票经纪人，他需要一定时间才能将信息传送给他联系人，给你这些信息，你的任务是，决定选谁作为第一个传送谣言的人，以使谣言传遍所有人的时间最短，当然，如果谣言不能传遍所有人的话，你也要给出说明。

例如，假设共有3个联系人，联系人1传递信息给联系人2和3所有的时间分别为4和5；联系人2传送信息给联系人1和3所有的时间分别为2和6；联系人3传送信息给联系人1和2所有的时间均为2，则选择联系人3作为第一个传送谣言的人，可以使谣言传遍所有的人时间最短，为2.

（选择有向图中的一个源点，使它到其余各顶点的最短路径中最长的一条路径最短）

题9：分形（95分）

目的：递归是基本的算法思想和设计方法之一，也是数据结构重点讲授的部分，是许多算法的基础，对它们的理解和运用直接关系着其他算法的理解和应用。因此，熟练掌握递归是十分重要的。通过本题，应使学生加深对于递归方法的理解，提高运用递归解决问题的能力。 题目：盒子分形

要求：分形是一种具有自相似性的现象，在分形中，每一组成部分都在特征上和

整体相似，只不过仅仅是缩小了一些而已，一种盒子分形定义如下： （1）规模为1的盒子分形为

X

（2）规模为2的盒子分形为 X X X X X

（3）若用B(n - 1)表示规模为n-1的盒子分形，则规模为n的盒子分形为 B(n - 1) B(n - 1) B(n - 1) B(n - 1) B(n - 1) 你的任务是，输出规模为n的盒子分形。例如，规模为3的盒子分形输出如下：

X X X X

X X X X X X X X X X X

X X X X

X X X X X X

题10：网络布线(95分)

计算机网络要求网络中的计算机被连接起来，本问题考虑一个“线性”的网络，在这一网络中计算机被连接到一起，并且除了首尾的两台计算机只分别连接着一台计算机外，其它任意一台计算机恰连接着两台计算机。图1中用圆点表示计算机，它们的位置用直角坐标表示。网络连接的计算机之间的距离单位为英尺。

由于很多原因，我们希望使用的电缆长度应可能地短。你的问题是去决定计算机应如何被连接以使你所使用的电缆长度最短。在设计方案施工时，电缆将埋在地下，因此连接两台计算机所要用的电缆总长度等于计算机之间的距离加上额外的16英尺电缆，以从地下连接到计算机，并为施工留一些余量。

下图是计算机的最优连接方案，这样一个方案用电缆的总长度是 (4 + 16) + (5 + 16) + (5.38 + 16) + (11.18 + 16) = 90.01英尺

编程要求：

基本要求：

输入网络中的计算机总数和每台计算机的坐标。

输出使电缆长度最短的连接方案。给出最优连接方案中每两台相邻计算机之间的距离，以及总的电缆长度。

提高要求：

参考图2，用图形化的方式显示结果，包括点的坐标、最优路径、相邻计算机之间的距离。

题11：数独游戏

在一个9×9的大正方形中，包含9个3×3的小正方形。如图3所示。可以看到，其每行、每列、每个小正方形，都有9个空格。

要求只用1到9这些数字，填满大正方形中所有的81个空格，同时满足： （1）在每列的9个空格中分别填入1到9，且每个数字在此列中只能出现一次； （2）在每行的9个空格中分别填入1到9，且每个数字在此行中只能出现一次；

（3）在每个小正方形的9个空格中分别填入1到9，且每个数字在此正方形中只能出现一次；

游戏一开始会给定了某些空格的值。参加游戏的人根据这些已知的值以及上面的约束条件，推理出剩余的空格的值。

数独题目示例

解题结果

编程要求：

层次一：只编写“数独计算器”

显示一个空白的9×9大正方形，请玩家自己输入要求解的题目，然后系统帮助玩家解答。

层次二：加入“数独题目生成器”

系统自动生成数独题目，玩家进行解答，系统可判定玩家答案的正确性。玩家也可以查看解答。

层次三：附加要求

在层次二的基础上，可以让玩家选择题目难度，生成不同难度级别的数独题目；可以设置提示功能，在玩家解题过程中帮他提示错误或给出若干空格的解答；可以根据题目难度和解题时间，对玩家的水平进行打分；

题12：中国邮路问题：

邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。 R14R1313

房屋11 房屋R1512

3房屋15R10 R94房屋房屋1117R12 R11房屋房屋105R5 房屋8135R66 房屋7R4房屋R7房屋 R898房屋7

127 房屋房屋房屋R2R3R1

编程要求：

层次一：只求解用户输入的图形的中国邮路问题

要求用户输入图形，求解输入的图形的中国邮路问题，要求能显示图形和最终结果。

层次二：加入图形编辑器 系统自动生成图形，系统求解生成的图形的中国邮路问题，要求能显示图形和最终结果。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库程序与算法综合设计课程设计指导书-2013(3)在线全文阅读。