《算法分析与设计》实验

《《算法分析与设计》实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法分析与设计》实验注：请将实验报告于2014-6-20之前统一上交给学习委员。一•递归法（必做）1.实验目的和要求：熟悉递归算法的设计思想。2.实验原理和主要内容：实验原理：直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。实验内容：Hanoi塔问题。设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些I员I盘门下而上，由大到小地叠在一起。各圆盘从小到大编号为l,2,・・・,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在

2、移动圆盘吋应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的I员I盘压在较小的I员I盘Z上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。3.实验结呆及分析：（将程序和实验结呆粘贴，程序要求注释清楚。）二.动态规划（必做）1.实验目的和要求：熟悉动态规划算法的设计思想。2.实验原理和主要内容：实验原理：动态规划算法的基本步骤是：建立问题的解与其子问题的解之间的递推关系、将子问题的解用表格记录下来（自底向上或自顶向下），避免子问题的重复计算、上述表格的最终状态即为（包含）最终解。实验内容：数字三角形问题。数字三角形中的数字为不超过1

3、00的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数W100,编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输入数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层屮的数字。如输入：5输出：30738810277455265注：输出最大路径为：738753.实验结果及分析：（将程序和实验结果粘贴，程序要求注释清楚。）三.贪心法（必做）1.实验目的和耍求：熟悉贪心算法的设计思想。2.实验原理和主要内容：实验原理：贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择

4、，而且一旦做出了选择，不管将来冇什么结果，该选择都不会改变。换言Z,贪心法并不是从整体最优考虑，它所做出的选择只是局部最优。实验内容：找钱。假设有n种面额不同的币值（例：1元、2元、5元、10元，5种币值）进行找钱,约定各种面额的钱币个数不限。问题：对于任意输入的要找钱数money,确定找钱所需是最少找钱数及其找钱方案。1.实验结呆及分析：（将程序和实验结呆粘贴，程序要求注释清楚。）二.回溯法（必做）1.实验目的和要求：熟悉冋溯算法的设计思想。2.实验原理和主要内容：实验原理：回溯法在问题的解空间树屮，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是

5、否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的基木思想：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程屮用剪枝函数避免无效搜索。实验内容：n后问题。在nXn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nXn格的棋盘上放置n个皐后，任何2个皐后不放在同一行或同一列或同一斜线上。QQQQQQQQ123457812481.实验结杲及分析：（将程序和实验结杲粘

6、贴，程序要求注释清楚。）