《算法设计与分析五邑大学》由会员分享，可在线阅读，更多相关《算法设计与分析五邑大学（50页珍藏版）》请在金锄头文库上搜索。
1、算法设计问题示例计算机科学的本质是算法计算机硬件系统仅仅是依照特定的算法， 按照物理和电子学原理，采用特定的工艺流程生产的 一种电子计算装置计算机程序设计语言是仅仅是程序员 与计算机硬件系统进行沟通、交流的 一种工具语言 熟练掌握一种程序设计语言是成为一名优秀程序员的基础要成为一名优秀的、能够解决各类疑难问题的 程序员 必须具有良好的算法设计的品质1. 中国象棋中马的走法问题描述：在45的棋盘上已知马的起始坐标(x,y)，求马能够返回到起始位置的不重复的所有不同走法的总数 。回 溯 法！ 马当前所在的位置是当前扩展结点！每个活结点可能有八个孩子结点！如何记录马行走的路径？152643class
2、 Horse private:int chess56;int d28=(1,2,2,1-1,-2,-2,-1),(2,1,-1,-2,-2,-1,1,2);int sx,sy;int count; public:Horse(int x,int y) sx=x; sy=y;for(int i=0;i=6|sy=5) return ;backtrack(sx,sy);return count; Private static void backtrack(int p1,int p2); ;Private static void Horse: backtrack(int p1,int p2)int p
3、i,pj;for(int i=0;i=0 int m=new int m+1n+1;for(int i=1; i=n; i+) mii-1=0;for(int i=1; i=n; i+) mii=1;for(int r=2; i=n; r+)for(int i=1; i=n-r+1; i+) int j=i+r-1; mij=MaxINT;if(xi=(if(xi=( | xi=)mij=min(mij, mi+1j)+1;if(xj=) | xj=)mij=min(mij, mij-1)+1;for(int k=i; kj; k+)mij=min(mij, mik+mk+1j)return
4、m1n; 3. 棋盘的最优分割问题描述：一个88的棋盘中每个格子里均有一个分值。对棋盘沿着任意 一条格子线进行一次分割，将使棋盘成为两块矩形棋盘。给定n15，对原棋盘进行n-1次分割，就把棋盘分割成了n块矩形棋盘 。一块矩形棋盘的总分是他的所有格子的分值之和。请设计算法，给出把原棋盘分割成n块矩形棋盘的方案，使得各矩形棋盘总分 的平方和 最小。其中xi是第i块棋盘的总分。动态规划！x1,y1x2,y2ab3. 棋盘的最优分割假设左上角为(x1,y1)、右下角为(x2,y2)的棋盘的总分为： sx1,y1,x2,y2， 被切割k次后得到的k+1块矩形的总分平方和的最小值是：dk,x1,y1,x2
5、,y2则： dk,x1,y1,x2,y2=minmin dk-1, x1, y1, a, y2+ sa+1, y1, x2, y2,dk-1, a+1, y1, x2, y2+ sx1, y1, a, y2 (x1ax2) ,min dk-1, x1, y1, x2, b+ sx1, b+1, x2, y2,dk-1, x1, b+1, x2, y2+ sx1, y1, x2, b (y1by2) ,我们最终需要的是：dn11884. 多边形游戏问题描述：a任意画了一个凸n边形，并任意对其n个顶点进行1到n 的编号。A又再这个多边形上画了m条不会相交于多边形内部的弦 。现在a以(i, j)的方
6、式把这n条边和m条弦告诉给b，让b说出n边形的 n个顶点的编号顺序。其中(i, j)是编号为i、j的两个顶点之间的一条 边或者弦。问题分析： “m条不会相交与多边形内部的弦”表明：a画的n边形中 至少有两个顶点不是任何弦的端点，而交于这个顶点的必定是多边 形的边。这样的顶点的度为2！算法： 1.求出所有度为2的顶点； 2.当存在度为2的取出一个度为2 的顶点s，以s为端点的边是(s,u) 和(s,v)； 2.从边集中删除这两个边，并标记或补充补充标记虚边(u,v)；示例： n=8,m=5 13条直线是 ： (1,5) (5,2) (2,7) (7,6) (6,4) (4,8) (8,3) (3
7、,1) (2,3) (2,8) (7,4) (5,3) (2,4)64728 351138467255. 分离英文单词问题描述：长度为n的双重单词串是一个由小写英文字母组成的字 符串，它至少存在两种分离单词的方法，每种方法都能形成一组正 确的单词排列，并且两种方法中不会出现相同的单词；同一单词不 会重复出现；一个单词在一种方法中的结束位置不会与某个单词在 另一种方法中的结束位置相同（单词串结束例外）。给定包含m个单词的单词表，是否能够从中选择出若干个单 词，组成一个长度为n的双重单词串。示例：n=17, m=14 all,an,and,are,area,as,ask,at,data,last,
8、or,read,real,task双重单词串是： andatareallastask5. 分离英文单词问题分析：字母表是否存在两个不相交的子集A和B，他们中所有 单词的长度之和均等于n？No： 不存在长度为n的双重单词串！Why?Yes： 的长度为n的双重单词串的构造算法。等量0-1背包问题分别由字母表的子集A和B中所有单词构造长度为n相同的两个字 符串，该字符串就是上的长度为n的双重单词串！030532085635230118an,ask,data,last,real as,at,and,all,are,taskananddat a at arerealalllastas taskask6.
9、 会餐交友问题问题描述：某机构举行一次不超过500人参加的盛大餐会，以增进 与会者之间的友谊。所以采取自助餐形式，客人可以自由走动、交 谈。由于客人中有些相互认识、有些相互不认识。为了让客人相互 引见，使大家都能认识更多的朋友，举办方想控制中途离开的客人 的人数。当客人离开太多时，就应该宣布餐会结束。问题是，最少 有多少客人离开后，剩下的客人两两彼此都不认识？输入示例： 8 1,2 1,3 2,4 7,6 4,3 5,6 0,0输入数据：n表示客人的个数，客人的编号依次是1,2,n。 i,j表示客人i和j相互认识；i=0int d=1;for(int i=1;i=b;i+)d=d*a mod
10、c;fmod=d;return fmod; 11. 最短表面距离问题问题描述：一个长方体P=(x,y,z)|0xL,0yW,0zH的 表面上有两个点A(x1,y1,z1)和B(x2,y2,z2)，求A与B之间的最短表面 距离。问题分析： 平面上两点之间的直线距离最短；球面上两点之间的最短距离？ 延伸： 此问题非平面亦非球面。转化：将长方体表面上的两点转化成平面上的两点 。区分： 1.两点在长方体的同一表面上；2.两点在长方体的两个相邻表面上；3.两点在长方体的两个相对表面上。11. 最短表面距离问题 1.A(x1,y1,z1)和B(x2,y2,z2)在长方体的同一表面上。 直接计算直线距离！2
11、.A(x1,y1,z1)和B(x2,y2,z2)在长方体的两个相邻表面上。 展开长方体；分三种情况；取小。 3.A(x1,y1,z1)和B(x2,y2,z2)在长方体的两个相对表面上。 展开长方体；分12种情况；取小。 12. 多花钱多卖鱼问题问题描述：现有资金m，想去购买n种鱼中尽可能多 的鱼，每种鱼只能购买一条。第i条鱼的价格是pi。 如果第i条鱼与第j条鱼相互斗食而不能共存，则这 两条鱼只能选择其一。写出能够计算出最佳买鱼方 案的算法。输入示例： 170 7 1 70 2 50 3 30 4 40 5 40 6 30 7 20 1 4 1 7 3 4 3 5 5 7 6 7 0 0输出示
12、例： 4 160 2 4 5 6这是一个什么问题？12. 多花钱多卖鱼问题问题分析： 这个问题有一些约束条件： 1.所买鱼的价格总和不能超过资金数m； 2.不能共存的鱼不能同时购买； 3.每种鱼最多买一条； 4.在满足上述条件的前提下，买尽可能多的鱼； 5.在满足上述条件的前提下，花尽可能多的买鱼钱。这是一个什么性质的问题？输入示例： 170 7 1 70 2 50 3 30 4 40 5 40 6 30 7 20 1 4 1 7 3 4 3 5 5 7 6 7 0 017025033044054063072013. 巧妙的剪纸问题问题描述： 有一张正方形的纸，用笔和直尺把它等分成mm个小 方
13、格，用彩笔选择任一小方格作为起点，任意地一笔画一条正好经 过了nn个小方格的彩线，把有彩线的小方格标记为*。我们的问 题是，你能够把所有标记为*的小方格从纸上全部剪下来在一张纸 片上,然后再把它分剪成两片纸，使得这两片纸经过旋转、翻转或 平移后可以拼成一个nn的正方形。* * * * * * AB B ABAB B B B AAAAAAAA AAAAAAABB BBBBB13.巧妙的剪纸问题问题分析：我们需要解决两个问题： 1.如何巧妙地将所有带*的纸剪成两片纸？ 2.这两片纸如何拼接成一个正方形？!所有的*是连通的。剪掉所有的空白纸，并记录横向或者纵向上*连续个数大 于n的直线坐标。从左到右
14、、从上到下找到第一个与空白纸相邻的*，从此 开始，按照右手规则剪掉所有的空白纸。! nn的正方形是由两片纸拼接成的。这两片纸中直线上 有连续n个*的情形可以分为几种？ ! 带*的纸片上连续超过n个*的直线是需要下剪子的。 13.巧妙的剪纸问题 !纸片的平移、旋转和翻转。对两张纸片分别进行矢量化处理。若取左上角方格的坐标 是(0,0)，则任意方格都有了相对坐标(x,y)。旋转(逆时针90。)：(x,y)(-y,x)。 翻转(上下)：(x,y)(x,-y)。 (左右)：(x,y)(-x,y)。平移：(x,y)(xd,yd)。 拼接：做一个nn的正方形模版。先把第一张纸片放进去，再 将第二张纸片经过有限次平移、旋转和翻转后放进去，若成功 ，则结束。14. 单轨砌积木问题问题描述： 有n个边长为1的正方体积木，要堆砌在一个无限长、 宽为1的水平轨道上，形成一个高度不超过m的积木堆： 1.水平方向上第一层积木之间不能分离； 2.积木的下面必须与轨道或另一个积木的上面完全接触； 3.若两种堆砌方案经翻转后形状一样，则认为他们是同一种方案。 试计算出所有的不同堆砌方案。这又是一个什么问题？这又是一个什么
