算法设计与分析报告
学生姓名
学号
专业班级
指导教师
完成时间
目录
一、课程内容 (3)
二、算法分析 (3)
1、分治法 (3)
（1)分治法核心思想 (3)
（2）MaxMin算法分析 (3)
2、动态规划 (4)
（1）动态规划核心思想 (4)
（2）矩阵连乘算法分析 (5)
3、贪心法 (5)
(1）贪心法核心思想 (5)
（2）背包问题算法分析 (6)
（3）装载问题算法分析 (7)
4、回溯法 (7)
（1）回溯法核心思想 (7)
（2)N皇后问题非递归算法分析 (7)
(3）N皇后问题递归算法分析 (8)
三、例子说明 (9)
1、MaxMin问题 (9)
2、矩阵连乘 (10)
3、背包问题 (10)
4、最优装载 (10)
5、N皇后问题(非递归） (11)
6、N皇后问题(递归) (11)
四、心得体会 (12)
五、算法对应的例子代码 (12)
1、求最大值最小值 (12)
2、矩阵连乘问题 (13)
3、背包问题 (15)
4、装载问题 (17)
5、N皇后问题(非递归） (19)
6、N皇后问题(递归） (20)
一、课程内容
1、分治法,求最大值最小值，maxmin算法；
2、动态规划，矩阵连乘，求最少连乘次数；
3、贪心法，1）背包问题，2）装载问题；
4、回溯法，N皇后问题的循环结构算法和递归结构算法。
二、算法分析
1、分治法
（1）分治法核心思想
当要求解一个输入规模为n,且n的取值相当大的问题时，直接求解往往是非常困难的。如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1 那末，这类问题可以用分治法求解。 分治法的核心技术 1)子问题的划分技术. 2）递归技术。反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。 3)合并技术. （2）MaxMin算法分析 问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。 分治策略设计思想： 将任一实例I＝（n，A（1)，…，A（n）)分成两个实例如果MAX1和MIN1是I1中的最大和最小元素，MAX2和 MIN2是I2中的最大和最小元素， MAX1和MAX2中的大者就是I 中的最大元素MAX， MIN1和MIN2中的小者是I中的最小元素MIN。如果I只包含一个元素,则不需要作任何分割直接就可得到其解。 核心算法如下： procedure MAXMIN（i，j,fmax,fmin) global n，A[1:n］ case ｛ i ＝j ： fmax ←fmin ←A ［i ］ /*只有一个元素＊/ i ＝j-1：if A[i ］ 〈A[j ］ then /*两个元素*/ fmax ←A ［j ］ ；fmin ←A ［i ］ else fmax ←A[i] ;fmin ←A[j ］ else ：mid ← /＊分成两部分*/ MAXMIN(i,mid ，max1,min1） MAXMIN （mid+1，j ，max2，min2) fmax ←max(max1，max2） fmin ←min(min1，min2） ｝ MAXMIN 的时间复杂性分析 用T(n)表示比较次数，则所导出的递归关系式： ⎣⎦⎡⎤⎪⎩ ⎪⎨⎧++=2)2/()2/(1 0)(n T n T n T 当n 是2的幂时,即对于某个正整数k ，n=2k,有 T （n)=2T （n/2）+2 =2(2T （n/4)+2）+2 =4T(n/4）+4+ =2k —1T(2）+2k —1+……+2 =2k —1+2k-2 =3n/2-2 对于任意 n ，存在整数k ，有2k-1 2、动态规划 (1）动态规划核心思想 动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算,从而得到多项式时间算法。 设计动态规划法的步骤： 1、划分阶段（子问题),分析最优子结构性质。 2、找出阶段间的最优决策的递推关系，写出动态规划方程； 3、设计自底向上计算出最优值的步骤. 4、从最终决策的回溯子问题的决策,构造一个最优解。 （2）矩阵连乘算法分析 问题：给定n个矩阵｛A1,A2，…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 两个矩阵相乘所需做的数乘次数为 l*n*m，矩阵乘法满足结合律，故矩阵连乘有可以有许多不同的计算顺序。计算顺序由加括号的方式确定，加括号的方式决定了矩阵连乘的计算量。 核心算法如下： 依次计算各层的子问题集 r=1，初始化 for i ← 1 to n do m[i][i］← 0 从 r=2至 r=n for r← 2 to n do 计算所有大小为r的子问题 MatrixChain（p[0：n]， n，m[1：n］［1：n],s ［1:n］［1：n］） ｛ 1) for i ← 1 to n do //初始化 m［i］[i] ← 0 2) for r ← 2 to n do // 子问题由小到大 3） for i ← 1 to n — r+1 do //子问题的起点 4）｛j←i+r-1 //子问题的终点 5) m[i］[j]←m［i+1]［j］+ p［i—1］*p[i］*p［j］ // 初值考虑 6) s[i]［j］← i // 记录分割点 7) for k← i+1 to j-1 do //求最好的分割k 8) ｛ t←m[i][k] + m[k+1］[j] + p［i-1］＊p［k]＊p[j］; 9) if t 〈 m［i］[j] then 10) ｛ m[i]［j］← t 11) s[i][j] ← k } ｝｝ ｝ 3、贪心法 (1）贪心法核心思想 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择.希望通过局部最优选择，达到全 局的最优 作出贪心决策的依据称为贪心准则(greedy criterion)。 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。 贪心法一般方法 1）根据题意,选取一种量度标准。 2）按这种量度标准对这n 个输入排序, 3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 （2）背包问题算法分析 问题:已知有n 种物品和一个可容纳M 重量的背包，每种物品i 的重量为wi 。假定将物品i 的一部分xi 放入背包就会得到pixi 的效益，这里，0≤xi ≤1，pi>0.如果这些物品重量的和大于M ，要求所有选中要装入背包的物品总重量不得超过M,而装入背包物品获得的总效益最大。即 , max 1i i i x p ∑≤≤M x w i n i i =∑≤≤1 满足约束条件的任一集合(x1，…，xn)是一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。 核心算法如下： 用利润/重量为量度 即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装人次序按pi/wi 比值的非增次序来考虑。 procedure KNAPSACK(real P,W ，M,X ，n) { //P(1：n)和W （1:n ）分别是n 个物品的重量，它们已按 P(i ）/W （i ）≥P （i+1)/W(i+1）排序，x(1:n ）是解向量// real cu ；int i ，n ； X ←0 //将解向量初始化为零// cu ←M //cu 是背包剩余容量// for i ←1 to n do ｛if W[i ］>cu then break X[i] ←1 cu ←cu —W ［i ］ ｝ if i ≤n then X ［i ］ ←cu/ W ［i ］ } (3）装载问题算法分析 问题:有一批集装箱要装上一艘载重量为M的轮船。其中集装箱i的重量为Wi。 最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船 设装载入船的集装箱的子集为S max｛∑i | i ∈S,1≤i ≤n} 约束∑w[i］≤M ,1≤i ≤n, i ∈S 核心算法如下: 采用重量最轻者先装的贪心选择策略 Loading( M， n) global W［1.。n]，X［1。.n] // W[1.。n] 为非递减序 X ←0 // 解向量清0 cu ←M for i←1 to n do { if cu break X［i］← 1 cu ← cu —W[i］ } 4、回溯法 （1）回溯法核心思想 回溯法是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略,从根结点出发搜索解空间树. 算法搜索至解空间树的任意一点时，先判断该结点是否满足约束。如果不满足,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯；否则，进入该子树,继续按深度优先策略搜索。 回溯法的一般步骤： （1)针对所给问题，定义问题的解空间； （2)确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。 (2）N皇后问题非递归算法分析 问题：n皇后问题可以表示成n—元组(x1,…，xn）,其中xi是放在第i行的皇后所在的 列号.于是，解空间由nn个n—元组组成。 显示约束条件为Si={1，2,……。，n｝,1i n。 隐式约束条件之一为没有两个xi相同(即任意两个皇后不在同一列上）。将其加入到显式条件中，于是解空间的大小由nn个元组减少到n!个元组。 核心算法如下： procedure NQUEENS（n) X（1)←0；k←1 //k是当前行；X（k)是当前列// While k>0 do //对所有的行执行以下语句// 1）｛ X（k)←X（k）+1 //移到下一列// While X（k)≤n and not PLACE(k) do 2) X(k）←X(k)十l if X（k）≤n //找到一个位置// then if k=n //是一个完整的解吗// then print(X） //是，打印这个数组// 3） else {k←k+1；X(k）←0；｝ 4） else k←k－1 //回溯// ｝ end NQUEENS 测试X(K)是否合理 procedure PLACE(k） //如果一个皇后能放在第k行和X(k)列，则返 回true;否则返回false。X是一个全程数 组，进入此过程时已置了k个值。// global X（1：k); integer i，k i←1 while i if X (i）＝X（k） //在同一列有两个皇后// or ABS（X（i)－X(k))＝ABS（i－k） //在同——条斜角线上// then return（false） endif i←i+1 repeat return（true） //满足约束// end PLACE (3）N皇后问题递归算法分析 使用递归算法使，反复的调用判断函数，判断后在决定位置。 核心算法如下： public void setposition(int n） //n表示在第n行，table［n]表示列数 ｛ for(int i = 0； i <= 5； i++） //i表示在第i列上放置皇后 ｛ x［n] = i； if（place（n）==false ） //如果没有皇后在同一列或斜线上（因为是按行依次放置故不可能在同一行上,又因为是每一行是从左到右放置故不可能出现右斜线上有皇后） ｛ if（n == 5) //棋盘满时输出方案 { count++; System。out。println("第" + count + ”种解:”）; for(int j=0；j〈=5;j++）{ System.out.print（x［j］+1+" ”）； ｝System.out.println(""）; //print(); ｝ else //一个棋盘未放满时继续放置 setposition（n + 1）; ｝ } } 三、例子说明 经上机操作,各个经典问题的算法实现实现如下： 1、MaxMin问题 比较10个数字的大小，10, 23， 45, 11, 757， 2, 1236， 768, 1,—9 比较得出最大值为1236,最小值为-9。 2、矩阵连乘 给定6个矩阵A（30*35），B(35＊15），C(15*5），D（5*10），E(10*20）G（20＊25）。 3、背包问题 给定3个背包：三个物品的价值分别为60,120，100，三个物品的质量分别是10，30,20，背包容量为50。 得到装入物品的比例分别为1，2/3，1，总重量为50，最大价值为240. 4、最优装载 船的称重量为20,给定10个物品，重量分别是： 1。0f，5。0f，2.0f，2。0f,4。0f，8。0f,3。0f，1。0f,6。0f，2.0f 5、N皇后问题（非递归) 给定4皇后问题，得到4种解。 6、N皇后问题（递归）给定6皇后问题，得到4种解。 四、心得体会 学习了栾老师的算法课,解决很多问题，老师说程序=算法+数据结构，首先老师教的知识对于逻辑思维能力有很大帮助,它可以培养我们思考分析问题能力，所谓算法简单来说，就是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令，，之前学习，学习了算法的时间空间复杂度分析，之后讲的就是分治法，任何一个可用计算机求解的问题所需要的计算时间都与其规模有关。问题的规模越小，越容易直接求解,解题所需要的时间也越少，分治法的设计思想就是将一个难以解决的大问题,分割成为规模小的问题,分别解决。之后有动态规划问题各种问题,算法是一门基础学科应该学好.对于自己在以后的学习会有很大的帮助。 五、算法对应的例子代码 1、求最大值最小值 /＊使用分治法求最大值最小值T(n)=3n/2-2*/ public class MaxMin ｛ static int count=0; public static void main（String args［]) { //实例化对象 MaxMin maxmin = new MaxMin（）; //创建数组 int[] array = new int［] { 10, 23, 45， 11， 757, 2, 1236， 768，1,-9 ｝; //取得最小值 int max = maxmin.getMax(array， 0， array.length—1); int min = maxmin.getMin(array，0，array。length-1)； //输出 System。out。println（"最大值是：”+max)； System.out。println(”最小值是："+min）； ｝ /* 求最大值＊/ public static int getMax(int［] array，int i，int j) { int Max1 = 0; int Max2 = 0； if（i == j） { return Max1 = Max2 = array［j］; ｝else if (i == （j — 1）） { Max1 = array[i］； Max2 = array［j]； return Max1 〉 Max2 ？ Max1 : Max2; ｝ else { int mid = (i + j） / 2; Max1 = getMax（array， i, mid）； Max2 = getMax（array, mid, j)； // count++; //System.out。println（count)； return Max1 > Max2 ? Max1 : Max2； ｝ } /＊求最小值＊/ public static int getMin(int[］array，int i，int j）{ i nt Min1=0； i nt Min2=0； i f（i==j）｛ return Min1=Min2=array［j］； ｝else if（i==(j-1)）｛ Min1=array[i]; Min2=array[j］； return Min1〉Min2？Min2：Min1； ｝else｛ int mid=(i+j)/2; Min1=getMin(array，i，mid)； Min2=getMin（array,mid,j); return Min1〉Min2？Min2：Min1； ｝ ｝ ｝ 2、矩阵连乘问题 /*矩阵连乘问题，i，r,k的三重循环,时间复杂度为O(n立方）*/ public class MatrixChainOrder ｛ int[] p;//矩阵维数 int［］[] m;//最少乘次数 int[][］s;//分割点 int length； public MatrixChainOrder（int［］ p，int[］［] m，int［］［］ s)｛this.p = p; this。length = p。length/2； this.m = m； this。s = s； init()； clac（)； printM（); ｝ public void init(）{ //m初始化 for (int i=0；i m［i］［i] = 0； } ｝ public void clac（）｛ for（int i=1;i〈length;i++)｛ for（int j=0；j〈length-i；j++){ int r = j+i; //重复计算子问题，长度由1，到length int t = Integer.MAX_VALUE；//定义当前最大值 for（int k = j;k int temp = m［j］[k］ + m[k+1］[r] + p[j*2］＊p［k*2+1］＊p[r*2+1］； if (t 〉 temp）{ t = temp; m［j]［r］ = temp; ｝ } ｝ ｝ } public void printM（）｛ for (int i=0；i for（int j=0；j System.out。print（m［i]［j]+ ”\t”)； ｝ System.out。println(); } ｝ public static void main(String args[］）{ int p[］ = {30，35,35,15，15，5,5,10,10,20，20,25}; int length = 6； int［］［] m = new int[6］［6]； int［］[] s = new int[6］[6]； new MatrixChainOrder（p，m,s）； } ｝ 3、背包问题 /* 利用贪心算法，对背包问题的java实现*/ public class Knapsack { private float m；//背包容量 float[] v；//三个物品的价值 float［] w ; //三个物品的质量 float[］x ; //往背包装东西的比例 int n ; //物品个数 double[] p_w_v；//每个物品的单位重量价值 public Knapsack（）{ this.m = 50。0f ; //背包容量为50 this。v = new float［］{60。0f，120.0f,100。0f｝ ; //三个物品的价值分别为60,120,100 this。w = new float［]｛10。0f,30。0f,20。0f，｝ ; //三个物品的质量分别是10，30,20， this.x = new float[3］；//往背包装东西的比例 this.n = 3 ；//三个物品 this.p_w_v = new double［n］；//每个物品的单位重量价值 } //对物品的单位重量价值进行排序 public void sort（int n ，float[］ v ,float［］ w)throws Exception{ for (int i = 0 ； i 〈 n ; i++）{ p_w_v[i］ = v[i] / w［i］ ;//单位重量价值 } print （p_w_v）； System.out.println （"”); Sort（p_w_v，w,v) ; print (p_w_v)； ｝ public void print （double a［］）｛//打印输出数组 int len = a。length; for (int i = 0; i < len； i++）{ System.out。print(a［i] + ” "); } ｝ public void print (String str）｛//打印输出数组 System.out。print（str + ”\n”）； ｝ public void Sort（double［］ a , float[] b ，float［］ c）｛//冒泡排序,实现排序功能 int len = a.length；//获得数组长度 double temp；//临时变量，用于交换值 float w_temp ； float v_temp ; for（int i = 0； i 〈 len-1; i++)｛//通过循环实现主要算法 for（int j = 0； j < len—1-i; j++）{ if（a［j+1] > a［j]){ //如果后一下值比前一个值大，则交换两个值的大小， //以下几行代码是实现数值交换的 temp = a［j+1］；//从大到小排序 w_temp = w［j+1］; v_temp = v[j+1］; a[j+1］ = a［j]； w［j+1] = w［j]; v[j+1] = v[j]; w［j] = w_temp; v［j］ = v_temp; } } } } //贪心算法核心思想 public void knapsack（)throws Exception{ sort （n，v，w) ； int i ; for (i = 0 ； i 〈n ; i++)｛ x［i] = 0 ; } float c = m； for (i = 0 ; i < n； i++)｛ if（w[i] 〉 c）｛ break ; ｝ x［i］ = 1 ； c —= w[i] ； ｝ if（i 〈n)｛ x[i] = c / w［i］ ; } print （"\n物品一可以装入的比例： " + x［0］)； print （”物品二可以装入的比例： " + x［1］）； print (”物品三可以装入的比例：” + x[2])； print （"可以装入的最大价值为: "+ (x［0]*v[0] + x［1]＊v[1] + x[2］＊v［2］）); print （"可以装入的最大重量为"+ （x[0］*w［0] + x［1]＊w[1] + x［2］＊w[2］)); ｝ public static void main （String[] args）throws Exception｛ Knapsack ksp = new Knapsack（）; ksp.knapsack（）; ｝ ｝ 4、装载问题 /*装载问题，贪心法，时间复杂度上界函数为O(n方）*/ public class Loading ｛ private float m;//船的称重量 private float w［］;//物品的质量 int［]x;//物品的选择 int n；//物品个数 public Loading(){ this.m=20。0f；//船的称重量为20 this.n=9;//10个物品 this。w=new float［］{1。0f,5.0f，2。0f，2.0f，4.0f,8.0f，3。0f，1.0f，6.0f,2.0f};//10个物品的重量 this。x=new int［n]; System。out。println（"给定的10个可选货物为：")； for（int i=0;i〈w。length;i++){ System。out。print（w［i］+” "）； ｝ System.out。println（"”); } //对物品按照重量进行排序 public void sort()｛ float temp=0f； for（int i=0;i for（int j=0；j if(w［j]>w[j+1］）{ temp=w［j］; w［j］=w[j+1]; w[j+1］=temp;｝ } ｝ System.out.println（”排序后的数据为:")； for（int i=0；i〈w.length；i++）｛ System。out。print（w［i]+””）; ｝ ｝ public void loading(）{ int i; System.out.println（）； System.out。println("贪心选择为："); for(i=0;i〈n；i++）｛ x[i]=0; } for（i=0；i〈n；i++）｛ if(w[i］>m）{ break； } x［i］=1; m=m-w［i］； if（m<0)｛ break； } System.out。print（w［i］+” ”）; } ｝ public static void main（String［]args){ Loading load=new Loading（)； load.sort()； load。loading（）; } ｝ 5、N皇后问题（非递归) /*回溯法N皇后问题，非递归算法，时间复杂度为O（n！）＊/ public class Queen1 ｛ static int count = 0； static int n = 6; static int x[］ = new int[n+1]; void backtrack(） { int k = 1; while (k 〉 0) { x［k］ += 1; // 第k列皇后向下移一行 while（（x[k] 〈= n) &＆ !(place(k)）） { // 如果当前第k列皇后未出界或者和其他皇后冲突 x［k］ += 1; // 第k列皇后向下移一行继续寻找 ｝ if（x[k］〈= n）｛// 找到一个值并且未出界 if (k == n) { // 已是最后一列说明已找到一个方案 count++； System.out.println("第" + count + "种解："）； for（int i=1；i<=k;i++) ｛//打印寻找策略 System.out.print（x[i]+” ”)； } System。out。println(）; } // print(）；｝ else { // 不是最后一列故寻找下一列 k++; x［k] = 0； ｝ } else // 找到的值已经出界,回退到上一列 k-—; } } // 判断皇后是否冲突 boolean place（int k) ｛ for（int j = 1; j < k; j++) { if(（Math.abs（j —k） == Math。abs（x[j] —x［k])）｜| （x[j］== x[k］）） return false; ｝ return true; } public static void main(String[］ args) { for(int i = 0；i〈n；i++）｛ x［i］ = 0; ｝ Queen1 huanghou = new Queen1（）; huanghou。backtrack（）； } ｝ 6、N皇后问题（递归） /*回溯法N皇后问题，递归算法＊/ public class Queen ｛ private int［］x = new int［6]； private int count = 0； public Queen(） { setposition（0）； ｝ public void setposition（int n) //n表示在第n行，table[n]表示列数 { for(int i = 0; i 〈= 5; i++) //i表示在第i列上放置皇后 { x[n］ = i; if（place(n）==false）//如果没有皇后在同一列或斜线上（因为是按行依次放置故不可能在同一行上，又因为是每一行是从左到右放置故不可能出现右斜线上有皇后) { if（n == 5) //棋盘满时输出方案 { count++; System。out.println(”第" + count + ”种解："）； for(int j=0；j〈=5；j++）｛ 算法分析与设计实验报告 学生姓名：系别：专业与班号：学号： 实验名称: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．代码设计： 实验报告 课程计算机算法设计与分析实验名称合并排序、快速排序学号姓名实验日期： 实验一合并排序、快速排序 一．实验目的 （1）学习合并排序和快速排序算法的思想，掌握原理。 （2）运用合并排序和快速排序算法的思想进行编程实现，以加深理解。二．实验内容 （1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。（2）输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果三．实验代码 (1)合并排序源代码如下： #include （四） 一、实验内容： 二、算法思想与设计描述： 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) 四、实验总结： 分治法分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。 在用分治法求解时，有些子问题被重复计算了许多次，时间复杂性呈指数增长。而动态规划使用最优子结构避免了大量重复计算。 算法设计与分析实验报告（三） 一、实验内容： 设有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）天： 算法设计与分析实验报告棋盘覆盖问题贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告课程名称:算法设计与分析班级:信计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 算法设计与分析实验报告 算法设计与分析实验报告 一、引言 在计算机科学领域，算法设计与分析是非常重要的研究方向。本次实验旨在通过实际案例，探讨算法设计与分析的方法和技巧，并验证其在实际问题中的应用效果。 二、问题描述 本次实验的问题是求解一个整数序列中的最大子序列和。给定一个长度为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. 实验结果 通过对比实验结果，我们发现两种算法得到的最大子序列和是一致的，验证了算法的正确性。同时，我们还对两种算法的运行时间进行了比较。结果显示，暴力法的运行时间明显长于动态规划法，进一步证明了动态规划法的高效性。 五、实验总结 通过本次实验，我们深入了解了算法设计与分析的方法和技巧，并通过实际案例验证了其在解决实际问题中的应用效果。我们发现，合理选择算法设计方法可以提高算法的效率，从而更好地解决实际问题。 然而，本次实验只涉及了一个简单的问题，实际问题往往更加复杂。在实际应用中，我们需要根据具体问题的特点选择合适的算法，并进行优化。同时，算法的正确性和效率也需要通过大规模测试数据进行验证。 综上所述，算法设计与分析是计算机科学领域中至关重要的研究方向。通过不断学习和实践，我们可以不断提高自己的算法设计与分析能力，为解决实际问题提供更好的解决方案。 算法设计与分析实验报告 实验一全排列、快速排序 【实验目的】 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=。 算法实验报告范文 《算法设计与分析》 实验报告 班级姓名学号 年月日 目录 实验一二分查找程序实现…………………………………………………………………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 递归算法 一、实验目的 掌握递归算法的基本思想； 掌握该算法的时间复杂度分析； 二、实验环境 电脑一台，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 自然语言处理算法实验报告 一、引言 自然语言处理（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%以上。 八、结论与展望 算法设计与分析实验报告 实验名称：矩阵乘法(分冶法) 一、问题陈述和分析： 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的阶 昆明理工大学信息工程与自动化学院学生实验报告 （ 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时，就比较分治法和动态规划法。由实验结果可知，动态规划法所用的时间要少。算法分析与设计实验报告一
算法设计与分析---回溯实验报告
算法设计与分析实验
算法与设计实验报告
算法设计与分析实验报告
算法分析与设计实验报告-合并排序、快速排序
算法设计与分析实验报告-砖石矿工问题
算法设计与分析实验报告-网球循环赛
算法设计与分析实验报告棋盘覆盖问题
算法设计与分析 实验报告
算法设计与分析实验报告
算法实验报告范文
算法设计及实验报告
自然语言处理算法实验报告
矩阵乘法(分治法)
算法实验3-最大子段和问题实验报告
相关主题
文本预览