文档介绍：问题 1
在一个按照东西和南北方向划分成规整街区的城市里,n个居民点散乱地分布在不同的
街区中。用x 坐标表示东西向,用y 坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。
街区中任意2 点(x1 , y1)和(x2 , y2) 之间的距离可以用数值|x1 - x2|+ |y1 - y2|度量。
居民们希望在城市中选择建立邮局的最佳位置,使n个居民点到邮局的距离总和最小。
对于给定的n个居民点的位置,设计一个法,计算邮局的最佳位置,使n个
居民点到邮局的距离总和最小。要求算法时间复杂度越低越好
问题2
若给定序列X={x1,x2,…,xm},则另一序列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
一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。
给出N,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。
问题4
问题描述
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
问题5
问题描述
对于给定的平面上的n 个点和连接这n个点的m条边,每条边连接2 个点。找出给定的m 条边的一条首尾相接的回路,使得从任何给定点出发沿此回路可以经过m 条边的每条边恰好1 次又回到出发点。
问题6
校园里有n台计算机,要将它们用数据线连接起来。连接2台计算机的费用与这2台计算机之间的直线距离成正比。如果将每2 台计算机都用数据线连接,势必造成浪费。为了节省费用,可以采用数据的间接传输手段,即一台计算机可以间接通过若干台计算机(作为中转)来实现与另一台计算机的连接。对于给定的n 台计算机及其位置坐标,计算连接n 台计算机的最少费用及连接方法。
问题 7
设有n个独立的作业{1,2,…,n},由m台相同的机器进行加工处理。作业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。有些数经过若干次倒置相加运算就成为一个回文数。