当前位置:首页 >> 数学 >>

《算法A》实验指导书(2015版)


《算法设计与分析 A》实验指导书
实验总要求 1. 遵守机房纪律,服从机房调度。 2. 努力准备上机内容,并预先做一些情况分析。 3. 仔细观察上机现象,记录主要情况。 4. 认真填写实验报告,包括姓名、所在班级、实验题目、实验目的、实验 要求、程序框图及程序清单和运行结果,运行情况分析,意见,程序清单要有注 释。 5. 四个实验订在一起,只要一个封皮。

r />实验一
目的和要求

分治法程序设计

(一) 目的 本实验的目的是了解分治策略算法思想,了解递归算法的设计思路,掌握两 路合并排序算法。 (二) 要求 1. 写出源程序,并编译运行。 2. 详细记录程序调试及运行结果。

实验内容
编写一个简单的程序,实现归并排序;

算法思想分析
两路合并排序:将待排序的元素序列一分为二分,得到两个长度基本相等的子序 列,如同对半搜索的做法;然后对两个子序列分别排序,如果子序列较长,还可 继续细分,直到子序列的长度不超过 1 为止;当分解所得的子序列已排列有序, 可以将两个有序子序列,合并成一个有序子序列的方法,实现将子问题的解组合 成原问题解,这是分治法不可缺少的一步。

1

实验二
目的和要求

贪心算法程序设计

(一)目的 本实验的目的是了解贪心算法思想,掌握贪心算法典型问题,如迪杰 斯特拉算法求单源最短路径问题。 (二)要求 1.写出源程序,并编译运行。 2.详细记录程序调试及运行结果。

实验内容
编写一个程序,实现单源最短路径问题。

算法思想分析
设集合 S 存放已经求得最短路径的终点,则 V-S 为尚未求得最短路径的终点集 合。初始状态时,集合 S 中只有一个源点,设为结点 s。迪杰斯特拉的具体做 法是:首先将源点 s 加入 S 中;在算法的每一步中,按照最短路径值的非减次 序,产生下一条最短路径(s->t),并将该路径的终点 t∈V-S 加入 S 中;直到 S=V,算法结束。 当前最短路径:在算法执行中,一个结点 t∈V-S 的当前路径,是一条从源点 s 到结点 t 的路径,在该路径上,除结点 t 外,其余结点都属于 S,当前最短路 径是所有这些路径中的最短者。于是可将最优量度标准设计为:从 V-S 中选择 具有最短的“当前最短路径”的结点加入集合 S 中。

2

实验三
目的和要求

动态规划法程序设计

(一)目的 掌握动态规划法思想,掌握最优子结构原理,掌握最长公共子序列问题,了 解动态规划一般问题。最长公共子序列是一个十分实用的问题,它可以描述两段 文字之间的“相似度” ,即它们的雷同程度,从而能够用来辨别抄袭。对一段文 字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分 提取出来,这种方法判断修改的部分,往往十分准确。 (二)要求 1.写出源程序,并编译运行。 2.详细记录程序调试及运行结果。

实验内容
编写一个程序,实现最长公共子序列问题。

算法思想分析
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列 X 和 Y,当另一序列 Z 既是 X 的子序列又是 Y 的子序列时,称 Z 是序列 X 和 Y 的 公共子序列。

3

实验四
目的和要求

回溯法程序设计

(一)目的 掌握回溯法思想,掌握回溯递归原理,掌握 n-皇后问题。 (二)要求 1.写出源程序,并编译运行。 2.详细记录程序调试及运行结果。

实验内容
编写一个程序,实现 8-皇后问题。

算法思想分析
皇后问题要求在一个 8?8 的棋盘上放置 8 个皇后,使得它们彼此不受“攻击” 。 8-皇后问题要求寻找在棋盘上放置这 8 个皇后的方案,使得它们中任何两个都不 在同一行、同一列或同一斜线上。 每一行可以而且必须放一个皇后,所以 n 皇后问题的解可以用一个 n 元向量 X= (x1,x2,.....xn)表示,其中,1≤i≤n 且 1≤xi≤n,即第 n 个皇后放在第 i 行 第 xi 列上。 由于两个皇后不能放在同一列上, 所以, 解向量 X 必须满足的约束条件为:xi≠xj; 若两个皇后的摆放位置分别是(i,xi)和(j,xj) ,在棋盘上斜率为-1 的斜线上, 满足条件 i-j=xi-xj;在棋盘上斜率为 1 的斜线上,满足条件 i+j=xi+xj; 综合两种情况,由于两个皇后不能位于同一斜线上,所以, 解向量 X 必须满足的约束条件为:|i-xi|≠|j-xj|

4


相关文章:
《大学计算机基础》实验指导书2015版_图文
《大学计算机基础》实验指导书2015版_工学_高等教育_教育专区。实验一 Windows ...6. 将考生文件夹下 JSTV 文件夹中的文件 ABIU.PRG 更名为 TEST.C。 7. ...
2015《算法分析与设计》实验指导书
2015《算法分析与设计》实验指导书_数学_自然科学_专业资料。算法分析与设计实验...要求算法在最坏的情况下的计算时间为 O(logn) 。 bool BinarySearch(int a[...
《数据结构与算法》实验指导书2015
《数据结构与算法》实验指导书2015_调查/报告_表格/模板_实用文档。《算法与数据...[实验数据]: := X:=(-b+(b^2-4*a*c)^0.5)/(2*a) * / + * ...
数据结构实验指导书(2015版)
数据结构实验指导书(2015版)_电脑基础知识_IT/计算机_专业资料。数据结构与算法...{'a','b','c','d','e'}, {{0,1,0,1,0}, {1,0,0,0,1}, ...
《数字信号处理》实验指导书(2015版)
《数字信号处理》实验指导书(2015版)_工学_高等教育_教育专区。数字信号处理 实验...14 实验五 基于 ICETEK-F2812-A 的 FFT 算法分析 ... 错误!未定义书签。...
2015《程序综合实验》实验指导书
2015《程序综合实验》实验指导书_调查/报告_表格/...{ m_a = m_1 * 10 + 1;//输入框对应的...算法设计与实现能力 实验要求: 1 熟悉数据结构、...
2015版《数据库原理实验》指导书
2015版《数据库原理实验》指导书_计算机软件及应用_IT/计算机_专业资料。《数据...按职称查询教师的平均工资,并按总工资降序排列 15.将笔试成绩转换成 A、B、C...
《算法设计与分析》实验指导书200609版
《算法设计与分析》实验指导书200609版_数学_自然...18.2 A 38.2 B 5.9 C 41.1 23.1 D 67 ....文档贡献者 习惯以后啊 贡献于2015-12-10 相关文档...
编译原理实验指导书(2015)_图文
4 《编译原理课程实验指导书 Procedure program1(a, b); Begin Var xyz=...设计原理及算法描述 所谓 LL(1)分析法,就是指从左到右扫描输入串(源程序) ...
微机实验指导书-学生使用(2015定稿)-A
微机实验指导书-学生使用(2015定稿)-A_其它_高等教育_教育专区。sse 《微机原理与接口技术》 实验指导书 2015 年 11 月 杭州电子科技大学自动化学院 《微机原理...
更多相关标签: