计算机算法分析与设计(第四版)习题算法分析部分详解(实验1)

实验参考代码 VC 6 0 测试通过 算法实验 1 1 1 5 任选一道实验 写实验报告 当堂 1 分 实验报告 4 分 算法实现题 1 1 统计数字问题 include include using namespace std int main int count 10 int i j k L int n len m while scanf d L ceil log10 n 1 for i 0 i 10 i count i 0 for j 0 j L j len ceil log10 m 1 k m pow 10 0 len 1 从高位到低位取各个位数的值 for i 0 i 10 i 小 K len 的数数值 0 9 出现的次数 count i k len 1 pow 10 0 len 2 K n f n 1 for i 0 i k i count i pow 10 0 len 1 在高位小于数值 K 的数出现的次数 count k m k pow 10 0 len 1 1 在高位数值 K 的数出现的次数 m m k pow 10 0 len 1 去掉已计算的高位 for i 0 i L i 去掉前导 0 count 0 pow 10 0 i 分别考虑 0 在高位的情况有到少种 for i 0 i 10 i printf d n count i return 0 算法实现题 1 2 字典序问题 实验参考代码 VC 6 0 测试通过 include include unsigned long dp 27 11 sum 17 ans 本代码实现 字符串长度不超过 10 可解 char str 11 void main int i j k len start memset dp 0 sizeof dp 为数组分配空间 并初始化为 0 memset sum 0 sizeof sum for i 1 i 27 i dp i 1 1 for j 2 j 1 i dp i j 以第 i 个字母开头的长度为 j 的单词个数 dp i j dp i 1 j dp i j dp i 1 j 1 for i 1 i 10 i 长度为 i 是的总个数 for j 1 j 26 j sum i dp j i scanf s str len strlen str for i 1 i 1 j for i start k 1 k str len j a start 1 k i 考虑打头为 1 i 1 长度为 j 的字 符串个数 ans dp i j start str len j a 2 打头字符在字典序中下一个字符位置 for i 0 i str i 1 ans 1 printf u n ans 1 实验参考代码 VC 6 0 测试通过 算法实现题 1 3 最多约数问题 方法一 include using namespace std bool back int a b int max 0 maxn void main cin a b if a b cout a b error endl return back new bool b 1 for int i a i b i int count 0 for int j 0 j b j back j false for int k 1 k i 2 1 k if i k 0 back k true back i k true for j 0 jmax max count maxn i cout max endl maxn endl 方法二 include using namespace std define max Max const long MAXP 100000 实验参考代码 VC 6 0 测试通过 long prim MAXP long max numb PCOUNT max 存放最多约数个数 numb 存放约数个数最多的数 void primes 用筛选法产生质数存于 prim 数组中 void search long from long tot long num long low long up int main primes long l u cin l u if l 1 numb 1 else max 2 numb l search 1 1 1 l u cout max endl numb endl system pause return 0 void primes bool get MAXP 1 long i for i 2 i MAXP i get i true for i 2 i MAXP i if get i long j i i while j MAXP get j false j i long ii j for ii 2 j 0 ii 1 if tot max tot max for long i from i up return else long j prim i x low 1 y up n num t tot m 1 while true m t tot x j y j if x y break n j search i 1 t n x 1 y m 1 m if tot max m return 实验参考代码 VC 6 0 测试通过 算法实现题 1 4 金币列阵问题 include include using namespace std const int size 100 int k n m ccount best int b0 size 1 size 1 b1 size 1 size 1 b size 1 size 1 bool found void print for int i 1 i n i for int j 1 j m j cout b1 i j cout endl void trans1 int x 行翻转 for int i 1 i m i b1 x i b1 x i 1 ccount void trans2 int x int y 列交换 for int i 1 i n i swap b1 i x b1 i y if x y ccount bool same int x int y for int i 1 i n i if b0 i x b1 i y return false return true void acpy int a size 1 size 1 int b size 1 size 1 for int i 1 i n i for int j 1 j k for int i 1 i n m n 行 m 列 原状态 b0 for x 1 x n x for y 1 y b0 x y 目标状态 b1 for x 1 x n x for int y 1 y b1 x y acpy b b1 b1 复制到 b best m n 1 for j 1 j m j acpy b1 b ccount 0 trans2 1 j 列变换 int p for p 1 p n p if b0 p 1 b1 p 1 trans1 p 行变换 for p 1 p m p 找列相等的 b1 的 q 列和 b0 的 p 列 相等 found false for int q p q m q if same p q trans2 p q found true break if found break if found if best m n 1 cout best endl else cout 1 endl 实验参考代码 VC 6 0 测试通过 int main answer return 0 实验参考代码 VC 6 0 测试通过 算法实现题 1 5 最大间隙问题 include using namespace std const int MAX 200001 double num MAX bool run int n if scanf d ctrl z 回车退出 int i double max 0 0 min INT MAX 大值初始化为最小 小值初始化为最大 for i 0 imax max num i if num i min min num i int cnt new int n double low new double n double high new double n for i 0 i n i 初始化桶 cnt i 0 low i max high i min double ave max min n 1 for i 0 ihigh tmp high tmp num i 修改桶边界 if num i low tmp low tmp num i double t high 0 res 0 0 for i 1 i0 桶中有数字才进行检查 无数字跳过 实验参考代码 VC 6 0 测试通过 double tmp low i t if tmp res res tmp t high i cout res endl return true int main while run return 0 附 实验 设计 报告参考格式附 实验 设计 报告参考格式 设计一 多段图问题的动态规划算法与实现多段图问题的动态规划算法与实现 班级 学号 姓名 成绩 分 一 一 设计目的设计目的 1 掌握有向网的成本邻接矩阵表示法 2 掌握多段图问题的动态规划递推算法 3 进一步掌握动态规划法的基本思想和算法设计方法 二 二 设计内容设计内容 1 1 任务描述任务描述 1 多段图问题简介 2 设计任务简介 设计求解多段图问题的动态规划算法 即设计和实现多段图问题的表示方案 动 态规划递推算法 设计对算法或程序的测试方案并完成测试 实验参考代码 VC 6 0 测试通过 2 2 多段图问题的表示方案多段图问题的表示方案 本设计采用成本邻接矩阵表示多段图 针对多段图 可插入图例 描述成本邻接矩 阵的规模与元素意义 3 3 递推过程的抽象描述递推过程的抽象描述 本设计采用前向或后向递推公式 用自然语言 伪程序设计语言或流程图等形式 针对多段图问题的求解 抽象地 描述递推过程 4 4 主要数据类型与变量主要数据类型与变量 typedef NodeNumber int 节点编号 typedef CostType int 成本值类型 CostType cost n n 成本邻接矩阵 n 为顶点数 NodeNumber path k k 段图最短路径上的节点编号数组 NodeNumber cur 1 当前邻接节点 必要时 可对数据类型和变量进一步解释或说明 增加可读性必要时 可对数据类型和变量进一步解释或说明 增加可读性 5 5 算法或程序模块算法或程序模块 int FindForward CostType cost n NodeNumber i NodeNumber cur 功能 根据邻接矩阵查找节点 i 的下一个前向邻接节点 成功时返回节点编号 否则 返回 1 cur 为当前的前向邻接节点 第一次调用时其值为 1 int FindBackward CostType cost n NodeNumber i NodeNumber cur 功能 根据邻接矩阵查找节点 i 的下一个后向邻接节点 成功时返回节点编号 否则 返回 1 cur 为当前的后向邻接节点 第一次调用时其值为 1 必要时 可对算法或程