l算法分析实验指导.docVIP

算法分析设计与提高 实验指导 2016年4月 实验一 算法基础 一、实验要求 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握描述算法的方法。? 实现具体的编程与上机实验，验证算法的时间复杂性函数。 二、实验内容 ? 统计数字问题 ?1. 问题描述 ?一本书的页码从自然数1?开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6?页用数字6?表示，而不是06?或006?等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，?2，…，9。? 2. 编程任务? 给定表示书的总页码的10?进制整数n?(1≤n≤109)?。编程计算书的全部页码中分别用到多少次数字0，1，2，…，9。? 程序算法 程序代码 程序调试中的问题 实验结果 实验二 分治法 一.实验要求 了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时， 如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。 掌握分治法的一般控制流程。 3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 循环赛日程表 程序算法 程序代码 程序调试中的问题 实验结果 实验三 动态规划 一.实验要求 对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。 最优子结构性质：原问题的最优解包含了其子问题的最优解。 子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。 理解分段决策Bellman方程。 每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。 us 初始值，uj第j段的最优值。 一般方法 找出最优解的性质，并刻画其结构特征； 递归地定义最优值（写出动态规划方程）； 以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造一个最优解。 步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。 二.实验内容 01背包问题 程序算法 程序代码 程序调试中的问题 实验结果 实验四 贪心算法 一.实验要求 掌握算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。 一般方法 1）根据题意，选取一种量度标准。 2）按这种量度标准对这n个输入排序 3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 活动安排问题 程序算法 程序代码 程序调试中的问题 实验结果 1