outline.htm

一些算法小技巧 有利于学习C语言 在C语言和JAVA中都可以用的

   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>信管系的同学回去学习框架和思想。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP31 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0081.htm');" onmouseover="Over(this)"
  id=PPTL31 onmouseout="Out(this)">补充 1.1 ：常见问题的类型</a></font></div>
  <div id=PPTC31 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB31 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>排序问题（Sorting）。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>搜索问题（Searching）。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>字符串问题（String problems）。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>图论问题（Graph problems）。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>组合数学问题（Combinatorial problems）。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>几何数学问题（Geometric problems）。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>数值计算问题（Numerical problems）。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>加密问题（Encrpytion problems）。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP32 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0085.htm');" onmouseover="Over(this)"
  id=PPTL32 onmouseout="Out(this)">1.2.1<span style="mso-spacerun: yes">&nbsp;
  </span>排序问题</a></font></div>
  <div id=PPTC32 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB32 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>所谓的“排序”就是把一组杂乱的数据按照一定的规律顺次排列起来。排序是很重要的，因为它可以使得以后的工作更加地容易。目前，计算机科学家发明了很多的排序算法，然而这些排序算法中并不存在一种算法是绝对最优的。这里介绍几个与“排序”相关的重要概念：数据表
    、关键字 、主关键字 、排序的稳定性 、内排序与外排序 。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP33 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0084.htm');" onmouseover="Over(this)"
  id=PPTL33 onmouseout="Out(this)">1.2.2<span style="mso-spacerun: yes">&nbsp;
  </span>搜索问题</a></font></div>
  <div id=PPTC33 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB33 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>所谓搜索，就是在数据集合中寻找满足某种条件的数据对象。一般的形式是先给出一个特定值，然后在数据集合中找出关键字等于该特定值的对象。对于搜索问题，通常需要返回的结果可能有两种。一种是简单的搜索成功或者失败的信息；另一种是返回满足搜索条件的对象所在位置，如果找不到则返回不存在信息。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP34 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0083.htm');" onmouseover="Over(this)"
  id=PPTL34 onmouseout="Out(this)">1.2.3<span style="mso-spacerun: yes">&nbsp;
  </span>字符串问题</a></font></div>
  <div id=PPTC34 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB34 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>对于字符串处理的问题，这里只是对其中一类特殊的问题进行讨论，即字符串模式匹配问题（string
    matching）。问题是这样表述的：在一篇文章或文章的一部分中找出单词第一次出现的位置。本书把字符串匹配问题作为一种特殊的搜索问题考虑，因为两者是有相似之处的。最大的区别在于，一般搜索问题是单一的关键字的搜索，而字符串匹配可以看作是几个关键字组成一种模式的搜索过程，因此对模式的分析有助于算法效率的提高。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP35 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0086.htm');" onmouseover="Over(this)"
  id=PPTL35 onmouseout="Out(this)">1.2.4<span style="mso-spacerun: yes">&nbsp;
  </span>图论问题</a></font></div>
  <div id=PPTC35 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB35 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>图论问题主要是与图或树相关的问题。这里所谓的“图”指的是一些顶点（Vertex）与边（Edge）的集合。图有着非常重要与丰富的实际应用，如通信网络，交通网络，工程计划等。本书所涉及到的图论问题主要包括了图的遍历问题（Graph
    Traversal），最短路径问题以及图的特例——树结构的排序、搜索中的应用问题。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP36 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0087.htm');" onmouseover="Over(this)"
  id=PPTL36 onmouseout="Out(this)">1.2.5<span style="mso-spacerun: yes">&nbsp;
  </span>组合数学问题</a></font></div>
  <div id=PPTC36 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB36 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>现代的组合数学所涉及的领域更加广阔，其中的问题出自抽象代数、拓扑学、数学基础、图论、博弈论、线性规划以及其他许多领域。值得注意的是，这些来源不同的问题不能在一个统一的理论体系中得到有效的解决，而且随着问题的输入量的增加，问题的规模急剧增长至计算机的处理能力的极限，所以可以说组合数学问题是最难的一类问题。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP37 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0088.htm');" onmouseover="Over(this)"
  id=PPTL37 onmouseout="Out(this)">1.2.6<span style="mso-spacerun: yes">&nbsp;
  </span>几何问题</a></font></div>
  <div id=PPTC37 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB37 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>几何问题是几何数学上与点、线、多边形相关的问题。当然，算法不是一本几何学的书，所以这里只会涉及如直线段的表示、相交判断等基本问题。同时还会给出最近邻点问题与凸包问题这两个重要问题的介绍。它们都有穷举法与分治法的算法，通过比较，可以深入体会到其中所用到的算法设计思想。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP38 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0089.htm');" onmouseover="Over(this)"
  id=PPTL38 onmouseout="Out(this)">1.2.7<span style="mso-spacerun: yes">&nbsp;
  </span>数值计算问题</a></font></div>
  <div id=PPTC38 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB38 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>数值计算问题是另一大类问题，它要解决的问题包括：求解方程或者方程组，求数值积分等。这些问题常常只能给出一个近似的结果，而不是精确的解析解。并且这些问题常涉及到具体的数据，由于计算机对数字表示的精度问题，所以还需要考虑可能带来的误差以及这些误差对算法稳定性的影响。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP39 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0090.htm');" onmouseover="Over(this)"
  id=PPTL39 onmouseout="Out(this)">1.2.8<span style="mso-spacerun: yes">&nbsp;
  </span>加密问题</a></font></div>
  <div id=PPTC39 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB39 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>加密问题是信息安全的基础，它要解决的问题包括：通信双方的相互鉴定，消息完整性的确定以及公开密钥的分发等。这些安全问题的解决方案依赖于加密算法的发展，如DES算法、RSA算法以及MD5算法都是目前广泛使用的加密算法。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP40 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0091.htm');" onmouseover="Over(this)"
  id=PPTL40 onmouseout="Out(this)">1.3<span style="mso-spacerun: yes">&nbsp;
  </span>解决问题的一般步骤</a></font></div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP41 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0092.htm');" onmouseover="Over(this)"
  id=PPTL41 onmouseout="Out(this)">1.3.1<span style="mso-spacerun: yes">&nbsp;
  </span>了解问题的内容</a></font></div>
  <div id=PPTC41 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB41 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>当遇到一个问题时，首先要清楚这个问题的所有内容。如果这个问题已经给出了明显的要求，如对成绩排序，那么只需要看看它是属于那一类的问题，然后参考相关的资料。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>了解问题内容这个步骤是十分重要的，因为只有知道了问题具有什么样的输入，需要得到什么样的输出，问题的解决才可能进行下去。理解了问题是问题求解的关键。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP42 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0093.htm');" onmouseover="Over(this)"
  id=PPTL42 onmouseout="Out(this)">1.3.2<span style="mso-spacerun: yes">&nbsp;
  </span>确定计算设备的能力</a></font></div>
  <div id=PPTC42 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB42 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>在清楚了解了问题的内容之后，下一步是确定用于解决问题的设备的能力。目前一般使用的计算机都是冯诺依曼（von
    Neumann）体系架构的。它的一个最重要假设是，程序指令的执行是顺序的。针对这一类计算机设计的算法被称为串行算法（sequential
    algorithms）。与之相区别的是所谓的并行计算机以及并行算法（parallel algorithms）。指令能够并行的执行，效率当然会大大提高，额外需要考虑的则是指令执行顺序以及同步等问题。并行算法的设计思想有自己相关的理论，这里仅考虑串行算法。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP43 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0094.htm');" onmouseover="Over(this)"
  id=PPTL43 onmouseout="Out(this)">1.3.3<span style="mso-spacerun: yes">&nbsp;
  </span>选择精确或者近似的算法</a></font></div>
  <div id=PPTC43 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB43 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>解决问题下一步要考虑的是使用精确的还是近似的算法。并不是每一个可解的问题都有精确的算法，例如求一个数的平方根，求非线性方程的解等。有时候一个问题有精确的解法但是算法的执行效率很差，例如旅行家问题。因此如果待处理的问题涉及到上述那些方面，则要考虑是选择精确的还是近似的算法。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP44 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0095.htm');" onmouseover="Over(this)"
  id=PPTL44 onmouseout="Out(this)">1.3.4<span style="mso-spacerun: yes">&nbsp;
  </span>确定合适的数据结构</a></font></div>
  <div id=PPTC44 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB44 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>许多程序设计的教程都提到：程序设计＝算法＋数据结构（Programs = Algorithms
    + Data Structures），由此可以看出数据结构对算法的重要性。例如在处理搜索问题时，对于仅仅进行搜索的算法只需要用到简单的数组即可，如果搜索后伴随着插入删除操作时，那么用链表以及堆等复杂的数据结构的算法更加可取。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP45 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0096.htm');" onmouseover="Over(this)"
  id=PPTL45 onmouseout="Out(this)">1.3.5<span style="mso-spacerun: yes">&nbsp;
  </span>选择算法设计技术</a></font></div>
  <div id=PPTC45 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB45 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>算法设计技术（algorithm design technique）或者算法设计策略（strategy）指的是解决一系列不同问题的通用设计思想。常用的设计技术包括分治法（Divide
    and Conquer），贪婪法（Greedy Technique），动态规划（Dynamic Programming），回溯法（Backtracking），分支限定法（Branch
    and Bound）等。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP46 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0097.htm');" onmouseover="Over(this)"
  id=PPTL46 onmouseout="Out(this)">1.3.6<span style="mso-spacerun: yes">&nbsp;
  </span>细化该算法</a></font></div>
  <div id=PPTC46 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB46 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>当对一个问题有了概要的理解后，下面的工作就是把这个问题的想法进行细化。所谓的细化就是把它们表示成算法的步骤。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>可以用到的工具有自然语言（nature language）、伪代码（pseudocode）以及程序流程图（flow
    chart）等。</font></td>
   </tr>
  </table>
  </div>
  </td>
 </tr>
 <tr>
  <td>
  <div id=PPTP47 class=PTxt><font size=2><a
  href="javascript:GoToSld('slide0098.htm');" onmouseover="Over(this)"
  id=PPTL47 onmouseout="Out(this)">1.3.7<span style="mso-spacerun: yes">&nbsp;
  </span>确认算法的正确性</a></font></div>
  <div id=PPTC47 class=CTxt style='display:none'>
  <table style='color:white' id=PPTB47 class=CBorder>
   <tr>
    <td width=5 nowrap></td>
    <td width="100%"></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>当给算法一个合法输入，而该算法给出一个错误的结果时，可以证明这个算法是错误的。但如果证明一个算法是正确，情况就不是那样地简单。算法的测试有一套完整的理论，这里不作详细叙述。</font></td>
   </tr>
   <tr>
    <td colspan=1></td>
    <td colspan=1><font size=2>特别需要提出的是，所谓算法的正确性指的是：对于任