实验报告题目
实验一递归与分治策略
一、实验目的
1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二、实验内容
设计一个递归和分治算法，找出数组的最大元素，找出x在数组A中出现的次数。
三、实验要求
（1）用分治法求解…问题；
（2）再选择自己熟悉的其它方法求解本问题；
（3）上机实现所设计的所有算法；
四、实验过程设计（算法设计过程）
1.设计一个递归算法，找出数组的最大元素。
2.设计一个分治算法，找出x在数组A中出现的次数。
3.写一个主函数，调用上述算法。
五、实验结果分析
（分析时空复杂性，设计测试用例及测试结果）
时间复杂性：最好情况下，O(n)
最坏情况下：O(nlog(n)
空间复杂性分析：O(n)
六、实验体会
通过写递归与分治策略实验，更加清楚的知道它的运行机理，分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。做实验重在动手动脑，还是要多写写实验，才是硬道理。
七、附录：（源代码）
#include"stdio.h"
#define ElemType int
int count(ElemType a[],int i,int j,ElemType x)
{
int k=0,mid; //k用来计数，记录数组中x出现的次数if(i==j)
{
if(a[i]==x) k++;
return k;
}
else
{
mid=(i+j)/2;
k+=count(a,i,mid,x);
k+=count(a,mid+1,j,x);
}
return k;
}
ElemType Maxitem(ElemType a[],int n)
{
ElemType max=a[n-1],j;
if(n==1)
{
max=a[n-1];
return max;
}
else
{
j=Maxitem(a,n-1);
if(j>max) max=j;
return max;
}
}
void main(void)
{
ElemType a[]={1,5,2,7,3,7,4,8,9,5,4,544,2,4,123};
ElemType b;
ElemType x;
int n;
b=Maxitem(a,15);
printf("数组的最大元素为%d\n",b);
printf("输入想要计数的数组元素:\n");
scanf("%d",&x);
n=count(a,0,14,x);
printf("%d在数组中出现的次数为%d次\n",x,n);
}
实验二动态规划——求解最优问题
一、实验目的
1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二．实验内容
根据实验目的要求和实验条件，由学生运用所学知识，自行选择最优问题，自己设计算法，自行编程实现、自行对实验结果进行分析，自行完成实验项目报告的撰写等。在教师的指导下，最大限度发挥学生资助学习的积极性，为后续专业课的学习打下坚实基础。
三．实验要求
（1）用动态规划思想求解最优问题；
（2）再选择自己熟悉的程序设计语言实现所有算法；
（3）分析所设计的算法的时间/空间复杂性。
四．实验过程设计（算法设计过程）
实验3.3。先在a[]，b[]数组中选a[0]和b[0]开始，然后分别计算在以a[0]和b[0]开始的总的时间，再比较哪个最短。
五．实验结果分析
六．实验体会
始终觉得用代码写着比用笔直接计算要难点，不过代码解决的事一类问题，只需要输数据就可以。所以还是代码好，不过要有好的逻辑思维和方法，才能写出好的
七．附录：（源代码）
#include "stdio.h"
#include "iostream.h"
#include "string.h"
void main()
{
void sf(int a[],int b[],int n);
int a[100],b[100],n,i;
printf("请输入需要完成的作业数量：");
scanf("%d",&n);
printf("请输入A组机器完成作业对应的时间:");
for(i=0;i printf("请输入B组机器完成作业对应的时间:"); for(i=0;i f(a,b,n); } void f(int a[],int b[],int n) { int max(int a,int b); int i,j,d,low,high,k,A,B,v[100]; for(i=0;i { for(j=0;j { if(a[i] { d=a[i]; a[i]=a[j]; a[j]=d; d=b[i]; b[i]=b[j]; b[j]=d; } } } for(i=0;i { low=i; high=i; while(a[i]==a[i+1]) { i++; high=i; } if(low!=high) { for(k=low;k<=high;k++) { for(j=k;j<=high;j++) { if(b[k] { d=b[k]; b[k]=b[j]; b[j]=d; } } } } } for(i=0;i { A=0; B=0; j=0; while(j<=i) { A=A+a[j]; j++; } while(j { B=B+b[j]; j++; } v[i]=max(A,B); } i=1; d=v[0]; while(i { if(v[i] { d=v[i]; } i++; } printf("最短作业时间为：%d\n",d); } int max(int a,int b) { if(a>b) { return a; } else{ return b; } } 实验三贪心算法——“0/1背包”及“有限期作业调度” 一、实验目的 1．进一步理解算法设计的基本步骤及各步的主要内容、基本要求 2．加深对贪婪法算法设计方法的理解与应用 3．掌握将算法转化为计算机上机程序的方法 4．培养学生应用所学知识解决实际问题的能力。 二．实验内容 （1）给定n种物品和一个背包。物品I的重量是w i，其价值为p i，背包的容量为M。应如何选择装入背包的物品（每件物品可以全装也可以只装一部分），使得装入背包中物品的总价值最大? （2）给定n个作业j1, j2,…, j n。对每个作业j i，有一个与之联系的限期d i>0和收益p i≥0，d i，p i均为整数，1≤I≤n。对作业j i，只有在限期d i内完成，才能得到收益p i。假定只有一台处理机为这批服务业服务，处理机每次只能处理一个作业，并且完成一作业需一个单位时间。所谓一个可行解，是这批作业的一个子集J，J中每一作业均能在限期d i内完成。调度的总收益是子集J中各作业收益之和。具有最大收益的的可行解和为最优解。如何求其最优解？ 三．实验要求 （1）设计用贪婪法求解“背包问题”及“带有限期的计算机作业调度问题”的算法； （2）上机实现所设计的算法； （3）分析所设计的算法的时间/空间复杂性。 四．实验过程设计（算法设计过程） 后面人的等到时间等于前面人的服务时间，要总的等待时间最短，就要前面的服务时间最短，就需要先让服务时间段的人先进行服务。 1.先按原来的顺序服务时间服务，得到一个等待时间 2.升序排列后，得到一个等待时间 五．结果分析 六．实验体会 后面人的等到时间等于前面人的服务时间，要总的等待时间最短，就要前面的服务时间最短，就需要先让服务时间段的人先进行服务。这是总的实验思路。贪心算法就是要尽可能的提高效率，得到想要的效益。 七．附录（源代码） #include "stdio.h" #include "iostream.h" #include "string.h" main() { int i,j,n,a[100],d=0,k=0; printf("请输入顾客的总人数："); scanf("%d",&n); printf("依次输入每个顾客的服务时间:"); for(i=0;i for(i=0;i { d=0; for(int j=0;j { d=d+a[j];//第j个人的等待时间 } k=k+d;//总的等待时间 } printf("此时等待的总时间为：%d\n",k); for(i=0;i { for(int j=i;j { if(a[i]>a[j]) { d=a[i]; a[i]=a[j]; a[j]=d; } } } printf("按升序排列后的数组为："); for(i=0;i k=0; for(i=0;i { d=0; for(int j=0;j { d=d+a[j]; } k=k+d; } printf("\n此时等待的总时间为：%d\n",k); } 实验四回溯法——“N皇后”问题 一、实验目的 1．掌握能用回溯法求解的问题应满足的条件； 2．加深对回溯法算法设计方法的理解与应用； 3．锻炼学生对程序跟踪调试能力； 4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。 二．实验内容 由N2个方块排成N行N列的正方形，称为N元棋盘，在N元棋盘上放置N个皇后，如果某两个皇后位于N元棋盘的同一行或同一列或同一斜线（斜率为±1）上，则称它们在互相攻击，试设计算法找出使N个皇后互不攻击的所有布局。 三．实验要求 （1）用回溯法算法设计方法求解N元皇后问题 （2）找出N皇后问题的互不攻击的所有解 （3）皇后数N由键盘动态输入 （4）上机实现所设计的算法； （5）分析所设计的算法的时间/空间复杂性。 四．实验过程设计（算法设计过程） （1）分析N皇后问题的约束条件，并将其显示化，选择存储结构建立相应的数学模型； （2）根据所建立的数学模型，设计求解该问题的粗略算法； （3）对所设计的粗略算法求精，得具体算法； （4）在C/C++/VC++下实现所设计的算法； （5）分屏显示结果； （6）分析运行结果的正确性； （7）进行算法效率分析； （8）课后写出实验报告。 五．实验结果和分析 六．实验体会 解n后问题主要在于可行解，一个一个的试，（t）能走通就往(t+1)下走，走不通就倒回去(t-1)换条走，再不行再回走。就要不停的尝试，不停的回溯，直到找全可行解，或者一个也没有就停止。还有重要的事约束条件，两个皇后不能在同行同列或者斜线上。 七．附录（源代码） #include "stdio.h" #include "iostream.h" #include "string.h" #include int n; int x[100]; int sum=0; int k=1; int nQueen(int nn) { n=nn; void backtrack(int t); for(int i=0;i<=n;i++) { x[i]=0; } backtrack(1); return sum; } int place(int k) { 2012 -2013第一学期 for(int j=1;j { if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) { return 0; } } return 1; } void backtrack(int t) { if(t>n) { printf("第"%d"个解的答案为：",k); k++; sum++; for(int i=1;i<=n;i++)printf("%d",x[i]); } else { for(int i=1;i<=n;i++) { x[t]=i; if(place(t)) { backtrack(t+1); } } } } main() { int nn; printf("输入n皇后n值："); scanf("%d %d",&n,&n); nQueen(nn); } 2012 -2013第一学期 算法分析与设计实验报告 学生姓名：系别：专业与班号：学号： 实验名称:Strassen’s 矩阵乘法和最近点对算法 实验目的 1、理解“分治法”算法设计思想及其实现步骤 2、掌握分治算法效率递归分析方法 3、掌握主方式求解递归式方法 实验内容及要求 1、利用计算机程序设计语言，实现教材第28.2 章介绍的“Strassen’s 矩阵乘法算法”，自主生成两个8×8 的矩阵，检验算法的正确性并输出算法结果。 2、比较 Strassen’s 矩阵乘法算法和数学定义的矩阵乘法算法效率之间的区别，并用直观的表达方式把两种不同矩阵乘法的效率随矩阵维数的变化趋势。 3、利用计算机程序设计语言，实现教材第33.4 章介绍的“最近点对算法”，在拟定的二维空间点集上检验算法的正确性并输出算法结果。 实验原理 1.Strassen’s矩阵乘法简介 Strassen’s算法是将矩阵分成了如图所示的均等的四块。分后的每一块儿任然还是方阵。 所以可以由大问题分解成若干子问题进行解决。为了能使子问题能够返回到原始问题。 Strassen‘s算法提出了如下的计算公式，可以用矩阵的子矩阵计算出S1-S7，然后又由S1-S7合成原始矩阵。而S1-S7的计算又是方阵的乘法。由此使用分治算法便可以解决问题。 2.最近点对问题(Closest Pair Problems)算法简介 首先这个问题也是采用了分治的思想，将空间内的距离分成三类，分界线左边的点之间的距离，分界线右边的点之间的距离，还有分界线两边距离为D 的区域内的两点间距离。 算法具体代码 1.矩阵相乘问题 // Strassen.cpp : 定义控制台应用程序的入口点。 // //******************************************************************************** #include "stdafx.h" #include "stdlib.h" #define AM Copy(A,0,0,A.v/2) #define BM Copy(A,A.v/2,0,A.v/2) #define CM Copy(A,0,A.v/2,A.v/2) #define DM Copy(A,A.v/2,A.v/2,A.v/2) #define EM Copy(B,0,0,B.v/2) #define FM Copy(B,B.v/2,0,B.v/2) #define GM Copy(B,0,B.v/2,B.v/2) #define HM Copy(B,B.v/2,B.v/2,B.v/2) #define V 2 //******************************************************************************** //矩阵结构 typedef struct matrix { int v; int x[16][16]; }Matrix; //******************************************************************************** //输入输出文件 FILE *fout; FILE *fin; //******************************************************************************** //矩阵打印（文件） void fPrint(Matrix A) { for(int j=0;j 《算法设计与分析》实验报告实验三回溯法 3.迷宫问题 一天Luna在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，. 和#，前者表示可以通行后者表示不能通行。同时当Luna处在某个格点时，她只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Luna想要从点A走到点B（不能走出迷宫）。如果起点或者终点有一个不能通行(为#)，则看成无法办到。 [输入] 第1行是测试数据的组数k，后面跟着k组输入。 每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n 的。 接下来是一个n * n的矩阵，矩阵中的元素为. 或者#。 再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb 行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。 1.八皇后问题 1.1解题思路 八皇后问题的解法，很简单的解法。通过回溯实现枚举。 对于当前行，尝试是否可在当前列放置皇后，然后进入下一行的尝试，同时尝试完毕以后，要将当前行回复（回溯），来进行下一次尝试。 到达最后一行的时候，即递归结束条件，打印结果即可。 1.2程序运行情况 1.3所有的皇后解 见附录。（毕竟92个解...） 1.4程序源码（含注释） 2. 24点问题 2.1 解题思路 这题虽然使用dfs很简单，但是有一点思维在里面。我很惭愧，自己没有想出来怎么如意的独立AC此题。 遇到的最大的问题——如何插入括号？枚举插入、和运算符一同排列都不靠谱。解决方法是：用同等的办法转化。每一次从待组合的是数字中，任取两个数，随机用运算符计算完毕后，再放回去。下一次计算，再次重复这个过程，可以等价为有括号的运算方式了。 遇到第二个问题——如何实现这种“任取两个数”的选择方式。这里就直接体现出了我个人能力的不足。居然没想到。尝试使用STL的set，但是没成功。这里借鉴了网上的AC 思路，我感到自己思维太僵硬。解决方法是——对于当前的运算状态中，用两个循环实现枚举两个数，计算为完毕以后，结果覆盖在数组序号小的那个数的位置，再将第二个数与最后一个数字交换即可进入下一个状态。回溯的时候，只需要回复小序号的数字的位置的值，以及再一次swap即可。（因为第二个数字只是swap却没有改变过内容）。 一个细节问题，就是加法和乘法是没有顺序的，减法和除法是有顺序的，以及除法要考虑0异常。一共是6次枚举即可。 2.2 测试样例 5 5 5 1 ans is YES 1 1 4 2 ans is :NO 2.3 程序运行情况 样例一： 实验一递归1.1实验目的 1）掌握递归算法的概念，理解递归算法的思想 2）掌握递归函数的写法，熟练运用递归函数 3）正确分析递归算法的时空复杂度 1.2 实验内容 1）编写程序递归地实现阶乘函数； 2）编写程序递归地实现Fibonacci数列； 3）编写程序递归实现整数划分问题 1.3 实验步骤 1）写出阶乘函数的定义公式 n!=1 n=0 n n?1! n>0 2）创建一个java程序，递归实现阶乘函数public static int factorial(int n) { if(n==0) return 1; return n*factorial(n-1); } 3）写出Fibonacci数列的定义公式 F n=1 n=0,1 F n?1+F n?2 n>1 4）创建一个java程序，递归实现Fibonacci数列public static int fibonacci(int n) { if(n<=1) return 1; return fibonacci(n-1)+fibonacci(n-2); } 5）分析并写出整数划分的递归公式 q n,m=1 n=1,m=1 q n,n n public static int q(int n,int m) { if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n 实验一分治与递归（4学时） 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境； 2、通过本实验加深对递归过程的理解 二、实验内容 掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数，输出结果能够用递归方法实现整数的划分。 四、程序代码 五、实验结果 首先按照提示输入数字： 按回车键，得到此数划分的个数： 此时您可以接着计算另一个数的划分个数： 若要退出，请输入一个小于等于零的数： 六、结果分析及程序功能 经过和其它同学的实验数据对比，初步认定此程序基本正确，然而不足之处是只能得到划分的个数，而不能列出每个划分的详细情况。 一、实验目的与要求 1、掌握棋盘覆盖问题的算法； 2、初步掌握分治算法 二、实验题 盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 三、程序代码 四、实验结果 按照提示输入特殊方格的行号和列号（起始行列号为0）： 按回车键，得到一个矩阵，数字相同区域为一个L型骨牌覆盖： 五、结果分析及程序功能 得到的16*16棋盘覆盖结果正确，此程序的不足之处：只能设定特殊方格的行列号，而不能设定棋盘的大小。 实验二动态规划算法(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的公共子序列。 三、实验程序 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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．代码设计： 算法设计与分析实验报告棋盘覆盖问题贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告课程名称:算法设计与分析班级:信计101班实验日期:2013-9-30 姓名: 张胜学号:1007010162 指导教师:程欣宇实验序号:一实验成绩: 一、实验名称 分治算法实验 - 棋盘覆盖问题 二、实验目的及要求 1、熟悉递归算法编写; 2、理解分治算法的特点; 3、掌握分治算法的基本结构。 三、实验环境 Visual C++ 四、实验内容 根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验; 要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。 五、算法描述及实验步骤 分治算法原理: 分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。 棋盘覆盖问题描述: 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌(每个骨牌可覆盖三个方格)不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。 实验步骤: 1、定义用于输入和输出的数据结构; 2、完成分治算法的编写; 3、测试记录结构; 4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么, 六、调试过程及实验结果 实验运行结果: 七、总结 通过本次实验，我更深的理解了递归和分治策略。代码是书上的算法，加上主函数就行了，用的是C语言编写，很长时间没用了，感觉有点生疏。实验结果有点 问题，就是覆盖棋盘时，并不是按照1，2，3….的字符顺序，而是按照很乱的顺序输出字符，这个我不知道怎么解决，就没解决。 八、附录 #include "stdio.h" #include "conio.h" int board[8][8] ={ {0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0 ,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0} }; int tile=0; void chessBoard(int tr, int tc, int dr, int dc, int size) { int t=tile++, s=size/2; if (size==1) return; if (dr 实验报告 课程计算机算法设计与分析实验名称合并排序、快速排序学号姓名实验日期： 实验一合并排序、快速排序 一．实验目的 （1）学习合并排序和快速排序算法的思想，掌握原理。 （2）运用合并排序和快速排序算法的思想进行编程实现，以加深理解。二．实验内容 （1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。（2）输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果三．实验代码 (1)合并排序源代码如下： #include 自然语言处理算法实验报告 一、引言 自然语言处理（Natural Language Processing，简称NLP）是人工智能领域中与人类自然语言交互相关的研究方向。随着计算机技术的发展，NLP在机器翻译、问答系统、情感分析等领域得到广泛应用。本次实验旨在探索和评估常见的NLP算法在文本分类任务上的效果。 二、实验设计 本实验使用了常见的NLP算法，包括词袋模型(Bag-of-Words，简称BoW)、TF-IDF算法和词嵌入(Word Embedding)技术。我们选取了经典的文本分类数据集进行实验，包括20类新闻文本集合以及影评文本集合。实验采用Python作为编程语言，并使用Scikit-learn和Gensim 等开源库进行实现。 三、数据预处理 在进行实验之前，我们对原始数据进行了一系列的预处理工作。首先，我们去除了文本中的标点符号、数字和停用词。然后，我们使用分词工具对文本进行分词处理，将文本转化为词语序列。最后，我们采用词干提取或词形还原等方法对词语进行归一化处理，以减少词语形态的差异对文本分类效果的影响。 四、词袋模型 词袋模型是一种常见的表示文本的方法。在词袋模型中，我们将文本表示为一个向量，向量的每个维度表示一个词语在文本中的出现频率。在实验中，我们使用了词频和TF-IDF两种方法来构建词袋模型，并使用朴素贝叶斯分类器进行分类。 五、TF-IDF算法 TF-IDF算法是一种衡量一个词语在文本中重要性的方法。它综合考虑了词语在文本中的出现频率以及在整个语料库中的逆文档频率。在实验中，我们使用TF-IDF算法构建了文本的特征向量，并使用支持向量机分类器进行分类。 六、词嵌入技术 词嵌入技术是一种将文本映射到低维度连续向量空间的方法。在实验中，我们使用了Word2Vec模型进行词嵌入训练，并将得到的词向量作为文本的特征表示。我们使用了多层感知器(MLP)分类器进行分类，并通过调整词向量的维度和训练步数等参数来优化实验结果。 七、实验结果与分析 我们将实验结果与基准算法进行比较，包括随机分类器和朴素贝叶斯分类器。实验结果表明，词袋模型在文本分类任务上具有一定的效果，在测试集上平均准确率达到了80%以上。TF-IDF算法相对于词袋模型有了一定的提升，平均准确率达到了85%以上。词嵌入技术在文本分类任务上表现出色，在测试集上平均准确率达到了90%以上。 八、结论与展望 算法设计与分析实验报告 算法设计与分析实验报告 一、引言 在计算机科学领域，算法设计与分析是非常重要的研究方向。本次实验旨在通过实际案例，探讨算法设计与分析的方法和技巧，并验证其在实际问题中的应用效果。 二、问题描述 本次实验的问题是求解一个整数序列中的最大子序列和。给定一个长度为n的整数序列，我们需要找到一个连续的子序列，使得其和最大。 三、算法设计 为了解决这个问题，我们设计了两种算法：暴力法和动态规划法。 1. 暴力法 暴力法是一种朴素的解决方法。它通过枚举所有可能的子序列，并计算它们的和，最终找到最大的子序列和。然而，由于需要枚举所有子序列，该算法的时间复杂度为O(n^3)，在处理大规模数据时效率较低。 2. 动态规划法 动态规划法是一种高效的解决方法。它通过定义一个状态转移方程，利用已计算的结果来计算当前状态的值。对于本问题，我们定义一个一维数组dp，其中dp[i]表示以第i个元素结尾的最大子序列和。通过遍历整个序列，我们可以利用状态转移方程dp[i] = max(dp[i-1]+nums[i], nums[i])来计算dp数组的值。最后，我们返回dp数组中的最大值即为所求的最大子序列和。该算法的时间复杂度为O(n)，效率较高。 四、实验结果与分析 我们使用Python编程语言实现了以上两种算法，并在相同的测试数据集上进行了实验。 1. 实验设置 我们随机生成了1000个整数作为测试数据集，其中包含正数、负数和零。为了验证算法的正确性，我们手动计算了测试数据集中的最大子序列和。 2. 实验结果 通过对比实验结果，我们发现两种算法得到的最大子序列和是一致的，验证了算法的正确性。同时，我们还对两种算法的运行时间进行了比较。结果显示，暴力法的运行时间明显长于动态规划法，进一步证明了动态规划法的高效性。 五、实验总结 通过本次实验，我们深入了解了算法设计与分析的方法和技巧，并通过实际案例验证了其在解决实际问题中的应用效果。我们发现，合理选择算法设计方法可以提高算法的效率，从而更好地解决实际问题。 然而，本次实验只涉及了一个简单的问题，实际问题往往更加复杂。在实际应用中，我们需要根据具体问题的特点选择合适的算法，并进行优化。同时，算法的正确性和效率也需要通过大规模测试数据进行验证。 综上所述，算法设计与分析是计算机科学领域中至关重要的研究方向。通过不断学习和实践，我们可以不断提高自己的算法设计与分析能力，为解决实际问题提供更好的解决方案。 算法设计与分析实验报告（三） 一、实验内容： 设有n个运动员要进行网球循环赛。设计一个满足下列条件的比赛日程表： 每个选手必须与其他n-1个选手各赛一次； 每个选手一天只能赛一次； 当n是偶数时，循环赛进行n-1天。当n是奇数时，循环赛进行n天。 二、算法思想与设计描述： 1、当n为1时，可以直接安排比赛shedule[1][1] = 1； 2、当n为奇数时，虚加上一个队员，变为偶数后处理，Schedule(schedule, n+1)，递归 调用结束后再将有虚拟队员的地方轮空（变为0）； 3、当n为偶数时，求解其子问题n/2，Schedule(schedule, n/2)。递归调用结束后，用 递归产生的队员数为n/2的日程表来生成队员数为n的日程表，这又分为以下两种 情况： （1）n/2为偶数。此时将队员数为n/2的数组向下、向右做拓展。行（或列）数相差n/2的地方，值也相差n/2，schedule[i+m][j] = schedule[i][j]+m; schedule[i][j+m] = schedule[i][j]+m;(m=n/2)。而又下角的部分直接将n/2的数 组复制过去schedule[i+m][j+m] = schedule[i][j]。如图： （2）n/2为奇数。先向下拓展，如果没有轮空时，schedule[i+m][j] = schedule[i][j]+m。 有轮空时，让同一天被轮空的两个人比赛，schedule[i][j] = i+m; schedule[i+m][j] = i。此时仅安排了n/2天，后（n/2）-1天的安排如下： 根据图中规律可得以下计算方法（m=n/2） for(i=1; i<=m; i++)//后几天安排 { for(j=m+2; j<=n; j++) { if(i+j-1 <= n) { schedule[i][j] = i+j-1; schedule[i+j-1][j] = i; } else { schedule[i][j] = i+j-m-1; schedule[i+j-m-1][j] = i; } } } 4、相关函数说明： （1）void Schedule(int schedule[][MAX_PLAYER], int n)//求日程表的递归函数，主要思想就是上述1、2、3所介绍的框架 （2）void Empty(int schedule[][MAX_PLAYER], int n)//轮空虚拟的队员 （3）void Copy(int schedule[][MAX_PLAYER], int n)//合并函数 （4）void CopyOdd(int schedule[][MAX_PLAYER], int n)// n为偶数且n/2为奇数时的日程表安排 （5）void CopyEven(int schedule[][MAX_PLAYER], int n)//n为偶数且n/2为偶数时的日程表安排 （6）int OddOrEven(int n)//判断一个整型数的奇偶性 三、测试说明： （1）n为奇数时（例如5），比赛n天（注意第一列表示的是参加比赛的队员，日程从第二列开始计）： （2）n为偶数时，比赛（n-1）天： 算法设计与分析实验报告 实验一全排列、快速排序 【实验目的】 1. 掌握全排列的递归算法。 2. 了解快速排序的分治算法思想。 【实验原理】 一、全排列 全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n 个数字的排列为例说明排列的生成法。 n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。 二、快速排序 快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再 按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 【实验内容】 １.全排列递归算法的实现。２.快速排序分治算法的实现。 【实验结果】 １. 全排列： ２. 快速排序： 实验二最长公共子序列、活动安排问题 【实验目的】 １. 了解动态规划算法设计思想，运用动态规划算法实现最长公共子序列问题。２. 了解贪心算法思想，运用贪心算法设计思想实现活动安排问题。 【实验原理】 一、动态规划法解最长公共子序列 设序列X=和Y=的一个最长公共子序列Z=，则： i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列； ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列； iii. 若xm≠yn且z k≠yn ，则Z是X和Yn-1的最长公共子序列。 其中Xm-1=，Yn-1=，Zk-1=。 （四） 一、实验内容： 二、算法思想与设计描述： 1、用二元组D(x,y)描述问题（源程序里是FindMax()），D(x,y)表示从第x层第y个位置 到达底层的最大路径得分。原问题的最大路径得分即为D(1,1)。 2、最优子结构性质：显然，D(x,y)的最优路径path(x,y)一定包含子问题D(x+1,y)或 D(x+1,y+1)的最优路径，否则，取D(x+1,y)和D(x+1,y+1)的最优路径中得分大的那条路径加上第x层第y个位置构成的路径得分必然大于path(x,y)的得分，这与path(x,y)的最优性矛盾。 3、递归关系： D(x,y) = max{D(x+1, y), D(x+1, y+1)}+a(x,y) D(n,k)=a(n,k), k=1,2……,n 其中，a(x,y)为第x层第y个位置的数值。 原问题的最大路径得分即为D(1,1) 4、相关函数说明： int FindMax(int pyramid[][MAX_LAYER+1], int n, int i, int j)//寻找价值最大路径 { path[i]=pyramid[i][j];//记录最大值路径 if(i == n)//到达底层，直接返回该位置钻石值 { return pyramid[i][j]; } else//未到达底层 { num++; //返回下一层两个元素到底层的最大钻石值加上本层钻石值 if(FindMax(pyramid, n, i+1,j) > FindMax(pyramid, n, i+1,j+1)) return FindMax(pyramid, n, i+1,j) + pyramid[i][j]; else return FindMax(pyramid, n, i+1,j+1) + pyramid[i][j]; } } 三、测试说明： 算法时间复杂度：O(n^2) 四、实验总结： 分治法分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。 在用分治法求解时，有些子问题被重复计算了许多次，时间复杂性呈指数增长。而动态规划使用最优子结构避免了大量重复计算。 昆明理工大学信息工程与自动化学院学生实验报告 （ 2011 — 2012 学年 第 1 学期 ） 课程名称：算法设计与分析 开课实验室：信自楼机房444 2012 年12月 14日 一、上机目的及内容 1.上机内容 给定有n 个整数（可能有负整数）组成的序列（a 1,a 2,…,a n ），求改序列形如∑=j k k a 1 的子段和的最大 值，当所有整数均为负整数时，其最大子段和为0。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不 同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； 蛮力法设计原理： 利用3个for 的嵌套（实现从第1个数开始计算子段长度为1，2，3…n 的子段和，同理计算出第2个数开始的长度为1，2，3…n-1的子段和，依次类推到第n 个数开始计算的长为1的子段和）和一个if （用来比较大小）,将其所有子段的和计算出来并将最大子段和赋值给 summax1。用了3个for 嵌套所以时间复杂性为○(n 3 )； 分治法设计原理： 1）、划分：按照平衡子问题的原则，将序列（1a ，2a ，…， n a ）划分成长度相同的两个字序 列（1a ，…， ⎣⎦ 2/n a ）和（ ⎣⎦1 2/+n a ，…， n a ）。 2）、求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在两端之间需要分别计算s1=⎣⎦ ⎣⎦)2/1(max 2/n i a n i k k ≤≤∑=，s2=⎣⎦⎣⎦)2/(max 1 2/n j n a j n k k ≤≤∑+=，则s1+s2 为最大子段和。若然只在左边或右边，那就好办了，前者视s1为summax2,后者视s2 o summax2。 3）、合并：比较在划分阶段的3种情况下的最大子段和，取三者之中的较大者为原问题的解。 4）、时间复杂性分析: f(n) = 2*f(n/2) + ○(n/2), 最后为○(nlogn)。 动态规划法设计原理： 动态规划法求解最大字段和问题的关键是要确定动态规划函数。记 )1(max )(1n j a j b i i k k j i ≤≤⎭ ⎬⎫ ⎩⎨⎧=∑=≤≤ 则 {})(max max max max 1111j b a a n j j i k k j i n j j i k k n j i ≤≤=≤≤≤≤=≤≤≤=⎭⎬⎫ ⎩⎨⎧=∑∑ 由b （j ）的定义，当b （j-1）>0是，b （j ）=b （j-1）+a ，否则，b （j ）=a 。可得如下递推式： )1()(0)1(0 )1()1({ n j j b j b j b a j b a j j ≤≤=>-≤-+- 代码实现过程中只用了一个for, 时间复杂性为：○(n) （2）对所设计的算法采用大O 符号进行时间复杂性分析； 蛮力法时间复杂性为○(n 3 )； 分治法时间复杂性为○(nlogn) 动态规划法时间复杂性为：○(n) （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； 详情见运行结果。 （4）通过分析对比，得出自己的结论。 结论：蛮力法只可以处理小理的数据。当数据量超过10000时，由蛮力法要等很久才输出，所以数据量超过10000时，就比较分治法和动态规划法。由实验结果可知，动态规划法所用的时间要少。 算法实验报告范文 《算法设计与分析》 实验报告 班级姓名学号 年月日 目录 实验一二分查找程序实现…………………………………………………………………03页实验二棋盘覆盖问题（分治法）.…………………………………………………………08页实验三0-1背包问题的动态规划算法设计……………………………………………….11页 实验四背包问题的贪心算法………………………………………………………………14页实验五最小重量机器设计问题（回溯法）………………………………………………17页 实验六最小重量机器设计问题（分支限界法）…………………………………………20页 指导教师对实验报告的评语 成绩： 指导教师签字： 年月日 2 实验一：二分查找程序实现 一、实验时间：2022年10月8日，星期二，第一、二节地点：J13#328 二、实验目的及要求目的： 1、用c/c++语言实现二分搜索算法。 2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。 三、实验环境 平台：Win732位操作系统开发工具：Codeblock10.05 四、实验内容 对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素某。 五、算法描述及实验步骤 算法描述： 折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的某作比较，如果某=a[n/2]则找到某，算法终止。如果某a[n/2]，则我们只要在数组a的右半部继续搜索某。二分搜索法的应用极其广泛，而且它的思想 算法设计与分析实验报告 实验名称：矩阵乘法(分冶法) 一、问题陈述和分析： 1.实验目的：掌握分总冶策略的基本思想以及用分冶法解决问题的一般技巧．运用编程工具，并运用分冶法来解决矩阵乘法问题； 2.实验内容：设A 和B 是两个n * n阶矩阵，求它们两的乘积矩阵C。这里，假设n是2的幂次方； 3.实验要求：编制程序并对其时间复杂度和空间复杂度进行分析. 二、模型拟制、算法设计和正确性证明： 设A和B是两个n*n阶矩阵，求他们两的成绩矩阵C。这里假设n是2的幂次方； A和B是两个n*n的矩阵，他们的乘积C=AB也是一个n*n的矩阵，矩阵C中的元素C[i][j]定义为C[i][j]= ，则每计算一个C[i][j]，需要做n次乘法和n-1次加法。因此计算C的n2个元素需要n3次乘法和n3- n2次加法。因此，所需的时间复杂度是O(n3)。 但是使用分治法可以改进算法的时间复杂度。这里，假设n是2的幂。将矩阵A,B,C中每一矩阵都分成4个大小相等的子矩阵，每个子矩阵是（n/2）*（n/2）的方阵。由此，可将方阵C=AB重写为 因此可得： C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B22 C22=A21B12+A22B22 这样就将2个n阶矩阵的乘积变成计算8个n/2阶矩阵的乘积和4个n/2阶矩阵的加法。 当n=1时，2个1阶方阵的乘积可直接算出，只需要做一次乘法。当子矩阵阶n>1时，为求两个子矩阵的乘积，可继续对两个子矩阵分块，直到子矩阵的阶为1。由此，便产生了分治降阶的递归算法。 但是这个算法并没有降低算法的时间复杂度。由strassen矩阵乘法， M1=A11（B12-B22） M2=（A11+A12）B22 M3=（A21+A22）B11 M4=A22（B21-B11） M5=（A11+A22）（B11+B22） M6=（A12-A22）（B21+B22） M7=(A11-A21)(B11+B12) C11=M5+M4-M2+M6 C12=M1+M2 C21=M3+M4 C22=M5+M1-M3-M7 算法共进行7次举证乘法，算法效率得到降低 主要数据的定义： int n；n是方阵A,B,C的阶 算法设计及实验报告 实验报告1 递归算法 一、实验目的 掌握递归算法的基本思想； 掌握该算法的时间复杂度分析； 二、实验环境 电脑一台，Turbo C 运行环境 三、实验内容、步骤和结果分析 以下是四个递归算法的应用例子：用C语言实现 1.阶乘： main() {int i,k; scanf("%d\n",&i); k= factorial(i); printf("%d\n",k); } int factorial(int n) { int s; if(n==0) s=1; else s=n*factorial(n-1); //执行n-1次 return s; } 阶乘的递归式很快，是个线性时间，因此在最坏情况下时间复杂度为O(n)。2.Fibonacci 数列： main() {int i,m; scanf("%d\n",&i); m=fb(i); printf("%d",m); } int fb(int n) {int s; if(n<=1)return 1; else s=fb(n-1)+fb(n-2); return s; } Fibonacci数列则是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由递归方程式可以知道他的时间复杂度T(n)是O(2n)，该数列的规律就是不停的赋 值，使用的内存空间也随着函数调用栈的增长而增长。 3.二分查找（分治法） #include算法分析与设计实验报告一
算法设计与分析---回溯实验报告
算法设计与分析实验
算法与设计实验报告
算法设计与分析实验报告
算法设计与分析实验报告棋盘覆盖问题
算法分析与设计实验报告-合并排序、快速排序
自然语言处理算法实验报告
算法设计与分析 实验报告
算法设计与分析实验报告-网球循环赛
算法设计与分析实验报告
算法设计与分析实验报告-砖石矿工问题
算法实验3-最大子段和问题实验报告
算法实验报告范文
矩阵乘法(分治法)
算法设计及实验报告
相关主题
文本预览