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

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


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

实验一
目的和要求

分治法程序设计

(一) 目的 本实验的目的是了解分治策略算法思想,了解递归算法的设计思路,掌握两 路合并排序算法。 (二) 要求 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


相关文章:
《计算机辅助设计AⅡ》实验指导书2014-2015-2版_图文
《计算机辅助设计AⅡ》 实验指导书 张凌青编写 四川农业大学建筑与城乡规划学院 2014-2015-2 版 《计算机辅助设计 AⅡ》实验指导书 2014-2015-2 版 说明该实验...
微机实验指导书-学生使用(2015定稿)-A
微机实验指导书-学生使用(2015定稿)-A_其它_高等教育_教育专区。sse 《微机原理与接口技术》 实验指导书 2015 年 11 月 杭州电子科技大学自动化学院 《微机原理...
计算方法实验指导书
《数值分析与实验》 ,薛毅编著,北京工业大学出版社,2005.3 实验项目: A, ...按照 Gauss 列主元消去法的算法写出其 Matlab 程序(Gauss.m) 。 Matlab 程序...
数值计算A上机实验指导书
数值计算A上机实验指导书_数学_自然科学_专业资料。...6.2 算法描述 6.2.1 复化梯形、Simpson、Cotes ...2015国考申论押密试卷及答案 2015国考面试通关宝典120...
《数据结构与算法》实验指导书
《数据结构与算法》实验指导书_管理学_高等教育_教育专区。《数据结构与算法》...提高要求:a.实现能计算操作数为浮点数的表达式,b.解决迷宫问题时 能找出所有...
A算法实验
A算法实验_IT/计算机_专业资料。A*算法寻径 实验二: 算法 实验二:A*算法姓名:曾焕凯 一、实验目的掌握 A*算法的原理,并会使用 A*算法. 班级:09 数字媒体...
操作系统A实验指导书
《操作系统 A》实验指导书实验一 进程调度实验实验名称: 进程调度实验 实验类型...二、实验要求本实验模拟单处理器系统的进程调度,加深对进程的概念及进程调度算法...
操作系统原理A实验指导书
操作系统原理A实验指导书_计算机软件及应用_IT/计算机...权优先或时间片轮转法四种算法中的两种算法来实现...文档贡献者 嗯是晓波 贡献于2015-05-22 专题推荐...
2015算法分析试卷A
2015算法分析试卷A_工学_高等教育_教育专区。2014 ~2015 学年度第 一 学期课程名称:算法分析与设计 课程性质: (必修) 考试时间:2014 年 12 月 1 日 考试...
《SQL SERVER 数据库应用》实验指导书-2015版
《SQL SERVER 数据库应用》实验指导书-2015版_物理_自然科学_专业资料。《数据...实验预习情况:A 实验出勤情况:B 原型系统效果验收和实验报告:C 实验成绩=A*20...
更多相关标签: