资源描述：
《计算机算法课程设计问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、问题1在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2点(x1,y1)和(x2,y2)之间的距离可以用数值
2、x1-x2
3、+
4、y1-y2
5、度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。对于给定的n个居民点的位置，设计一个法，计算邮局的最佳位置，使n个居民点到邮局的距离总和最小。要求算法时间复杂度越低越好问题2若给定序列X={x1,x2,…,xm}，则另
6、一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。要求：算法执行的速度越快越好。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。问题3一辆汽车加满油后
7、可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。问题4问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?问题5问题描述对于给定的平面上的n个点和连接这n个点的m条边，每条边连接2个点。找出给定的m条边
8、的一条首尾相接的回路，使得从任何给定点出发沿此回路可以经过m条边的每条边恰好1次又回到出发点。问题6校园里有n台计算机，要将它们用数据线连接起来。连接2台计算机的费用与这2台计算机之间的直线距离成正比。如果将每2台计算机都用数据线连接，势必造成浪费。为了节省费用，可以采用数据的间接传输手段，即一台计算机可以间接通过若干台计算机(作为中转)来实现与另一台计算机的连接。对于给定的n台计算机及其位置坐标，计算连接n台计算机的最少费用及连接方法。问题7设有n个独立的作业{1,2,…,n}，由m台相同的机器进行加工处理。
9、作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。问题8若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。问题9回文问题试设计一个算法测试一个串t的值是否为回文，即正读和倒读相同。给定一个k进制数a，其倒置相加运算⊕是将a的各位数字倒置后再与a相加。例如，当a=56时，⊕a=56+65=121。有些
10、数经过若干次倒置相加运算就成为一个回文数。例如，56经过1次倒置相加运算就变成回文数121。给定一个k进制数a，设计一个算法计算最少经过多少次倒置相加运算，a变成回文数。问题10DNA排序问题对于给定的全序集中排序元素序列，元素的逆序数定义为。序列A的逆序数定义为：。事实上，序列A的逆序数刻画出序列A中元素已排序的程度。逆序数越小，序列A已排序的程度就越高。当序列A已排好序时，其逆序数为0。生物信息学家在进行分子计算研究DNA序列时需要将若干长度相同的DNA串按其逆序数从小到大排序。例如，给定6个长度为10的D
11、NA串：AACATGAAGG，TTTTGGCCAA，TTTGGCCAAA，GATCAGATTT，CCCGGGGGGA，ATCGATGCAT，按其逆序数从小到大排序为：CCCGGGGGGA，AACATGAAGG，GATCAGATTT，ATCGATGCAT，TTTTGGCCAA，TTTGGCCAAA。DNA排序问题就是要对给定的长度相同的DNA串按逆序数排序。对于给定的长度相同的DNA串，设计算法使其逆序数从小到大排序。问题11荷兰国旗问题对于给定的仅由红，白，蓝3种颜色的条块组成的条块序列，要求将这些条块按照红，
12、白，蓝的顺序排好。排序时只允许交换2个条块的位置。荷兰国旗问题要对给定的序列，计算完成排序任务需要的最少交换次数。对于给定的仅由红，白，蓝3种颜色组成的条块序列，计算完成排序任务需要的最少交换次数。问题12一笔画问题对于给定的平面上的n个点和连接这n个点的m条边，每条边连接2个点。一笔画问题：找出给定的m条边的一条首尾相接的回路，使得从任何给定点出发沿此回路可以经过m条边的每条边恰好1
