算法设计与分析报告 正文

算法分析与设计上级实现题报告TSP问题一、问题描述所谓TSP问题是指旅行商要去n个城市推销商品，其中每个城市到达且仅到达一次，并且要求所走的路程最短（该问题又称货郎担问题、邮递员问题、售货员问题等）。

TSP问题最容易想到、也肯定能得到最优解的算法是穷举法，即考察所有可能的行走线路，从中选出最佳的一条。

二、解题思路1.基木思路对于图G=(V,E),从起点出发，其余点作为路径集合，然后列出路径集合中各个点作为子路径起点，其余点作为路径集合的情况，从中选取路径长度最短的情况，再对路径集合迭代计算，直到路径集合为空的时候，这时最短路径的情况即是该点到原点的距离，路径集合是空集{},此时己触碰临界条件，可以不断回溯之前的迭代，进而解决此问题。

2.最优值函数和边界条件rd(k,o)= ckild(i,W) = minfCjk + d(k V - {k}) } (k G V z) 第二行是最优值函数。

从i到集合v的最优路径是以v'中某一点作为子路径起点，其余点作为路径集合的路径的长度加上从k至ij i 的距离的最优值。

第一行是边界条件。

当子路径的路径集合是空集时，最优子问题的解，木题来说也就是子路径的最短路径就是从子路径的起点到原来起点的距离。

3.标记函数标记函数同时也是算法的核心函数，完全按照递推公式的思想，使用迭代的方式。

distance是第一个核心函数，主要负责路径的输岀; distance 1是第二个核心函数，主要负责寻求子集合的最短路径并计算长度。

第一核心函数中调用了第二核心函数，第一核心函数只负路径的输出，在将问题细化深入的过程中，将真正的路径寻找和计算交给第二核心函数。

4.标记函数的解读：(l)distancedouble distance(int a^int b[]^int double d[][NUM]^int start) a:子问题起点b[]:字问题路径集合d[][]:距离矩阵(最开始创建的，所有调用函数过程中，都使用的这个，没有更改，只有读取)start:原问题起点(达到临界条件时，找到路径长度)〃边界条件if(c==0){cout<<start;return d[a][start];}〃非临界条件时候，构建所有路径集合的，起点和对应的路径集合，在迭代的时候会使用到else{for(i=0;i<c;i++){point[i]=b[i];k=0;for(j=0;j<c;j++){e[i][k]=b[j]; /*节点方阵，冗余的*/k++;}}}mindistance=distancel(point[k]^efkj^c-l^d^start)+d[a][point[k] ]；〃假定下一层的最短路径就是p[0]以及其对应的路径矩阵e[k] for(i=0;i<c-l;i++) //比较出下一层真正的最短路径if (mindis tan ce>(dis tan cel(po int[ i+1] star t)+d[ a][point[i+l]])){k=i+l;mindistance=distancel(point[灯，e[k],c-l’d，start)+d[a][poin t[k]];}cout<<point[k]<<,l->";return distance(point[k]，e[k],c-l’d,start)+d[a][point[k]];}(2)distanceldouble distancel(int a，int b[],int c^double d[][NUMj^int start) 〃边界条件if(c==0){return d[a][start];}〃非边界条件else{for(i=0;i<c;i++){point[i]=b[i];k=0;for(j=0;j<c;j++){e[i][k]=b[j];k++;}}}//拆分该点到达起点所需经过的集合该点的下一点到达起点所需经过的集合mindistance=distancel(point [0]，e[0] start)+d[a] [point [ 0]]；for(i=0;i<c-l;i++)if (mindis tan ce>(dis tancel (point [i+1] ,e[i+：L]’c-：La star t) +d[ a][point[i+l]]))mindistance=distancel(point[i+l]，e[i+l],c-：Lsd，start)+d[a][ point]i+1]]；return mindistanee; 〃求最小值}}5.时间复杂度分析整体的时间复杂度是O (2M)。

实验报告题目实验一递归与分治策略一、实验目的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 intint 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．提高学生综合应用所学知识解决实际问题的能力。

算法设计与分析实验报告一实验名称统计数字问题评分实验日期2014 年11 月15 日指导教师姓名专业班级学号一.实验要求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<iostream.h>int s[10]; //记录0~9出现的次数int a[10]; //a[i]记录n位数的规律void sum(int n,int l,int m){ if(m==1){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<t;i++)m=m*10;a[t]=t*m;}int zero=1;for(int i=0;i<l;i++){ zero*= 10;} //求出输入数为10的n次方int yushu=n%zero; //求出最高位以后的数int zuigao=n/zero; //求出最高位zuigaofor(i=0;i<zuigao;i++){ s[i]+=zero;} //求出0~zuigao-1位的数的出现次数for(i=0;i<10;i++){ s[i]+=zuigao*a[l];} //求出与余数位数相同的0~zuigao-1位中0~9出现的次数//如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数if(yushu==0) //补上所缺的0数,并且最高位加1{ s[zuigao]++;s[0]+=l; }else{ i=0;while((zero/=10)>yushu){ i++; }s[0]+=i*(yushu+1);//补回因作模操作丢失的0s[zuigao]+=(yushu+1);//补回最高位丢失的数目sum(yushu,l-i-1,m+1);//处理余位数}}void main(){ int i,m,n,N,l;cout<<"输入数字要查询的数字:";cin>>N;cout<<'\n';n = N;for(i=0;n>=10;i++){ n/=10; } //求出N的位数n-1l=i;sum(N,l,1);for(i=0; i<10;i++){ cout<< "数字"<<i<<"出现了:"<<s[i]<<"次"<<'\n'; }}五.程序调试中的问题调试过程，页码出现报错。

实验一全排列、快速排序【实验目的】1.掌握全排列的递归算法。

2.了解快速排序的分治算法思想。

【实验原理】一、全排列全排列的生成算法就是对于给定的字符集, 用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。

任何n个字符集的排列都可以与1～n的n个数字的排列一一对应, 因此在此就以n个数字的排列为例说明排列的生成法。

n个字符的全体排列之间存在一个确定的线性顺序关系。

所有的排列中除最后一个排列外, 都有一个后继；除第一个排列外, 都有一个前驱。

每个排列的后继都可以从它的前驱经过最少的变化而得到, 全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。

二、快速排序快速排序（Quicksort）是对冒泡排序的一种改进。

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

【实验内容】１.全排列递归算法的实现。

２.快速排序分治算法的实现。

【实验结果】１.全排列：快速排序:实验二最长公共子序列、活动安排问题【实验目的】了解动态规划算法设计思想, 运用动态规划算法实现最长公共子序列问题。

了解贪心算法思想, 运用贪心算法设计思想实现活动安排问题。

【实验原理】一、动态规划法解最长公共子序列设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>, 则:..i.若xm=yn, 则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列...ii.若xm≠yn且zk≠x., 则Z是Xm-1和Y的最长公共子序列...iii.若xm≠yn且zk≠y.，则Z是X和Yn-1的最长公共子序列.其中Xm-1=<x1, x2, …, xm-1>, Yn-1=<y1, y2, …, yn-1>, Zk-1=<z1, z2, …, zk-1>。

算法分析及设计范文
随着信息技术的飞速发展，信息系统的规模也在不断增加，复杂度
也在不断增加，对信息系统的算法设计有着极大的重要性。

算法分析与设
计横跨于计算机科学和数学等各个领域，是其中一个关键问题，值得研究
分析。

算法分析与设计是指用数学和逻辑等手段，研究问题的计算解决方案，通过研究问题的有效性、完整性、正确性和可行性来设计、证明和实现其
中一计算有效解决方案的一种技术。

其包括分析问题的特点，描述问题的
概要，确定问题的输入和输出，把抽象问题转换成可执行程序的运算过程，确定算法的时空复杂度，确定算法的正确性和可行性，以及评价算法的性
能等多方面工作。

算法分析与设计是以计算机软件的功能需求为基础，结合算法学、数
据结构和程序设计语言来分析和设计一种应对其中一种普遍存在的问题的
算法原则，然后用程序语言作出算法的具体实现。

实验一排序算法设计一、实验内容冒泡排序二、实验问题分析该问题主要涉及到了指针和循环和相互比较的方法，是综合知识的应用。

三、数学模型根据题目要求，依次对每个数据进行比较，直至得出最后结果。

如果a>b则交换位置，如果a<b则不交换。

四、程序流程图五、源代码#include <stdio.h>void sort(int a[]){int temp;for(int i=0;i<9;i++){for(int j=0;j<10-i-1;j++){if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}printf("排序后的数据\n"); for(i=0;i<10;i++){if(i==5){printf("\n");}printf("%d ",a[i]);}printf("\n");}void main(){int a[10];for(int i=0;i<10;i++){scanf("%d",&a[i]);}printf("排序前的数据\n"); for(i=0;i<10;i++){if(i==5){printf("\n");}printf("%d ",a[i]);}printf("\n");sort(a);}六、测试结果实验二递归算法设计一、实验内容1.判断S字符是否为“回文”的递归函数，并编写程序测试。

二、实验问题分析递归是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。

递归算法设计，就是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题，在逐步求解小问题后，再返回（回溯）得到大问题的解。

算法设计与分析实验报告算法设计与分析实验报告引言：算法设计与分析是计算机科学中的重要课程，它旨在培养学生解决实际问题的能力。

本次实验旨在通过设计和分析不同类型的算法，加深对算法的理解，并探索其在实际应用中的效果。

一、实验背景算法是解决问题的步骤和方法的描述，是计算机程序的核心。

在本次实验中，我们将重点研究几种经典的算法，包括贪心算法、动态规划算法和分治算法。

通过对这些算法的设计和分析，我们可以更好地理解它们的原理和应用场景。

二、贪心算法贪心算法是一种基于局部最优选择的算法，它每一步都选择当前状态下的最优解，最终得到全局最优解。

在实验中，我们以背包问题为例，通过贪心算法求解背包能够装下的最大价值物品。

我们首先将物品按照单位重量的价值从大到小排序，然后依次将能够装入背包的物品放入，直到背包无法再装下物品为止。

三、动态规划算法动态规划算法是一种通过将问题分解为子问题，并记录子问题的解来求解整体问题的算法。

在实验中，我们以斐波那契数列为例，通过动态规划算法计算斐波那契数列的第n项。

我们定义一个数组来保存已经计算过的斐波那契数列的值，然后通过递推公式将前两项的值相加得到后一项的值，最终得到第n项的值。

四、分治算法分治算法是一种将问题分解为更小的子问题，并通过递归求解子问题的算法。

在实验中，我们以归并排序为例，通过分治算法对一个无序数组进行排序。

我们首先将数组分成两个子数组，然后对子数组进行递归排序，最后将两个有序的子数组合并成一个有序的数组。

五、实验结果与分析通过对以上三种算法的设计和分析，我们得到了以下实验结果。

在贪心算法中，我们发现该算法能够在有限的时间内得到一个近似最优解，但并不能保证一定得到全局最优解。

在动态规划算法中，我们发现该算法能够通过记忆化搜索的方式得到准确的结果，但在问题规模较大时，其时间复杂度较高。

在分治算法中，我们发现该算法能够将问题分解为更小的子问题，并通过递归求解子问题，最终得到整体问题的解。

算法设计与分析报告在当今数字化的时代，算法无处不在，从我们日常使用的智能手机应用到复杂的科学研究和金融交易系统，都离不开算法的支持。

算法设计与分析作为计算机科学的核心领域之一，对于提高计算效率、优化资源利用以及解决实际问题具有至关重要的意义。

算法，简单来说，就是为解决特定问题而制定的一系列清晰、准确的步骤。

一个好的算法不仅要能够正确地解决问题，还需要在时间和空间复杂度上尽可能地高效。

这就要求我们在设计算法时，充分考虑问题的特点和约束条件，选择最合适的算法策略。

在算法设计的过程中，首先要对问题进行深入的理解和分析。

明确问题的输入和输出，以及所期望达到的目标。

例如，在排序问题中，我们需要将一组无序的数据按照一定的顺序排列。

常见的排序算法有冒泡排序、插入排序、选择排序、快速排序等。

对于较小规模的数据，冒泡排序和插入排序可能是简单而有效的选择；而对于大规模的数据，快速排序通常能够提供更好的性能。

接下来，我们要根据问题的特点和要求选择合适的算法策略。

算法策略可以大致分为贪心算法、分治算法、动态规划、回溯算法等。

贪心算法通过在每一步都做出当前看起来最优的选择来逐步逼近最终的解，但并不一定能得到全局最优解。

分治算法则是将一个大问题分解为若干个规模较小且相互独立的子问题，分别求解这些子问题，然后将子问题的解合并得到原问题的解。

动态规划通过保存已解决子问题的结果，避免重复计算，从而有效地解决具有重叠子问题的优化问题。

回溯算法则是一种通过尝试逐步构建解，如果发现当前构建的解不满足条件就回溯并重新尝试的方法。

以背包问题为例，如果我们要在有限的背包容量内选择一些物品，使得物品的总价值最大，就可以使用贪心算法或者动态规划来解决。

贪心算法可能会在某些情况下得到次优解，而动态规划则可以保证得到最优解，但在实现上相对复杂一些。

在算法的实现过程中，数据结构的选择也非常重要。

数据结构是组织和存储数据的方式，不同的数据结构适用于不同的算法和操作。

《算法设计与分析》实验报告
学号：姓名：
实验一分治法求解众数问题
一、实验目的
1.掌握分治法的设计思想并能熟练应用；
2.理解分治与递归的关系。

二、实验题目
在一个序列中出现次数最多的元素称为众数，根据分治法的思想设计算法寻找众数。

三、实验程序
四、程序运行结果
实验二动态规划法求解单源最短路径问题
一、实验目的
1.深刻掌握动态规划法的设计思想；
2.熟练应用以上算法思想求解相关问题。

二、实验题目
设有一个带权有向连通图，可以把顶点集划分成多个互不相交的子集，使得任一条边的两个顶点分属不同子集，称该图为多段图。

采用动态规划法求解多段图从源点到终点的最小代价路径。

三、实验程序
四、程序运行结果
实验三贪心法求解单源点最短路径问题
一、实验目的
1.掌握贪心法的设计思想；
2.分析比较同一个问题采用不同算法设计思想求解的结果。

二、实验题目
设有一个带权有向连通图，可以把顶点集划分成多个互不相交的子集，使得任一条边的两个顶点分属不同子集，称该图为多段图。

采用贪心法求解多段图从源点到终点的最小代价路径。

三、实验程序
四、程序运行结果
实验四回溯法求解0/1背包问题
一、实验目的
1.掌握回溯法的设计思想；
2.掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；
二、实验题目
给定n种物品和一个容量为C的背包，选择若干种物品（物品不可分割），使得装入背包中物品的总价值最大。

采用回溯法求解该问题。

三、实验程序
四、程序运行结果。

算法设计与分析报告学生姓名学号专业班级指导教师完成时间目录一、课程内容 (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<k≤n, 而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。

那末，这类问题可以用分治法求解。

分治法的核心技术1)子问题的划分技术.2）递归技术。

反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。

3)合并技术.（2）MaxMin算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。