算法设计题目.doc

算法设计题 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中的某一个数。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。 这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 1 2 15 8 9 5 12 6 7 13 14 11 10 3 4 初始状态 1 2 3 4 5 6 7 8 9 10 11 12 13 15 15 目标状态5.电路布线问题 印刷电路板将布线区域划分成n×n个方格。精确的电路布线问题要求确定连接方格a到方格b的最短布线方案。在布线时，电路只能沿着直线或直角布线，也就是不允许线路交叉。 6. 最小生成树问题 设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，Pi 0。背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大? 要求使用分支限界法和动态规划法求解 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上