算法分析与设计实验报告

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

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

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

本科实验报告专用纸

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

课程名称 算法设计与分析 成绩评定 实验项目名称 蛮力法 指导教师 实验项目编号 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)设计思路

对于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<<\请输入一个

学 号

《算法设计与分析》

实验报告三

学专指成

生业导、

姓班教

名 级 师 绩

计算机与信息工程学院软件工程系

2014 年 10 月 20 日

实验三：贪心算法运用练习

一、实验目的

本次实验是针对贪心算法运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。

二、实验步骤与要求

1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容；

3．实验结束后，用统一的实验报告模板编写实验报告。

4．提交说明：

（1）电子版提交说明：

a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验四_学号_姓名”， 如“《算法设计与分析》实验四_09290101_张三”。

b 压缩包内为一个“《算法设计与分析》实验四_学号_姓名”命名的顶层文件夹，

其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。

（2）打印版提交说明：

a 不可随意更改模板样式。

b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为

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

完成日期： 20011.11.10

一、实验目的

(1) 了解分治策略算法思想

(2) 掌握快速排序、归并排序算法

(3) 了解其他分治问题典型算法

二．实验内容：

(1) 编写一个简单的程序，实现归并排序。

(2) 编写一段程序，实现快速排序。

(3) 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天

三．实验要求：

（1） 写出源程序，并编译运行

（2） 详细记录程序调试及运行结果

四．算法思想分析：

①归并排序：将待排序元素分成大小大致相同的两个集合，分别把对两个子集合进行排序，最终将排序号的子集合合并成为所要求的排好序的集合

②快速排序：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

③按照分治策略，将所有选手分为两组，n个选手的比赛日程就可以通过为n/2个选手设计的比赛日程表来决定。递归的对选手进行分割，直到剩下两个选手时，比赛日程表的制定

课 程 设 计 说 明 书

设计题目： 二分查找程序的实现

专业： 班级：

设计人：

山 东 科 技 大 学 年 月 日

课 程 设 计 任 务 书

学院：信息科学与工程学院 专业： 班级： 姓名：

一、课程设计题目： 二分查找程序的实现 二、课程设计主要参考资料

（1） 计算机算法设计与分析（第三版）王晓东著 （2） 三、课程设计应解决的主要问题

（1） 二分查找程序的实现

姓名： 学号：

实验六

实验目的：通过对例题分析、设计、调试，体会和掌握贪心法在程序设计中的应用，并进行

贪心优化的相应练习。

实验要求：综述应用贪心法求解问题的特点，并从贪心对象的选择、程序结构与参数设置的

改进等方面对贪心设计进行优化。

实验内容：

1、/* 贪心删数字 */

#include<stdio.h>

void main()

{ int i,j,k,m,n,t,x,a[200];

char b[200];

printf("请输入整数：");

scanf("%s",b);

for(n=0,i=0;b[i]!='\0';i++)

{n++;a[i]=b[i] -48;}

printf("删除数字个数: ");scanf("%d",&k);

printf("以上%d位整数中删除%d个数字分别为: ",n,k);

i=0;m=0;x=0;

while(k>x && m==0)

{i=i+1;

if(a[i-1]<a[i]) /* 出现递增,删除递增的首数字 */

{printf("

姓名： 学号：

实验六

实验目的：通过对例题分析、设计、调试，体会和掌握贪心法在程序设计中的应用，并进行

贪心优化的相应练习。

实验要求：综述应用贪心法求解问题的特点，并从贪心对象的选择、程序结构与参数设置的

改进等方面对贪心设计进行优化。

实验内容：

1、/* 贪心删数字 */

#include<stdio.h>

void main()

{ int i,j,k,m,n,t,x,a[200];

char b[200];

printf("请输入整数：");

scanf("%s",b);

for(n=0,i=0;b[i]!='\0';i++)

{n++;a[i]=b[i] -48;}

printf("删除数字个数: ");scanf("%d",&k);

printf("以上%d位整数中删除%d个数字分别为: ",n,k);

i=0;m=0;x=0;

while(k>x && m==0)

{i=i+1;

if(a[i-1]<a[i]) /* 出现递增,删除递增的首数字 */

{printf("

算法设计与分析实验报告

重 庆 交 通 大 学 学 生 实 验 报 告

实验课程名称 算法设计与分析 开课实验室 数学实验室

学院 数学与统计学院 年级13 专业班 信息与计算科学2 学 生 姓 名 辜朕圆 学 号 631322020223 开 课 时 间 2015 至 2016 学年 第 1 学期

假设合理 建模求解全面 结果分析完善 文档清晰 综合成绩 教师姓名

优 优 优 优 良 良 良 良 中 中 中 中 差 差 差 差 韩逢庆 2015-2016学年 第一学期

算法设计与分析实验报告

实验报告题目 实验一 递归与分治策略

开课实验室：数学实验室 指导老师：韩逢庆 时间：2015.9 学院：理学院 专业：信息与计算科学 班级：2013级2班

姓名： 辜朕圆 学号：631322020223

一、 实验目的

1．加深学生对分治法算法设计方法的基本

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

学号： 姓名：

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

一、实验目的

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