算法分析实验报告--分治策略
《算法设计与分析》实验报告
分治策略
姓名：XXX
专业班级：XXX
学号：XXX
指导教师：XXX
完成日期：XXX
一、试验名称：分治策略
（1）写出源程序，并编译运行
（2）详细记录程序调试及运行结果
二、实验目的
(1)了解分治策略算法思想
(2)掌握快速排序、归并排序算法
(3)了解其他分治问题典型算法
三、实验内容
(1)编写一个简单的程序，实现归并排序。
(2)编写一段程序，实现快速排序。
(3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现
要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天
四、算法思想分析
(1)编写一个简单的程序，实现归并排序。
将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行
排序，最终将排好序的子集合合并成为所要求的排好序的集合。
(2)编写一段程序，实现快速排序。
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有
数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数
据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据
变成有序序列。
(3)编写程序实现循环日赛表。
按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通
过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，
直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让
这2个选手进行比赛就可以了。
五、算法源代码及用户程序
(1)编写一个简单的程序，实现归并排序。
#include
#include
#define MAX 10
using namespace std;
void merge(int array[],int p,int q,int r)
{
int i,k;
int begin1,end1,begin2,end2;
int* temp = new int[r-p+1];
begin1 = p;
end1 = q;
begin2 = q+1;
end2 = r;
k = 0;
while((begin1 <= end1)&&(begin2 <= end2))
{
if(array[begin1] < array[begin2])
{
temp[k] = array[begin1];
begin1++;
}
else
{
temp[k] = array[begin2];
begin2++;
}
k++;
}
while(begin1 <= end1)
{
temp[k++] = array[begin1++];
}
while(begin2 <= end2)
{
temp[k++] = array[begin2++];
}
for(i = 0;i < (r-p+1);i++)
{
array[p+i] = temp[i];
}
delete[](temp);
}
void merge_sort(int data[],int left,int right) {
if(left < right)
{
int mid = (left + right)/2;
merge_sort(data,left,mid);
merge_sort(data,mid + 1,right);
merge(data,left,mid,right);
}
}
void main()
{
int number[MAX] = {0};
srand(time(NULL));
printf("排序前：");
for(int i = 0; i < MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}
cout< merge_sort(number,0,9); printf("排序后："); for(int j = 0; j < MAX; j++) { printf("%d ", number[j]); } } (2)编写一段程序，实现快速排序。#include #include #define MAX 10 #define SW AP(x,y) {int t; t = x; x = y; y = t;} using namespace std; void quicksort(int number[],int left,int right) { int i,j,s; if(left < right) { s = number[(left + right)/2]; i = left - 1; j = right + 1; while(1) { while(number[++i] < s); while(number[--j] > s); if(i>=j) break; SWAP(number[i],number[j]); } quicksort(number,left,i-1); quicksort(number,j+1,right); } } void main() { int number[MAX] = {0}; srand(time(NULL)); printf("排序前："); for(int i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); cout< } quicksort(number,0,9); printf("排序后："); for(int j = 0; j < MAX; j++) { printf("%d ", number[j]); } } (3)编写程序实现循环赛日程表。#define MAXN 64 /*日程表数组*/ #include #include #define MAX 32 int a[MAX][MAX]; void Copy(int tox, int toy, int fromx, int fromy, int n) { int i, j; for (i=0; i { for (j=0; j } } void Table(int k, int a[][MAX]) { int i, n = 1 << k; int r; for (i=0; i a[0][i] = i + 1; for (r=1; r { for (i=0; i { Copy(r, i + r, 0, i, r); Copy(r, i, 0, i + r, r); } } } void Out(int a[][MAX], int n) { int i, j; for (i=0; i { for (j=0; j printf("\n"); } printf("\n"); getch(); } int main() { int i; for (i=0; i<5; i++) { int len = 1 << i; Table(i, a); Out(a, len); } return 0; } 六试验结果及分析 分治策略对于解决排序，循环日赛表起着很优越的作用，应该熟 练掌握归并排序和快速排序。而且应该认真搞懂递归的思想。 编译原理实验报告 实验名称 _____________ 消除文法的左递归__________________________ 实验时间 _____________________________________________ 院系 _________________________________________ 班级 ______________________________________________ 学号 ____________________________________________ 姓名 1. 试验目的 ?掌握和理解消除左递归(包括直接左递归和间接左递归)在构建 LL(1)文法的作用和目的 ?掌握消除左递归(包括直接左递归和间接左递归)的方法和步骤。 ?写出对于输入任意的上下文无关文法可以输出消除了左递归的等 价文法。 2. 实验原理 ?直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符 P的规则为 P—P a/ B 其中，B是不以P开头的符号串。那么，我们可以把P的规则改写为 如下的非直接左递归形式：P—尸’ P'—P'￡ 考虑更一般的情况，假定关于非终结符P的规则为 P—P a / P o2 / …/ P a n / [31 / [32 / …/ p m 其中，a (I = 1, 2,…，n)都不为￡而每个p j (j = 1, 2,…，m) 都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归： P— p l P'/ 32 P'/…/p m P' P' — 01P' / a P'/…/ a n P'/￡ 实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境； 2、通过本实验加深对递归过程的理解 二、实验内容： 掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数，输出结果能够用递归方法实现整数的划分。 四、算法思想 对于数据n,递归计算最大加数等于x 的划分个数+最大加数不大于x-1的划分个数。最大加数x 从n 开始，逐步变小为n-1, (1) 考虑增加一个自变量：对于数据n,最大加数n1不大于m 的划分个数记作),(m n q 。则有： ???????>>=<==-+--+=1 1,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q 五、代码实现 #include "stdafx.h" #include return 0; } int q(intn,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 递归与分治实验报告 班级：计科1102 姓名：赵春晓学号：2011310200631 实验目的：进一步掌握递归与分治算法的设计思想，通过实际问题来应用递归与分治设计算法。 实际问题：1集合划分问题，2输油管道问题，3邮局选址问题，4整数因子分解问题，5众数问题。 问题1：集合划分 算法思想：对于n个元素的集合，可以划分为由m个子集构成的集合，例如{{1,2}{3,4}}就是由2个子集构成的非空子集。假设f（n，m）表示将n个元素划分成由m个子集构成的集合的个数。那么1）若m == 1 ，则f（n，m）= 1 ；2）若n == m ，则f（n，m）= 1 ；3）若不是上面两种情况则有下面两种情况构成：3.1）向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；3.2）向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。 实验代码： #include 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 兰州交通大学 《算法设计与分析》 实验报告3 题目03-动态规划 专业计算机科学与技术 班级计算机科学与技术2016-02班学号201610333 姓名石博洋 第3章动态规划 1. 实验题目与环境 1.1实验题目及要求 (1) 用代码实现矩阵连乘问题。 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。 确定一个计算顺序，使得需要的乘的次数最少。 (2) 用代码实现最长公共子序列问题。 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj 。例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。 (3) 0-1背包问题。 现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W i，价值为正整数V i，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分） 使用动态规划使得装入背包的物品价值之和最大。 1.2实验环境： CPU：Intel(R) Core(TM) i3-2120 3.3GHZ 内存：12GB 操作系统：Windows 7.1 X64 编译环境：Mircosoft Visual C++ 6 2. 问题分析 (1) 分析。 共享知识分享快乐 编译原理实验报告 实验名称消除文法左递归 实验时间2014年12月12日 院系软件工程 ______________ 班级软件工程（2）班 学号E01214215 __________ 姓名刘翼________________ 实验目的： 输入：任意的上下文无关文法。输出：消除了左递归的等价文法。 实验原理： 1．直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符P 的规则为 P—P a / B 其中，B是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式：P —B P' P'—a P' / ￡ 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。 设有简单表达式文法G[E] ： E —E+T/ T T —T*F/ F F —（E）/ I 经消除直接左递归后得到如下文法： E —TE' E ' —+TE' / ￡ T —FT' T' —*FT' / ￡ F —（E）/ I 考虑更一般的情况，假定关于非终结符P的规则为 P—P a 1 / P a 2 / …/ P a n / B 1 / B 2 / …/ B m 其中，a i （I = 1，2，…，n）都不为￡，而每个B j （j = 1，2，…，m都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归： P—B 1 P' / B 2 P' / …/ B m P' P' —a 1P' / a 2 P' / …/ a n P' / ￡ 2．间接左递归的消除 直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法G[S] ： S—Qc/ c Q—Rb/ b R—Sa/ a 虽不具有左递归，但S、Q R都是左递归的，因为经过若干次推导有 S Qc Rbc Sabc Q Rb Sab Qcab R Sa Qca Rbca 集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算12 姓名： 学号： 上机实践日期：2014.11 上机实践时间： 4学时 一、实验目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： (1) 掌握从源程序文件中读取有效字符的方法和产生源程序内部表示文件的方法； (2)掌握语法分析的实现方法； (3)上机调试编出的语法分析程序。 二、实验环境 Windows7 x64、VC6.0 三、实验原理 递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，可根据输入串的当前符号以及各产生式右部首符，选择某非终结符的产生式，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。即：假设A 的全部产生式为A →α1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式 First(A →αi )∩First (A →αj )=Φ,当i≠j. 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于人以非中介符号U 的产生式右部n x x x |...||21，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P P +?的推导），也不含以ε为右部的产生式，那么可以通过执行消除左递归的算法消除文法的一切左递归。 四、实验内容 完成以下描述算术表达式的LL(1)文法的递归下降分析程序构造 G[E]: E →TE ′ E ′→+TE ′|ε T →FT ′ 宁波工程学院电信学院计算机系 实验报告 课程名称：算法设计与分析实验项目：用分治法算法解 最接近点对问题 指导教师：崔迪 实验位置：软件工程实验室姓名： 班级： 学号： 日期： 2016/10/12 一、实验目的 通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设 计和算法复杂性分析等。 二、实验环境： Eclipse 三、实验内容：用分治法解最接近点对问题 （1）问题描述 给定平面S上n个点，找其中的一对点，使得在n(n-1)/2 个点对中，该 点对的距离最小。 （2）算法设计思想 1. n较小时直接求 (n=2). 2.将S上的n个点分成大致相等的2个子集S1和S2 3.分别求S1和S2中的最接近点对 4.求一点在S1、另一点在S2中的最近点对 5.从上述三对点中找距离最近的一对. （3）程序设计（程序清单及说明） package closestpair; import java.util.Arrays; import https://www.wendangku.net/doc/0c14158472.html,parator; import java.util.Random; import java.util.Scanner; //定义坐标点 class Point { double x; double y; public Point(double x, double y) { this.x = x; this.y = y; } } // 根据x坐标排序 class MyComparatorX implements Comparator 学生实验报告书 实验课程名称算法设计与分析开课学院计算机科学与技术学院 指导教师姓名李晓红 学生姓名 学生专业班级软件工程zy1302班2015-- 2016学年第一学期 实验课程名称：算法设计与分析 同组者实验日期2015年10月20日第一部分：实验分析与设计 一．实验内容描述（问题域描述） 1、利用分治法，写一个快速排序的递归算法，并利用任何一种语言，在计算机上实现，同时 进行时间复杂性分析； 2、要求用递归的方法实现。 二.实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） 本次的解法使用的是“三向切分的快速排序”，它是快速排序的一种优化版本。不仅利用了分治法和递归实现，而且对于存在大量重复元素的数组，它的效率比快速排序基本版高得多。 它从左到右遍历数组一次，维护一个指针lt使得a[lo..lt-1]中的元素都小于v，一个指针gt 使得a[gt+1..hi]中的元素都大于v，一个指针i使得a[lt..i-1]中的元素都等于v，a[i..gt]中的元素都还未确定，如下图所示： public class Quick3way { public static void sort(Comparable[] a, int lo, int hi) { if (lo >= hi) return; int lt = lo, i = lo + 1, gt = hi; Comparable pivot = a[lo]; 第二部分：实验调试与结果分析 一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等） 1、调试方法描述： 对程序入口进行断点，随着程序的运行，一步一步的调试，得到运行轨迹； 2、实验数据： "R", "B", "W", "W", "R", "W", "B", "R", "R", "W", "B", "R"； 3、实验现象： 4、实验过程中发现的问题： （1）边界问题： 在设计快速排序的代码时要非常小心，因为其中包含非常关键的边界问题，例如： 什么时候跳出while循环，递归什么时候结束，是对指针的左半部分还是右半部分 排序等等； （2）程序的调试跳转： 在调试过程中要时刻记住程序是对那一部分进行排序，当完成了这部分的排序后， 会跳到哪里又去对另外的那一部分进行排序，这些都是要了然于心的，这样才能准 确的定位程序。 二、实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等） 1、实验结果： 西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告 题目：分治法循环赛日程表 学号 姓名 专业班级 指导教师 实践日期2011年5月16日-5月20日 目录 一、综合训练目的与要求 (1) 二、综合训练任务描述 (1) 三、算法设计 (1) 四、详细设计及说明 (3) 五、调试与测试 (4) 六、实习日志 (6) 七、实习总结 (6) 八、附录：核心代码清单 (6) 一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务： （1）巩固和加深学生对算法分析课程基本知识的理解和掌握； （2）培养利用算法知识解决实际问题的能力； （3）掌握利用程序设计语言进行算法程序的开发、调试、测试的能力； （4）掌握书写算法设计说明文档的能力； （5）提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1天 利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。 三、算法设计 (1) 文字描述 假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手，根据分治法，要求n个选手的比赛日程，只要知道其中一半的比赛日程，所以使用递归最终可以分到计算两位选手的比赛日程，然后逐级合并，得出结果。 (2) 框图 院系：计算机科学学院 专业、年级： 07计科2大班 课程名称：编译原理 学号姓名： 指导教师： 2010 年11月17 日 组员学号姓名 实验 名称 实验一：词法分析实验室9205 实验目的或要求 通过设计一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 具体要求：输入为某语言源代码，达到以下功能： 程序输入/输出示例：如源程序为C语言。输入如下一段： main() { int a,b; a=10; b=a+20; } 要求输出如下（并以文件形式输出或以界面的形式输出以下结果）。 （2，”main”） （5，”（“） （5，”）“） （5，”{“} （1，”int”） （2，”a”） （5，”,”） （2，”b”） （5，”;”） （2，”a”） （4，”=”） （3，”10”） （5，”;”） （2，”b”） （4，”=”） （2，”a”） （4，”+”） （3，”20”） （5，”;”） （5，”}“） 要求： 识别保留字：if、int、for、while、do、return、break、continue等等，单词种别码为1。 其他的标识符，单词种别码为2。常数为无符号数，单词种别码为3。 运算符包括：+、-、*、/、=、>、<等；可以考虑更复杂情况>=、<=、!= ；单词种别码为4。分隔符包括：“，”“；”“（”“）”“{”“}”等等，单词种别码为5。 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 学生学号0120810680316 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称《编译原理》 开课学院计算机科学与技术学院 指导老师姓名何九周 学生姓名刘洋 学生专业班级软件工程0803 2010 —2011 学年第二学期 实验课程名称：编译原理 实验项目名称单词的词法分析程序设计实验成绩实验者刘洋专业班级软件0803 组别 同组者实验日期 2011 年 5 月 17日 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 实验目的： 设计，编制并调试一个词法分析程序，加深对词法分析原理的理解。 实验要求： 在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写；上机时应随带有关的高级语言教材或参考书；要学会程序调试与纠错；每次实验后要交实验报告。 实验题目： 对于给定的源程序（如C语言或Pascal等），要求从组成源程序的字符行中寻找出单词，并给出它们的种别和属性——输出二元组序列。以便提供给语法分析的时候使用。要求能识别所有的关键字，标志符等，并且能够对出先的一些词法规则的错误进行必要的处理。 二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或 者算法描述） 实验原理： 由于这是一个用高级语言编写一个词法分析器,使之能识别输入串,并把分析结果(单词符号,标识符,关键字等等)输出.输入源程序,输入单词符号,本词法分析器可以辨别关键字,标识符,常数,运算符号和某些界符,运用了文件读入来获取源程序代码,再对该源程序代码进行词法分析,这就是词法分析器的基本功能.当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号.当缓冲区里的字符串被处理完之后,它又调用预处理子程序来处理新串. 编写的时候，使用了文件的输入和输出，以便于词法分析的通用型，同时在文件输出时，并保存在输出文件output文件中。 从左到右扫描程序，通过初始化：1为关键字；2为标志符； 3为常数；4为运算符或界符。 三、主要仪器设备及耗材 计算机 实验一分治与递归算法的应用 一、实验目的 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。 二 . 实验内容 金块问题 老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三.问题分析: 一般思路：假设袋中有n 个金块。可以用函数M a x（程序 1 - 3 1）通过n-1次比较找到最重的金块。找到最重的金块后， 可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。 分治法：当n很小时，比如说，n≤2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法 程序设计 据上述步骤，可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。 当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。 首先处理n≤1的情况。若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。 在for 循环中，外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值， 编译原理实验报告 实验名称：编写语法分析程序 实验类型：设计性实验 指导教师：蒋勇 专业班级：软件工程1401 姓名：**** 学号：********** 实验地点：东六E座301 实验成绩：_________________ 日期：2016年5月17日 实验一 编写词法分析程序 一、实验目的： 1.设计、编写、调试一个递归下降分析程序，实现对词法分析程序提供的 单词序列进行语法检查和结构分析。 2.掌握递归下降语法分析方法。 3.巩固理论知识。 二、实验设计： 1.设计原理： 1)对于文法的每一个非终结符U的文法规则是一个识别U的过程定义， 为每一个非终结符构造子程序。 2)如果U的右部符号串只有一个候选式则从左到右依次构造U的识别 代码。 3)如果U的右部符号串有终结符号，则判断输入的符号是否匹配终结 符号，如果相等，则读入下一个符号；如果不相等，则有语法错误， 应当报错。 4)如果是非终结符号，则调用非终结符号的子程序即可。 5)如果U的右部有多个候选式，应该根据每个候选式的第一个符号来 确定该分支。 6)对于含有ε表达式的文法规则需要判断输入的符号是否在U的 FOLLOW集里面。 2.设计方法： (1)文法改造，消除二义性； (2)对含有左递归或者左公因子的文法消除左递归，提取左公因子； (3)求每一个右部符号串的FIRST集合，如果右部含有ε，则需要求出其 产生式左部非终结符的FOLLOW集。判断文法是否是LL（1）文法， 若不是LL(1)文法，说明文法的复杂性超过自顶向下方法的分析能力。 (4)根据改写后的文法设计程序，依据设计原理构造每一个非终结符的子 程序。 3.设计过程： (1)改写文法、消除左递归（将左递归改为右递归）、提取左公因子； (2)求出相应的First集和Follow集； (3)设计程序流程图，设计程序； (4)编写程序； 4.框架思路，错误信息输出： 对每一个非终结符构造其子程序，设定一个返回值。如果语法分析有错 则返回1，没有错误就返回0；对于错误，在程序的相应行数报错。各 个非终结符之间依据文法规则调用。每次遇到终结符函数都判断是否匹 配当前终结符号，如果不匹配则报错，返回1。如果匹配，则读入下一 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 消除文法的左递归实验
实验报告 分治与递归
算法设计与分析实验报告贪心算法
算法分析实验报告--分治策略
递归与分治实验报告
算法设计与分析实验报告
算法分析_实验报告3
消除左递归实验报告
编译原理-实验二-递归下降分析程序构造
分治法实验报告一
武汉理工大学算法分析实验报告
(完整word版)分治法循环赛日程表实验报告
编译原理实验报告
算法设计与分析：递归与分治法-实验报告
算法分析实验报告--分治策略
编译原理实验报告
算法实验报告
编译原理语法分析实验报告
算法设计与分析实验报告 统计数字问题
算法设计与分析实验报告