课程设计内容

1、算法设计与分析课程设计内容1 .马的Hamilton周游路线问题问题描述：8 x 8的国际象棋棋盘上的一只马，恰好走过除起点外的其他63个位置各一 次，最后回到起点。这条路线称为马的Hamilton周游路线。对于给定的m x n的国际象棋棋 盘，m和n均为大于5的偶数，且m - nk 2，试设计一个分治算法找出马的一条Hamilton 周游路线。设计任务：对于给定的偶数m，n 6且Im - n| 2，设计算法并验证算法的正确性， 编程计算m x n的国际象棋棋盘上马的一条Hamilton周游路线。设计要求：程序运行结束时，将计算出的马的Hamilton周游路线用下面的2种表达方 式输出。第一种

2、表达方式按照马步的次序给出马的Hamilton周游路线。马的每一步用所在的方 格坐标（x, y）来表示，X表示行坐标，编号为0,1,，m - 1 ； y表示列坐标，编号为0,1,，n -1。起始方格为（0,0）。第二种表达方式在棋盘的方格中标明马到达该方格的步数。（0,0）方格为起跳步，并标 明为第1步。排列的字典序问题问题描述：n个元素1,2,., n有n!个不同的排列。将这n!个排列按字典序排列，并 编号为0,1,., n !-1。每个排列的编号为其字典序列。例如，* = 3时，6个不同排列的字 典序值如下：字典序列012345排列123132213231312321设计任务：给定n以及n

3、个元素1,2,., n的一个排列，计算出这个排列的字典序值， 以及按字典序排列的下一个排列。圈乘运算问题问题描述：对于给定的十进制整数X和K，由X和运算可以组成各种不同的表达 式。试设计一个算法，计算出由X和运算组成的值为K的表达式最少需用多少个运算。关于整数的二元圈乘运算定义为：（XY ）=十进制整数X的各位数字之和x十进制整数Y的最大数字+ Y的最小数字例如：（9 30 ）= 9 x 3 + 0设计任务：对于给定的十进制整数设计任务：对于给定的十进制整数X和K，1 X , K 10 20，试设计一个有效算法，编程计算由X和运算组成的值为K的表达式最少需用多少个运算。有向树k中值问题问题描述

4、：给定一棵有向树T，树T中每个顶点u都有一个权叭u ），树的每条边（u , v） 也都有一个非负边长d （u , v）。有向树T的每个顶点u可以看作客户，其服务需求量为叭u ）。 每条边（u , v）的边长d （u , v）可以看作运输费用。如果在顶点u处未设置服务机构，则将顶点 u处的服务需求沿有向树的边（u , v）转移到顶点v处服务机构需付出的服务转移费用为 叭u ） . d （u , v）。树根处已设置了服务机构，现在要在树T中增设k处服务机构，使得整棵 树T的服务转移费用最小。设计任务：对于给定的有向树T，试设计一个有效算法，编程计算在树T中增设k处服 务机构的服务转移费用最小。套汇

5、问题问题描述:套汇是指利用货币兑换率的差异将一个单位的某种货币转换为大于一个单位 的同种货币。例如，假定1美元可以买0.7英镑，1英镑可以买9.5法郎，且1法郎可以买到 0.16美元。通过货币兑换，一个商人可以从1美元开始买入，得到0.7 x 9.5 x 0.16 = 1.064 美元，从而获得6.4%的利润。设计任务：对于n种货币c 1, C2,., c的有关兑换率，试设计一个有效算法，用以确定 是否存在套汇的可能性。非单位时间任务安排问题问题描述：具有截止时间和误时惩罚的任务安排问题要描述如下。（1）给定n个任务的集合S = 1,2, . , n；（2）完成任务z需要t时间，1 i n ；

6、（3）任务i的截止时间d，1 i n，即要求任务i在时间d之前结束；（4）任务i的误时惩罚w，1 i n，即任务i未在时间dZ前结束将招致w的惩罚; 若按时完成则无惩罚。任务安排问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。设计任务：给定的n个任务，编程计算总误时惩罚最小的最优时间表。运动员最佳配对问题问题描述：羽毛球队有男女运动员各n人。给定2个n x n矩阵P和Q。P z j是男 运动员Z和女运动员j配对组成混合双打的男运动员竞赛优势；Q i j是女运动员j和男 运动员Z配对组成混合双打的女运动员竞赛优势。由于技术配合和心理状态等各种因素影 响，P i j不一定等于Q i

7、 j。男运动员i和女运动员j配对组成混合双打的男女双方竞 赛优势为P i j * Q i j。设计一个算法，计算男女运动员最佳配对法，使各组男女双方 竞赛优势的总和达到最大。设计任务：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对 法，使各组男女双方竞赛优势的总和达到最大。n色方柱问题问题描述：设有n个立方体，每个立方体的每一面用红、黄、蓝、绿等n种颜色之一染 色。要把这n个立方体叠成一个方形柱体，使得柱体的4个侧面的每一侧均有n种不同的颜 色。试设计一个回溯算法，计算出n个立方体的一种满足要求的重叠方案。设计任务：对于给定的n个立方体以及每个立方体各面的颜色，计算出n个立方体的一 种叠置方案，使得柱体的4个侧面的每一侧均有n种不同的颜色。最小权顶点覆盖问题问题描述：给定一个赋权无向图G = (V , E )，每个顶点v e V都有一个权值w3)。如果U c V，且对任意(u , v) e E有v e U，就称U为图G的一个顶点覆盖。G的最小权顶 点覆盖是指G中所含顶点权之和最小的顶点覆盖。设计任务：对于给定一个赋权无向图G = (V , E )，设计一个优先队列式分支限界法， 计算G的最小权顶点覆盖。行列变换问题问题描述:给定2个m x n方格阵列组成的图形A和每个方格的颜色为黑色或白色。 行列变换问