《算法设计与分析》实验指导书 bfm(全)
更新时间:2023-10-31 22:50:01 阅读量: 综合文库 文档下载
- 算法设计与分析实验报告推荐度:
- 相关推荐
《算法设计与分析》实验指导书
计算机学院信息安全系 毕方明
本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导,其目的是使学生消化理论知识,加深对讲授内容的理解,尤其是一些算法的实现及其应用,培养学生独立编程和调试程序的能力,使学生对算法的分析与设计有更深刻的认识。 上机实验一般应包括以下几个步骤: (1)、准备好上机所需的程序。手编程序应书写整齐,并经人工检查无误后才能上机。 (2)、上机输入和调试自己所编的程序。一人一组,独立上机调试,上机时出现的问题,最好独立解决。 (3)、上机结束后,整理出实验报告。实验报告应包括:题目、程序清单、运行结果、对运行情况所作的分析。
本书共分阶段4个实验,每个实验有基本题和提高题。基本题必须完成,提高题根据自己实际情况进行取舍。题目不限定如下题目,可根据自己兴趣爱好做一些与实验内容相关的其他题目,如动态规划法中的图象压缩,回溯法中的人机对弈等。 其具体要求和步骤如下:
实验一 分治与递归(4学时)
基本题一:基本递归算法 一、实验目的与要求
1、 熟悉C/C++语言的集成开发环境;
2、通过本实验加深对递归过程的理解 二、实验内容:
掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法。 三、实验题
任意输入一个整数,输出结果能够用递归方法实现整数的划分。 四、实验步骤
1. 理解算法思想和问题要求; 2. 编程实现题目要求;
3. 上机输入和调试自己所编的程序; 4. 验证分析实验结果; 5. 整理出实验报告。
基本题二:棋盘覆盖问题 一、实验目的与要求
1、掌握棋盘覆盖问题的算法; 2、初步掌握分治算法 二、实验题:
盘覆盖问题:在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形
态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 三、实验提示
void chessBoard(int tr, int tc, int dr, int dc, int size) {
if (size == 1) return;
int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t; // 覆盖其余方格
chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格
chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s);
else {// 用 t 号L型骨牌覆盖右上角 board[tr + s][tc + s - 1] = t; // 覆盖其余方格
chessBoard(tr+s, tc, tr+s, tc+s-1, s);} // 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中
chessBoard(tr+s, tc+s, dr, dc, s);
else {// 用 t 号L型骨牌覆盖左上角 board[tr + s][tc + s] = t; // 覆盖其余方格
chessBoard(tr+s, tc+s, tr+s, tc+s, s);} }
提高题一:二分搜索 一、实验目的与要求 1、熟悉二分搜索算法; 2、初步掌握分治算法; 二、实验题
1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时,I和j相同,均为x在数组中的位置。 2、设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标I,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O(logn)。 三、实验提示
1、用I,j做参数,且采用传递引用或指针的形式带回值。 bool BinarySearch(int a[],int n,int x,int& i,int& j) {
int left=0; int right=n-1; while(left int mid=(left+right)/2; if(x==a[mid]) { i=j=mid; return true; } if(x>a[mid]) left=mid+1; else right=mid-1; } i=right; j=left; return false; } int SearchTag(int a[],int n,int x) { int left=0; int right=n-1; while(left int mid=(left+right)/2; if(x==a[mid]) return mid; if(x>a[mid]) right=mid-1; else left=mid+1; } return -1; } 提高题二: 用分治法实现元素选择 一、实验要求与目的 1、了解分治法的基本思想,掌握递归程序编写方法; 2、使用分治法编程,求解线形序列中第k小元素。 二、实验内容 1、 给定线形序列集中n个元素和一个整数k,1≤k≤n,输出这n个元素中第k小元素的值 及其位置。 2、 简述该算法的原理、步骤。对该算法与直接排序查找进行比较。 3、 编写并调试程序。 测试要求:元素个数不少于100;分三种情况:k=1、k=n和k=中位数。 实验二 动态规划算法(4学时) 基本题一:最长公共子序列问题 一、实验目的与要求 1、熟悉最长公共子序列问题的算法; 2、初步掌握动态规划算法; 二、实验题 若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。 给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。 三、实验提示 include \#include \ void LCSLength(char *x ,char *y,int m,int n, int **c, int **b) { int i ,j; for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } void LCS(int i ,int j, char *x ,int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { LCS(i-1,j-1,x,b); printf(\ } else if (b[i][j]== 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); } 基本题二:最大字段和问题 一、实验目的与要求 1、熟悉最长最大字段和问题的算法; 2、进一步掌握动态规划算法; 二、实验题 若给定n个整数组成的序列a1,a2,a3,……an,求该序列形如ai+ai+1+……+an的最大值。 三、实验提示 int MaxSum(int n,int *a,int &besti,int &bestj) { intsum=0;
正在阅读:
男士该如何保养皮肤07-23
小学一年级注音美文诵读十篇 小学一年级注音美文诵读十篇电子教04-26
宝峰-2012奖励性绩效工资分配方案05-20
02331数据结构2013年1 月份历年真题附答案 - 图文12-10
践行社会主义核心价值观的心得体会范文-心得体会模板03-08
重庆市万州桥亭中学2014年初2015级年级九月月考英语试卷04-08
赞美你绿树作文600字07-15
- 必修一物理寒假作业
- 2019-201X年5月大学生入党积极分子思想汇报-word范文模板(3页)
- 药物分析习题五
- 重拾应用意识 体会数学价值(沈建军)
- 2017全国高校辅导员结构化面试题集及参考答案
- 广东徐闻县实验中学2014届高三第二次月测地理试题
- 今天你共鸣了么?
- 2018-2019正能量读后感1000字-推荐word版(6页)
- 2018年中国截切型盖板针布行业专题研究分析报告目录
- 中国移动业务处理流程大全
- 公文写作常用词汇和句子集锦2016
- ARM课程设计说明书
- 教师资格证教育学论文
- 中考试卷分析
- 环境监测试卷(五)
- 党风廉政建设广播稿1
- 快速制作香香宫煮麻辣烫教程
- 《国际金融学》习题
- 文明施工保障措施方案
- 春兰维修资料故障代码
- 指导书
- 算法
- 实验
- 分析
- 设计
- bfm