算法分析与设计实验

《算法设计与分析》实验报告

学号： 姓名：

实验一 分治法求解**问题

一、实验目的

1.掌握分治法的设计思想并能熟练应用；

2.理解分治与递归的关系。

二、实验题目

在有序序列中(r1,r2,…,rn)中,存在序号i（1≤i≤n）,使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n).

三、实验程序

//以(0,2,3,3,5,7,8,10,12,13)为例

#include<iostream>

using namespace std;

void PrintData(int data[],int length)

{

}

int Bisearch(int data[],int begin ,int last)

{

if ( mid < data[mid] ) int mid=(begin + last) /2; if (mid+1 == data[mid]) { } return mid; cout<<"有序序列是："; for (int i=0;i

实验一 算法分析与设计

一、实验目的

1. 掌握递归程序的概念和递归程序的编写。 2. 编写两种或以上算法解决同一个问题，对算法性能比较，从而认识到算法设计的重

要性。

二、实验内容

1、用递归函数解决汉诺塔问题，并输出圆盘移动的过程。 汉诺塔(Hanoi)问题。

设有三个塔座X、Y、Z，n个圆盘。这些圆盘大小互不相同， 初始时，这些编号为1，2， …，n的圆盘从大到小依次放在塔座X上。最底下为最大圆盘。要求将该塔座上的圆盘移到另一个塔座Z上，并按照同样顺序放置。圆盘移动时， 满足以下规则： ① 一次只能移动一个圆盘；② 任何时刻不允许将大的圆盘放在小的圆盘之上； ③ 圆盘可以放在X、Y和Z的任一塔座上。

输入较大的n值，观察执行时间变化。 #include

void Hanoi(char x,char z,char y,int n) {

if(n==1) printf(\ else {

Hanoi(x,y,z,n-1);

printf(\ Hanoi(y,z,x,n-1); } }

main() {

int n;

printf(\输入n的值:\\n\ scanf(\

实验二：分治法实验

一、实验目的

（1）掌握设计有效算法的分治策略。

（2）通过快速排序学习分治策略设计技巧

二、实验要求

（1）熟练掌握分治法的基本思想及其应用实现。

（2）理解所给出的算法，并对其加以改进。

三、分治法的介绍

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k个子问题，1

分治法的适用条件：

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

（3）利用该问题分解出的子问题的解可以合并为该问题的解；

（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于

算法设计与分析实验指导

余腊生 编

实验一：递归与分治

1. 二分查找 2. 合并排序 3. 快速排序

实验二：回溯

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 1. 2. 3. 4. 5. 6. 7. 8. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 1. 2. 3. 4. 5.

0-1背包问题 装载问题

堡垒问题（ZOJ1002） *翻硬币问题 8皇后问题 素数环问题 迷宫问题

*农场灌溉问题（ZOJ2412） *求图像的周长（ZOJ1047） *骨牌矩阵

*字母转换（ZOJ1003） *踩气球（ZOJ1004）

实验三：搜索

Floodfill

电子老鼠闯迷宫 跳马 独轮车 皇宫小偷 分酒问题 *找倍数 *8数码难题

实验四：动态规划

最长公共子序列 计算矩阵连乘积

凸多边形的最优三角剖分 防卫导弹 *石子合并

*最小代价子母树 *旅游预算 *皇宫看守 *游戏室问题 *基因问题 *田忌赛马

实验五：贪心与随机算法

背包问题 搬桌子问题 *照亮的山景

*用随即算法求解8皇后问题 素数测试

实验一：递归与分治

实验目的

理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。

算法设计与分析实验指导

余腊生 编

实验一：递归与分治

1. 二分查找 2. 合并排序 3. 快速排序

实验二：回溯

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 1. 2. 3. 4. 5. 6. 7. 8. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 1. 2. 3. 4. 5.

0-1背包问题 装载问题

堡垒问题（ZOJ1002） *翻硬币问题 8皇后问题 素数环问题 迷宫问题

*农场灌溉问题（ZOJ2412） *求图像的周长（ZOJ1047） *骨牌矩阵

*字母转换（ZOJ1003） *踩气球（ZOJ1004）

实验三：搜索

Floodfill

电子老鼠闯迷宫 跳马 独轮车 皇宫小偷 分酒问题 *找倍数 *8数码难题

实验四：动态规划

最长公共子序列 计算矩阵连乘积

凸多边形的最优三角剖分 防卫导弹 *石子合并

*最小代价子母树 *旅游预算 *皇宫看守 *游戏室问题 *基因问题 *田忌赛马

实验五：贪心与随机算法

背包问题 搬桌子问题 *照亮的山景

*用随即算法求解8皇后问题 素数测试

实验一：递归与分治

实验目的

理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。

算法分析与设计

专业班级：姓 名：学 号：指导老师：实 验 报 告

实验一 递归算法的设计与实现 ? 计算整数的非负整数次幂

(1)设计思路

对于34按步骤可以分析： 34=32*32 32=31*31 31=31*1

对于33按步骤可以分析： 33=32*31； 32=31*31； 31=31*1；

分析可以得到：

当xn中n为奇数时，xn=x*(xn/2)2 当xn中n为偶数的，xn=（xn/2）2； 当n/2=0;return 1；

一步步进行递归返回计算，如果n位奇数，在进行一部乘以x 否则返回运算结果

(2)源程序代码

#include using namespace std;

int power(int x,int n) { int y; if(n==0) { y=1; } else { y=power(x,n/2); y=y*y; if(n%2==1) { y=y*x; }

} return y; }

void main() {

cout<<\请输入一个底数X：\ int x; cin>>x;

cout<<\请输入一个

史上最完整的《算法设计与分析》实验报告。敬请下载。

算法设计与分析 课程实验项目目录

*实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。

本科实验报告专用纸

史上最完整的《算法设计与分析》实验报告。敬请下载。

课程名称 算法设计与分析 成绩评定 实验项目名称 蛮力法 指导教师 实验项目编号 20122229201 实验项目类型 设计 实验地点 机房 学生姓名 学号

学院 信息科学技术学院数学 系 信息与计算科学 专业 级 实验时间 2012年 3月 1 日～6月30日 温度24℃ 1. 实验目的和要求： 熟悉蛮力法的设计思想。 2. 实验原理和主要内容：

实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验内容：以下题目任选其一

1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。

3).最著名的算式谜题是由大名鼎鼎的英国谜人

S END

H.E.Dudeney(1857-1930)给出的：+MORE. 这里有两个前提假设：

MON

声明：此文档只作为学习参考，不得用作它途！ 《算法设计与分析》实验教学大纲

实验学时：32 实验个数：7 实验学分：1 课程性质： 适用专业：计算机科学与技术、软件工程 教材及参考书：

1. 《计算机算法设计与分析》，王晓东，北京：电子工业出版社，2012 2. 《算法与数据结构》，傅清祥等著，北京：电子工业出版社，2003

3. 《计算机算法导引—设计与分析》，卢开澄著，北京：清华大学出版社，2001 大纲执笔人：刘芳 大纲审定人： 郭涛 一、 实验课的性质与任务

算法的设计与分析是计算机科学的核心问题之一，也是计算机科学与技术专业本科 及研究生的一门重要的专业基础课，其内容是研究计算机领域及其有关领域中的一些非 数值计算的常用算法。课程将覆盖计算机软件实现中常用的、有代表性的算法，并具有 一定的深度和广度，通过实验，使学生理解并掌握算法设计的基本技术，让学生具有针 对所给的问题设计和实现高效算法的基本能力。 二、实验课程目的与要求 计算机科学的一个核心问题是算法理论，本课程介绍非数值算法设计的策略与技 术，同时介绍算法的复杂性的概念通过对一

《算法设计与分析》习题

第一章 引 论

习题1-1 写一个通用方法用于判定给定数组是否已排好序。 解答：

Algorithm compare(a,n) Begin J=1;

While (j

While (j=a[j+1]) do j=j+1;

If j=n then return true else return false end if

End if end

习题1-2 写一个算法交换两个变量的值不使用第三个变量。 解答： x=x+y; y=x-y; x=x-y;

习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件 (n2-mn-m2)2=1 且使n2+m2达到最大的m、 n。 解答：

m:=k; flag:=0; repeat

n:=m; repeat

l:=n*n-m*n-m*n;

if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1 until (flag=1) or (

《算法设计与分析》习题

第一章 引 论

习题1-1 写一个通用方法用于判定给定数组是否已排好序。 解答：

Algorithm compare(a,n) Begin J=1;

While (j

While (j=a[j+1]) do j=j+1;

If j=n then return true else return false end if

End if end

习题1-2 写一个算法交换两个变量的值不使用第三个变量。 解答： x=x+y; y=x-y; x=x-y;

习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件 (n2-mn-m2)2=1 且使n2+m2达到最大的m、 n。 解答：

m:=k; flag:=0; repeat

n:=m; repeat

l:=n*n-m*n-m*n;

if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1 until (flag=1) or (