算法分析与设计实验报告(二)-20131344102-蒋刘燃

《算法设计与分析》实验报告目录一、实验内容描述和功能分析.二、算法过程设计.三、程序调试及结果（附截图）.四、源代码（附源代码）.一、实验内容描述和功能分析.1.整数因子分解问题内容描述：大于1 的正整数n可以分解为：n=x1*x2*…*xm。

例如，当n=12 时，共有8 种不同的分解式：12=12；12=6*2；12=4*3；12=3*4；12=3*2*2；12=2*6；12=2*3*2；12=2*2*3。

对于给定的正整数n，编程计算n共有多少种不同的分解式。

功能分析：输入一行对应1 个正整数n (1≤n≤2000000000)，输出对应的n的不同分解式。

例如：输入：12，输出：82.邮局选址问题内容描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。

用x 坐标表示东西向，用y 坐标表示南北向。

各居民点的位置可以由坐标(x,y)表示。

街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。

居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。

编程任务：给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。

功能分析：输入由多组测试数据组成。

每组测试数据输入的第1 行是居民点数n，1≤n≤10000。

接下来n 行是居民点的位置，每行2 个整数x 和y，-10000≤x，y≤10000。

对应每组输入，输出的第1 行中的数是n 个居民点到邮局的距离总和的最小值。

例如：输入：5 输出：101 22 21 33 -23 3二、算法过程设计.1.整数因子分解问题通过函数的定义和相关变量的定义，根据数学上整数因子的分解算法，来对程序进行设计。

2.邮局选址问题通过题目给定的意思，可以知道其数学算法，通过调用库函数来实现程序的设计和结果的实现。

三、程序调试及结果（附截图）.1.整数因子分解问题2.邮局选址问题四、源代码（附源代码）.1.整数因子分解问题#include<stdio.h>#include<math.h>struct DP{ int num;int sum;} d[50000]={0};int max=0;void qsort(int low,int high,struct DP key[]){ int i=low,j=high;struct DP tag=key[i];if(i<j){ do{ while(tag.num<key[j].num && i<j) j--;if(i<j){ key[i]=key[j];i++;while(tag.num>=key[i].num && i<j) i++;if(i<j){ key[j]=key[i];j--;}}}while(i<j);key[i]=tag;qsort(low,j-1,key);qsort(i+1,high,key);}}int dfs(int left){ int i,p;int l,r,m;int count=0;l=0; r=max;while(l<=r){ m=(l+r)>>1;if(d[m].num<left) l=m+1; else r=m-1;}p=l; if(d[p].sum) return d[p].sum;for(i=1;i<=d[i].num;i++){ if(left%d[i].num==0) count+=dfs(left/d[i].num); }d[p].sum=count;return count;}int main(void){ int i,j,tmp;int n;scanf("%d",&n); tmp=sqrt(n);for(i=1;i<=tmp;i++){ if(n%i==0){ d[max].num=i; max++;d[max].num=n/i; max++;}} max--;qsort(0,max,d);d[0].sum=1;printf("%d\n",dfs(n));return 0;}2.邮局选址问题#include<stdio.h>#include<stdlib.h>#include<math.h>int cmp( const void *a , const void *b ) { return *(int *)a - *(int *)b; } int main(){ int i,a[10005],b[10005],n,y,x;int sum;while(scanf("%d",&n)==1){ for(i=0;i<n;i++)scanf("%d%d",&a[i],&b[i]);qsort(b,n,sizeof(b[0]),cmp);qsort(a,n,sizeof(a[0]),cmp);y=b[(n-1)/2];x=a[(n-1)/2];sum=0;for(i=0;i<n;i++){ sum=sum+fabs(b[i]-y);sum=sum+fabs(a[i]-x);}printf("%d\n",sum);}return 0;}。

算法设计与分析实验21. 实验背景算法设计与分析是计算机科学中重要的研究方向，涉及到算法的设计、分析和实现。

本次实验旨在帮助学生进一步理解和掌握常见的算法设计与分析方法，通过实践操作加深对算法原理的理解。

2. 实验目的本次实验的主要目的如下：- 理解动态规划算法设计思想；- 学习并掌握动态规划算法的实现方法； - 熟悉动态规划算法的时间复杂度分析方法。

3. 实验内容本次实验的主要内容是实现一个动态规划算法，并分析它的时间复杂度。

3.1 动态规划算法介绍动态规划算法是一种将问题分解成子问题并逐个求解的方法。

它通过存储子问题的解来避免重复计算，从而提高算法的效率。

动态规划算法通常采用自底向上的方式来求解问题，即先求解小规模的子问题，再逐步扩大规模，直到解决原始问题。

3.2 实现一个动态规划算法在本次实验中，我们将实现一个动态规划算法来解决一个具体的问题。

具体步骤如下： 1. 确定子问题：将原问题分解为子问题； 2. 确定状态转移方程：定义一个状态转移方程，用于表示子问题与原问题之间的关系； 3. 确定边界条件：确定子问题的边界条件，即最简单的情况下的解； 4. 自底向上求解：根据状态转移方程和边界条件，逐步求解子问题，最终得到原问题的解。

3.3 时间复杂度分析完成动态规划算法的实现后，我们需要对算法的时间复杂度进行分析。

时间复杂度是衡量算法性能的重要指标，它反映了算法在处理输入规模增大时所需的时间。

在分析时间复杂度时，我们需要考虑算法的基本操作次数，并且基于不同输入规模的情况，推导出算法的大O表示法。

4. 实验结果完成实验后，我们得到了动态规划算法的实现代码，并对其进行了时间复杂度分析。

下面是实验结果的总结： - 实现了动态规划算法，并成功解决了一个具体的问题； - 分析了实现代码的时间复杂度，并得出了算法的大O表示法。

5. 总结与展望本次实验通过实现动态规划算法，深入了解了动态规划的设计与分析方法。

算法分析与设计实验报告算法分析与设计实验报告一、引言算法是计算机科学的核心，它们是解决问题的有效工具。

算法分析与设计是计算机科学中的重要课题，通过对算法的分析与设计，我们可以优化计算机程序的效率，提高计算机系统的性能。

本实验报告旨在介绍算法分析与设计的基本概念和方法，并通过实验验证这些方法的有效性。

二、算法分析算法分析是评估算法性能的过程。

在实际应用中，我们常常需要比较不同算法的效率和资源消耗，以选择最适合的算法。

常用的算法分析方法包括时间复杂度和空间复杂度。

1. 时间复杂度时间复杂度衡量了算法执行所需的时间。

通常用大O表示法表示时间复杂度，表示算法的最坏情况下的运行时间。

常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)和O(n^2)等。

其中，O(1)表示常数时间复杂度，O(log n)表示对数时间复杂度，O(n)表示线性时间复杂度，O(n log n)表示线性对数时间复杂度，O(n^2)表示平方时间复杂度。

2. 空间复杂度空间复杂度衡量了算法执行所需的存储空间。

通常用大O表示法表示空间复杂度，表示算法所需的额外存储空间。

常见的空间复杂度有O(1)、O(n)和O(n^2)等。

其中，O(1)表示常数空间复杂度，O(n)表示线性空间复杂度，O(n^2)表示平方空间复杂度。

三、算法设计算法设计是构思和实现算法的过程。

好的算法设计能够提高算法的效率和可靠性。

常用的算法设计方法包括贪心算法、动态规划、分治法和回溯法等。

1. 贪心算法贪心算法是一种简单而高效的算法设计方法。

它通过每一步选择局部最优解，最终得到全局最优解。

贪心算法的时间复杂度通常较低，但不能保证得到最优解。

2. 动态规划动态规划是一种将问题分解为子问题并以自底向上的方式求解的算法设计方法。

它通过保存子问题的解，避免重复计算，提高算法的效率。

动态规划适用于具有重叠子问题和最优子结构的问题。

3. 分治法分治法是一种将问题分解为更小规模的子问题并以递归的方式求解的算法设计方法。

实验二：分治法实验一、实验目的（1）掌握设计有效算法的分治策略。

（2）通过快速排序学习分治策略设计技巧二、实验要求（1）熟练掌握分治法的基本思想及其应用实现。

（2）理解所给出的算法，并对其加以改进。

三、分治法的介绍任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。

问题的规模越小，越容易直接求解，解题所需的计算时间也越少。

而当n较大时，问题就不那么容易处理了。

要想直接解决一个规模较大的问题，有时是相当困难的。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

这自然导致递归过程的产生。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法的适用条件：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

03《算法设计与分析》实验报告福建师范大学协和学院本科实验报告课程名称：《算法设计与分析》学院（系）：专业：班级：学号：学生姓名：学号：学生姓名：学号：学生姓名：实验项目实验序号项目序号实验项目名称实验成绩 1 一 2 3 4 二 5 6 三 7 8 四 9 五 10 11 12 六 13 七 14 15 总分快速排序合并排序 * 寻找主元素递归求排列 * 分治找K大元素平面最近点对 * 分治法求棋盘覆盖问题贪婪法求解普通背包问题单源最短路径的dijstra算法多段图最短路径（动态规划） * 最优资源分配（动态规划） * KMP模式串匹配 0/背包问题 * 回溯法求解巡游问题回溯法求解0/1背包问题标题前加*号的实验题目为设计实验《算法设计与分析》实验报告填写要求一、本课程共需完成七次实验，由十五个实验项目组成。

每一次实验需在备选项目中选择一个项目完成并提交一份实验报告，批改后下发的实验报告请保存起来，期末上交。

二、实验报告书写要求：1. 实验目的和要求：明确实验的内容和具体任务；2. 列出源程序，备注说明程序的基本结构，包括程序中各部分的功能。

3. 说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并给出计算过程。

4. 实验结果与分析：给出不少于3组数据测试算法，并将每组测试数据的运行结果列出，并对调试源程序的结果进行分析，杜绝只罗列不分析；5. 讨论、建议、质疑：针对实验中碰到的问题进行组内以及组外讨论，遇到不能解决的问题时向指导老师请教，并将问题的提出以及解决的过程写入实验报告，以作为以后学习的参考。

问题要具体描述，避免抽象地罗列、笼统地讨论； 6. 全部文字叙述内容要求简明扼要，思路清楚； 7. 实验日期、同组员姓名写清楚。

三、要求实验报告字迹工整、文字简练、数据齐全、计算正确，分析充分、具体、定量。

对于抄袭实验报告和编篡原始数据的行为，一经发现，以零分处理，并根据相关条例给予处分。

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

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

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

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

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

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

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

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

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

采用回溯法求解该问题。

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

《算法设计与分析》课程实验报告实验序号：实验项目名称：随机化算法一、实验题目1.N后问题问题描述：在n*n格的棋盘上放置彼此不受攻击的n个皇后，任何两个皇后不放在同一行同一列，同一斜线上，问有多少种放法。

2.主元素问题问题描述：设A是含有n个元素的数组，如果元素x在A中出现的次数大于n/2，则称x是A的主元素。

给出一个算法，判断A中是否存在主元素。

二、实验目的（1）通过N后问题的实现，体会拉斯维加斯随机算法的随机特点：运行次数随机但有界，找到的解一定为正确解。

但某次运行可能找不到解。

（2）通过实现主元素的不同算法，了解蒙特卡罗算法的随机特性：对于偏真的蒙特卡罗算法，找到为真的解一定是正确解；但非真的解以高概率给出解的正确率------即算法找到的非真解以小概率出现错误。

同时体会确定性算法与随机化算法的差异及各自的优缺点。

（3）通过跳跃表的实现，体会算法设计的运用的广泛性，算法设计的思想及技巧不拘泥独立问题的解决，而在任何需要计算机解决的问题中，都能通过算法设计的技巧（无论是确定性还是随机化算法）来灵巧地解决问题。

此实验表明，通过算法设计技巧与数据组织的有机结合，能够设计出高效的数据结构。

三、实验要求（1）N后问题分别以纯拉斯维加斯算法及拉斯维加斯算法+回溯法混合实现。

要求对同一组测试数据，完成如下任务a.输出纯拉斯维加斯算法找到解的运行次数及运行时间。

b.输出混合算法的stopVegas值及运行时间c.比较a、b的结果并分析N后问题的适用情况。

（2）主元素问题，要求对同一组测试数据，完成如下任务：a.若元素可以比较大小，请实现O(n )的确定性算法，并输出其运行时间。

b.(选做题）若元素不可以比较大小，只能比较相同否，请实现O（n) 确性算法，并输出其运行时间。

c.实现蒙特卡罗算法，并输出其运行次数及时间。

d.比较确定性算法与蒙特卡罗算法的性能，分析每种方法的优缺点。

（3）参照教材实现跳跃表（有序）及基本操作：插入一个结点，删除一个结点。

算法分析与设计实验报告实验一分治策略排序一、实验目的1）以排序问题为例，掌握分治法的基本设计策略；2）熟练掌握合并排序算法的实现；3）熟练掌握快速排序算法的实现；4) 理解常见的算法经验分析方法。

二、算法思路1. 合并排序算法思想：分而治之(divide - conquer);每个递归过程涉及三个步骤第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作第三, 合并: 合并两个排好序的子序列,生成排序结果.最坏时间复杂度最好时间复杂度空间复杂度2.快速排序算法思想：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。

一躺快速排序的算法是：1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；5）、重复第3、4步，直到I=J；三、实验内容：1. 准备实验数据要求：编写一个函数data-generate，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。

这些数作为本算法实验的输入数据。

2. 实现合并排序算法要求：实现mergesort算法。

输入：待排数据文件data.txt；输出：有序数据文件resultsMS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeMS。

14210501022017 3 281234121010 3201741112//枢轴元素t为数组最左侧的元素//i往右移动j往左移动当指向同一位置时扫描完成//如果右侧指针元素比轴测元素大，指针元素左移//确保i在j左边//当右侧指针元素比轴测元素小时，交换两指针指向数的位置//如果左侧指针元素比轴测元素小，指针元素右移//确保i在j左边//当左侧指针元素比轴测元素大时，交换两指针指向数的位置//对左边进行排序//对右边进行排序实用文案printf("\n");system("pause");getchar();}运行结果经验归纳结合以前学的数据结构及应用算法，较容易理解。

题目二：对用户输入的杂乱无序的数字序列按照由小到大的顺序排序：合并排序题目分析合并排序的基本思想是：将待排序的元素分成大小大相同的两个子集合，分别对两个子集合进行排序，最终将排序好的子集合合并成所要求的拍好序的集合。

算法构造核心代码来自书上：MergePass(Type x[],Type y[],int s,int n)//合并大小为s的相邻序列子数组Merge(Type c[],Type d[],int l,int m,int r) //合并c[l,m]和x[m+1,r]到y[l,r]算法实现//将a中的元素合并到数组b//将b中的元素合并到数组a//合并c[l,m]和x[m+1,r]到y[l,r]//合并大小为s的相邻序列子数组//合并大小为s的相邻2字段数组//合并x[i,i+s-1]和x[i+s,i+2*s-1]到y[i,i+2*s-1] //处理剩下的元素少于2sfor(int j=i;j<=n-1;j++)y[j]=x[j];}void main(){int a[100],i,n;printf("请输入要进行合并排序的数字的个数:\n");scanf_s("%d",&n);for( i=0;i<n;i++){printf("请输入要进行合并排序的第%d个数字:\n",i+1);scanf_s("%d",&a[i]);}MergeSort(a,n);printf("合并排序的结果:\n");for(i=0;i<n;i++)printf("%d,",a[i]);printf("\n");system("pause");}运行结果经验归纳结合以前学的数据结构及应用算法，用心理解还能明白。

《算法设计与分析》实验指导实验二动态规划应用日期：一、实验目的1．理解动态规划的基本思想,了解最优子结构性质和子问题的重叠性质。

2．熟练掌握典型的动态规划问题。

掌握动态规划思想分析问题的一般方法,对较简单的问题能正确分析,并设计出动态规划算法,并能够用程序实现。

二、实验要求1. 认真学习动态规划方法基本思想、方法步骤,练习利用动态规划法分析问题解决问题,加深动态规划类程序的理解。

2. 阅读经典问题的关键代码段,仔细领会动态规划算法的精要。

3.选定实验题目，仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。

4. 实验要有详细的测试记录，包括各种可能的测试数据。

三、实验内容1.调试验证选择经典问题TSP问题、最长公共子序列、0/1背包问题之一,完善算法,用C/C++以及Javascript语言编写程序并调试。

2.巩固提高针对其中经典问题之一，通过检索论文资料，类比研究等方法对其算法进行优化，并通过实验得方式对其进行验证比较,上机调试，最终形成一篇不少于2000字得小论文。

实验报告一、实验目的掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法。

二、实验内容现有n种物品，对1<=i<=n，第i种物品的重量为正整数W，价值为正整数V，背包能承受的最大载重量为正整数C，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过C且总价值最大。

三、实验环境操作系统、调试软件名称、版本号，上机地点，机器台号四、问题分析令V（i,j）表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划；（1）V（i,0）=V(0,j)=0（2）V(i,j)=V(i-1,j) j<Wi V(i,j)=max{V(i-1,j),V(i-1,j-Wi)+Vi} j>Wi(1)式表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1的物品得到的最大价值是相同的，即物品i不能装入背包；第（2）个式子表明：如果第i个物品的重量小于背包的容量则会有以下两种情况：（a）如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi（b）如果第i个物品没有入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。