算法课程设计.docx

《算法课程设计.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、摘要当今科技迅速发展，运用计算机解决实际问题变得异常重要。尤其是运用计算机实现算法设计具要重大意义。算法设计与分析，其实可以解释为一种优化问题，一般是对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出的各种不同的解决方案，并且要针对具体问题做细致的空间与时间复杂度分析。本文是运用动态规划法解决租用游艇问题和回溯法解决部落卫队问题。利用C++编程实现算法。动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。首先找出最优解的性质，并刻画其结构特征，然后递归的定义最优

2、值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造一个最优解。回溯法算法是确定了解空间的组织结构后，回溯法从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个

3、活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。关键字：动态规划法、租用游艇问题、回溯法、部落卫队问题、C++目录一、动态规划法解决租用游艇问题21.1问题重述21.2问题分析21.3算法原理与设计21.3.1算法原理21.3.2算法设计31.4算法实现与结果41.5结果描述5二、回溯法解决部落卫队问题62.1问题重述62.2问题分析62.3算法原理及设计62.3.1算法原理62.3.2算法设计72.4

4、算法实现82.5结果描述10三、总结12参考文献13一、动态规划法解决租用游艇问题1.1问题重述长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。有可以游艇出租站用游艇并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i

5、0），表示有n个游艇出租站。接下来的n-1行是一个半矩阵r(i,j),1<=i

6、法原理与设计1.3.1算法原理本文主要适用动态规划法的思想求解，其基本思想时将原问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都

7、要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。设计动态规划法一般包含以下4个步骤为：u找出最优解的性质，并刻画其结构特征；u递归地定义最优值；u以自底向上的方法计算出最优解；u根据计算最优值得到的信息，构造最优解。1.3.2算法设计intmain(){intnum,i,j,k;for(k=2;k

8、++){intmark=i+k;for(j=i+1;j