算法设计与分析五邑大学.ppt

17. 折纸留痕问题 问题描述： 给你一张大矩形纸，连续从右向左对折纸n次形成一个纸条。现在把这个纸条小心地沿着折痕连续打开，使得折痕连接的两个面保持垂直，这时从纸的一端沿着和纸面平行的方向看去，会看到一条美妙的画面。快写个程序把这样的画面绘制出来！ 递归与分治算法！ ？ ？ 18. 三色凸多边形问题 问题描述： 有一个凸n边形，用红、绿、蓝对它的所有顶点进行染色，使得相邻顶点不同色，而且三种颜色都用过。请给出这个多边形一种三角剖分方案，使得每个三角形的三个顶点都不同色。 递归与分治算法！ ？ ？ 19. 超长数字串问题 问题描述： 给定一个数字串S:12345678910111213141516171819202122232425262728293031… 它是由所有自然数从小到大依次排列起来的。任意一个数字串S1一定在S中出现无穷多次。请你计算S1在S中首次出现的位置。 递归与分治算法！ ？ ？ 20. 彩球问题 问题描述： 有n个人，每个人任意从编号为1到n的n个彩球中拿走一个彩球，你知道剩下的那个彩球的编号吗？你有权利每次询问第i个人他的彩球编号的右数第j个二进制位dij是几，他会正确回答你的。你能用最少的询问次数来确定最后一个彩球的编号吗？ 递归与分治算法！ ？ ？ 21.月亮之眼问题 问题描述：很早以前，在佛教圣地某庙宇的一根大立柱上，镶嵌着一串用银白色和黛黑色各染一半的金线串接起来的、由n颗珍珠组成的、谓之“月亮之眼”的圣物。由于所有珍珠以及它们之间的金线在柱子上形成一条与地面垂直、与柱子平行的直线；可能会有两个珍珠镶嵌在同一地方；可能会有两根金线重叠摆放，所有使得圣物很美丽壮观。可是有一天，圣物突然脱落遗失，几千年后，一个古董商人得到了圣物，他出于对佛的虔诚，把圣物送回圣地。圣地的僧人想恢复圣物的原状，可他们怎么都无法把圣物原样地镶嵌在柱子上。你能帮助他们吗？ 递推 问题示例： 珍珠编号 1 2 3 4 5 6 7 8 9 白色金线 1 2 2 4 5 5 6 7 9 黑色金线 2 3 7 5 6 9 7 8 8 金线长度 3 5 1 4 1 1 1 3 4 6 1 2 3 7 8 9 5 4 5 1 1 1 1 4 4 3 3 6 1 2 3 7 8 9 5 4 1 1 1 3 2 2 22.丢失的正整数数列问题 问题描述：数学老师给全班同学写了一个包含n个正整数的递增数列，要求大家回家后同样按照递增的次序，写出所有的、任意两个数的和。有个同学很快就写完了作业。可是他出去玩了一会，回来后发现老师给的原始数列丢失了。你能帮他找回来吗？ 递推 22.丢失的正整数数列问题 问题分析：假设这个同学丢失的正整数递增数列是： a1,a2,a3,a4,…,an 他写出的结果包含了n(n-1)/2个数，它们由小到大是： k1,k2,k3,k4,… !!! a1+a2=k1, a1+a3=k2 a2+a3= ??? 假设 a2+a3=kx , 则解方程可得：a1,a2,a3 依次递推计算写出每个ai 22.丢失的正整数数列问题 例题：假设K={4,5,7,10,11,12,13,13,14,19}，求 a1,a2,a3,a4,… 解：因为 a1+a2=4, a1+a3=5 a2+a3 是K中的哪一个数呢？a1,a2,a3 因为只有a1+ai 可能比a2+a3小，所以a2+a3 是K中的序号一定在3到(n+3)之间！ 由于a2+a3＜ (a1+ a2)+(a1+a3)=k1+k2，（据此可以提高枚举的速度！）所以 a2+a3=7. 于是 a1=1，a2=3，a3=4 从K中删掉这三个数的和有K={10,11,12,13,13,14,19} ， 于是，进一步递推有a1+a4=10, 所以a4=9。 从K中删掉由于a4产生的和有K={11,13,14,19} ， 同样进一步递推有a1+a5=11, 所以a5=10。 从K中删掉由于a5产生的和有K={} ，所以 A={1,3,4,9,10} ! 23.电气工程师的烦恼 问题描述：电气工程师们刚为学校计算机大楼布好网线，结果发现，在入口处已经明确标记了各条网线的编号是1,2,3,…,n，但到了机房，这n条网线的顺序全乱了。为了知道这些网线的对应关系，他们测得网线中途有许多相互交叉的现象，而且两条线最多交叉一次。你如果知道了所有网线的交叉信息，能够帮他们找到这n条网线在机房的排列顺序吗？ 1 2 3 4 5 1 2 3 4 5 23.电气工程师的烦恼 问题分析：以各条网线的编号1,2,3,…,n为顶点构造一个有向图。若 ij同时i与j不相交，则