算法设计题目

算法设计题1.最大子段和给定由n个整数组成的序列(a1,a2,…,an)，求该序列形如(i=1,2,3,…n;j=1,2,3…n)的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.填自然数：设有如图所示的3n＋2个球互连，将自然数1－3n＋2分别为这些球编号，使如图相连的球编号之差的绝对正好是数列1，2，……，3n+2中各数。②─⑥②─⑨─⑤②─⑿─⑤─⑨│││││││││①─⑧─④─⑤①─⑾─④─⑧─⑦①─⒁─④─⑾─⑦─⑧│││││││││③─⑦(n=2)③─⑩─⑥(n=3)③─⒀─⑥─⑩(n=4)3.多段图问题设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一条边(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。4.15谜问题在一个4×4组成的十六宫格棋盘上，摆有十五个牌，刻有1-15中的某一个数。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。121589512671314111034初始状态123456789101112131515目标状态5.电路布线问题印刷电路板将布线区域划分成n×n个方格。精确的电路布线问题要求确定连接方格a到方格b的最短布线方案。在布线时，电路只能沿着直线或直角布线，也就是不允许线路交叉。jikka6.最小生成树问题设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树。要求至少要有Prim(或者加上Heap优化)和Kruska算法。7.装箱问题有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。8.最短路径给定带权有向图G＝(V,E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。9.五皇后问题在标准的8*8国际象棋棋盘上,每个皇后可以吃掉横线,直线,斜线上的任意一个棋子.现在给5个皇后放置在棋盘上规定：1、5个皇后彼此不能攻击！2、在棋盘上在放任何一个棋子都会被攻击！即：用五个皇后占领整个棋盘！设计一算法求出满足以上条件的所有可能的分布总数。10.马踏棋盘将马随机放在国际象棋的8*8棋盘Bord[8Ⅱ8]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。要求设计算法求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。可自行指定一个马的初始位置。11.背包问题给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为pi，装包时物品可拆，即可只装每种物品的一部分。显然物品i的一部分放入背包可产生的效益为xipi,这里，0≤Xi≤1，Pi0。背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?(要求使用分支限界法和动态规划法求解)12.哈密尔顿回路设G=V,E,W，为一个n阶完全带权图Kn，各边的权非负，且有的边的权可能为∞.求G中一条最短的哈密顿回路.13.八枚硬币问题在八枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计高效的算法来检测出这枚假币。14．最大团问题给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。下图G中，子集{1，2}是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图{1，2，5}包含。{1，2，5}是G的最大团。{1，4，5}和{2，3，5}也是G的最大团。15.流水作业调度n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。16.活动安排问题设有n个活动的集合E={a1,a2,…,an}，其中每个活动都要求使用同一资源（如演讲会场），而在同一时间内只有一个能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题要求在所给的活动集合中选出最大的相容活动子集。17.最长公共子序列问题对给定序列X=(x1,x2,…,xm)和序列Z=(z1,z2,…,zk)，Z是X的子序列当且仅当存在一个严格递增下标序列(i1,i2,…,ik)，使得对于所有j=1,2,…,k，有zj=xij（1≤ij≤m）。给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列问题就是在序列X和Y的公共子序列中查找长度最长的公共子序列。要求：（1）各个问题至少用两种算法完成。（2）要求分析各算法的效益。（3）提交完整的算法程序（4）所有题目均以论文形式提交。（5）最后一周进行课堂答辩。