软件工程课程实习题目

软件工程课程实习题目

1、 设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：

（1） 每个选手必须与其他n-1个选手各赛一次。 （2） 每个选手一天只能赛一次。

（3） 当n是偶数时，循环赛进行n-1天。当n是奇数时，循环赛进行n天。

2、 考虑国际象棋棋盘上某个位置的一只马，它是否可能只走63步，正好走过除起点外的

其他63个位置各一次？如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。试设计一个程序输出这样的一条马的周游路线。

3、 Gray码是一个长度为2n的序列。序列中无相同元素，每个元素都是长度为n位的串，

相邻元素恰好只有一位不同。设计一个程序实现对任意的n构造相应的Gray码。

4、 多边形游戏问题是1998年国际信息学奥林匹克竞赛试题。该游戏是一个单人玩的游戏，

开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。 游戏的地一步，将一条边删除。随后n-1步按以下方式操作： （1） 选择一条边E以及由E连接着的两个顶点V1和V2；

（2） 用一个新的顶点取代边E以及由E连接着的两个顶点V1和V2。将由顶点V1

和V2的整数值通过边E上的运算得到的结果赋予新的顶点；

（3） 最后，所有边都被删除，游戏结束。 游戏的得分就是所剩顶点上的整数值。

5、 在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只

能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个程序，计算出将n堆石子合并成一堆的最小得分和最大得分。

6、 商店中每种商品都有标价。例如：一朵花的价格是2元，一个花瓶的价格是5元。为了

吸引顾客，商店提供了一组优惠商品。优惠商品是把一种或多种商品分成一组，并降价销售。例如：3朵花的价格不是6元而是5元。2个花瓶加1朵花的优惠价格是10元。试设计一个程序，计算出某个顾客所购商品应付的最少费用。

7、 n个作业{1，2，3，??，n}要在有2台机器M1和M2组成的流水线上完成加工。每

个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业j所需要的时间分别为 Aj和Bj，1 <= j <= n 。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需要的时间最少。

8、 长江游艇俱乐部在长江上设计了n个游艇出租站1，2，3，??，n 。游客可在这些游

艇出租站用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j 之间的租金为R( i , j ) ，1<= i < j <= n 。试设计一个程序，计算出从游艇出租站 i 到游艇出租站j所需的最少租金。

9、 哈夫曼编码是用于数据文件压缩的一个十分有效的编码方法。设计一个哈夫曼编码的生

成树模拟演示程序。 10、 给定一个n为正整数A ，去掉其中任意K<=n 个数字后，剩下的数字按原次序排

列组成一个新的正整数。对于给定的n位正整数A和正整数K，设计一个程序找出剩下数字组成的新数最小的删数方案。 11、 在黑板上写了n个正数组成的一个数列，进行如下操作：每一次擦去其中两个数设

为A和B，然后在数列中加入一个数 A*B+1，如此下去直至黑板上只剩下一个数。在所有按这种操作方式最后得到的数中，最大的数记为Max ，最小的数记为Min ，则该

数列的极差M=Max-Min 。对于给定的数列，设计一个程序计算出极差M 。 12、 套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同

种货币。例如：假定1美元可以买0。7英镑，1英镑可以买9。5法郎，切1法郎可以买0。16美元。通过货币兑换，一个商人可以从1美元开始买入，得到0。7*9。5*0。16=1。064美元，从而获得6。4%的利润。

假设已知n种货币C1,C2,??，Cn和有关兑换率的N*N表R。最小重量机器设计问题。设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设W ij是从供应商j处购得的部件I的重量，Cij是相应的价格。试设计一个程序，输出总价格不超过C的最小重量机器设计。 13、 运动员最佳配对问题。一羽毛球队有男女运动员各n个，给定2个N*N矩阵P和

Q。p[I][j]是男运动员I和女运动员j配对组成混合双打时的竞赛优势；Q[I][j]是女运动员I和男运动员j配合时的竞赛优势。显然，由于技术的配合和心理状态等各种因素的影响，P[I][j]不一定等于Q[j][I]。设计一个程序，计算出男女运动员的最佳配对法，使各组男女双方竞赛优势乘积的总和达到最大。 14、 排列宝石问题。设有n种不同的颜色，同一种形状的n颗宝石分别具有这n种不同

的颜色。现有n种不同形状的宝石共n2颗，欲将这n2颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个程序计算出对于给定的n有多少种不同的宝石排列方案。 15、 工作分配问题。设有n件工作要分配给n个人去完成。将工作I分配给第j 个人所

需的费用为Cij 。试设计一个程序，为每一个人都分配1件不同的工作，并使总费用达到最小。 16、 世界名画陈列馆问题。世界名画陈列馆由m*n个陈列室组成。为了防止名画被盗，

需要在陈列室中设计警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的程序，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。 17、 在计算机上实现“海战”游戏。游戏的规则是：游戏中有两个对手（分别是玩家和

计算机），游戏是在两块完全相同的棋盘（）上进行的，两个对手分别在各自的棋盘上放置他们的战舰，当然对手是看不见的。每一个对手都有5艘战舰，每艘战舰都在棋盘上占据一定数量的格子：一艘驱逐舰（2格）、一艘潜艇（3格）、一艘战列舰（4格）、一艘航空母舰（5格）。每艘舰船即可以横放也可以竖放，但任意两舰不能互相接触。游戏的玩法是：双方轮流“轰炸”对方的战舰。每次轰炸的结果是击中还是未击中都会显示出来。如果击中的话，该玩家就可以继续攻击，直到击不中为止。游戏的目标是赶在对手之前把他所有的战舰击沉（要击沉一艘战舰，该战舰的所有格子都必须被命中）。 18、 翻薄饼：有n张大小互不相同的薄饼，一张叠在另一张的上面。允许大家把一个翻

板插到一个薄饼下面，然后可以把板上面的这叠薄饼翻个身。我们的目标是根据薄饼的大小重新安排它们的位置，最大的饼要放在最下面。设计一个算法来解这个谜题。 19、 对于一块n*m的巧克力，我们要把它分成n*m块1*1的小块。我们每次只能沿直线

分割，而且每次只能分割一块。设计一个解决该问题的算法，使得分割的次数最少。

本文来源：https://www.bwwdw.com/article/ax0d.html