算法与分析。
课程设计报告。
题目： 算法设计和分析
专业： 网络工程
班级： 1020552
学号： 11
姓名： 赫前进
太原工业学院计算机工程系。
2023年 11月 24 日。
第二章主元素问题。
一、 算法问题描述。
主元素问题：设t[0..n-1]是n个元素的数组。
对任一元素x，设s(x)=。当|s(x)|>n/2时，称x为t的主元素。如果t中元素存在序关系，按分治策略设计并实现一个线性时间算法，确定t[0..
n-1]是否有一个主元素。
二、 算法问题形式化表示。
若t 中存在主元素，则将t 分为两部分后，t 的主元素也必为两部分中至少一部分的主元素，因此可用分治法。将元素划分为两部分，递归地检查两部分有无主元素。算法如下：
若t 只含一个元素，则此元素就是主元素，返回此数。
将t 分为两部分t1 和t2（二者元素个数相等或只差一个），分别递归调用此方法求其主元素m1 和m2。
若m1 和m2 都存在且相等，则这个数就是t 的主元素，返回此数。
若m1 和m2 都存在且不等，则分别检查这两个数是否为t 的主元素，若有则返回此数，若无则返回空值。
若m1 和m2 只有一个存在，则检查这个数是否为t 的主元素，若是则返回此数，若否就返回空值。
若m1 和m2 都不存在，则t 无主元素，返回空值。
三、 期望输入与输出。
输入：数组中元素的个数9
数组元素0 0 1 1 0 8 1 1 1
输出：显示主元素是1。
四、 算法分析与步骤描述。
选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为k。
如果k>n/2，那么继续用同样的方法在左边部分找；如果k五、 问题实例及算法运算步骤。
首先运行程序，按照提示输入数据；其次求出在数组t[0:n]**现次数最多的元素x出现的次数k；然后用select方法线性时间选择，找到第（n+1）/2大的数；用quicksort进行快速排序；用partition方法进行数组划分，用swap将小于x的元素移到x左边，大于x的元素移到x右边；然后就可以得到时候存在主元素，输出到屏幕上。从屏幕得到数组0 0 1 1 0 8 1 1 1后，可以得到出现次数最多的元素为1，其次数为5，第（n+1）/2大的数字为0,可以判断存在主元素，然后进行快排，移动元素得到数组为0 0 0 1 1 1 1 1 8，此时就可以得到主元素为1。
六、 算法运行截图。
七、 算法复杂度分析。
根据快速排序的思想，可以在平均时间复杂度为o(n)的时间内找出一个数列的中位数。然后再用o(n)的时间检查它是否是主元素， 时间复杂度分析master()中求中位数可以在平均时间复杂度为o(n)的时间内完成，检查中位数是否是主元素耗时o(n),所以时间复杂度为o(n)。
第三章字符串问题。
一、 算法问题描述。
设a和b是两个字符串，要用最少的字符操作将字符串a转换为字符串b
字符串操作包括，1）删除一个字符。
2）插入一个字符。
3）将一个字符改为另一个字符。
将字符串a变换成字符串b所用的最少字符操作数称为字符串a到b的编辑距离，记为d（a，b）。试着设计一个有效算法，对任意给出的俩个字符串a和b，计算出他们的编辑距离d(a,b)。
二、 算法问题形式化表示。
定义一个二维数组d[存储中间结果，如下图所示，为已经初始化后的情况。然后从d[1,1]开始从左到右，从上到下依次按填表，表的最后一个元素d[m,n]就是要求的最终结果。
三、 期望输入与输出。
输入：由文件 提供输入数据，文件的第一行是字符串a，文件的第二行是文件b。
输出：程序运结束时，将编辑距离d（a，b），输出到文件的第一行中。
四、 算法分析与步骤描述。
注意：报告中不附加程序**，主要程序要描述程序流程。
设所给的两个字符串为a[1:m]和b[1:n]。定义d[i][j]=d(a[1:i],b[1,j])。单字符a,b间的距离定义为：
d(a,b)=0 (a=b)
d(a,b)=1(a!=b)
考察从字符串a[1:i]到字符串b[1:j]的变换。可分成以下几种情况：
1）字符a[i]改为字符b[j]；需要d(a[i],b[j])次操作。
2）删除字符a[i]；需要1次操作。
3）插入字符b[j]；需要1次操作。
因此，d[i][j]可递归地计算如下。
d[i][j]=min。
五、 问题实例及算法运算步骤。
例子：下面实际解决一下从srcstr = bd" 到 dststr = abcd"的过程，上面这三种情况分别是初始化的时候要做的，首先用一维数组表示两位数组，纵向 i = 0 ->m+1 ， d[i * n + 1)] i
横向 i = 0 ->n+1, d[i] =i,即：如下图是初始化之后的**信息，纵向是b,d 横向是a,b,c,d
步骤：for(i = 1 ->2) /2为“bd"的长度。
for( j = 1 ->4 ) 4 为”abcd"的长度。
为了确定d[ i ][j ]的大小， 需要比较。
a)从d[ i - 1 ][j - 1] 修改字符srcstr[i - 1], 使之变为dststr[j - 1], 如果srcstr[i - 1] =dststr[j - 1] 则这一步可以免去。
b)从d[ i - 1 ][j ]在srcstr的[ i - 1]处添加一个字符，使字符srcstr[ i - 1 ]变为dststr[ j - 1 ]
c)从d[ i ][j - 1 ] 在dststr的[ j - 1 ]处删除一个字符，使字符dststr[ j - 1 ]变为srcstr[ i - 1],三者之间的最小值赋给d[ i ][j ]
六、 算法运行截图。
七、 算法复杂度分析。
从上面算法可以看出，该算法时间复杂性为0(m*n),空间复杂性为o（m*n）。同时可以看出，当对第i行进行填表时，只需要用到第i-1行的数据，因此可以用一个一维数组dis[0…n]代替二维数组d[0…m,0…n]，因此空间复杂性降为o(n)。
第四章磁带存储问题。
一、 算法问题描述。
设有n个程序要存放在长度为l的磁带上。程序i 存放在磁带上的长度是li ，1<=i<= n。这n个程序的读取概率分别为p1，p2，……pn，且σpi=1(i=1,2,….
n)。如果将这n个程序按i1，i2，……in的次序存放，则读取程序所需的时间tr=cσpik lik(k=1,2,….r)（可假定c为1）。
这n 个程序的平均读取时间为t(1)+t(2)+.t(r)。磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序，使平均读取时间达到最小。
二、 算法问题形式化表示。
对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数和占用磁带的长度。
三、 期望输入与输出。
输入：给出输入数据。第1行是正整数n，表示文件个数。
接下来的n行中，每行有2个正整数a和b,分别表示程序存放在磁带上的长度和读取概率。实际上第k个程序的读取概率为ak/σai。对所有输入的均假定c = 1。
输出：将编程计算出的最小平均读取时间输出到文件。
输入文件示例输出文件示例。
四、 算法分析与步骤描述。
因为长度和检索该程序的时间成正比，输入程序后，先按程序长度由小到大排序，即程序短的放在前面，则由题意的检索方法可知该方法检索时间最短。
1.输入n和l[1],l[2],.l[n];
2.将l数组从小到大排序；
3.计算出个个程序的从头查到的检索时间t[i]；
4.计算出最有存储的平均检索时间st。
五、 问题实例及算法运算步骤。
最多数量是最优先解决的问题，然后再数量最大的前提下让利用率站到最大，所以按照贪心策略先将占用的长度从小到大进行排序，以此输入到磁带中， ２
排序之后3,7,7,8,9,12,最佳组合应为 ３ 先按照数量最多的前提下可存放3个程序3 7 7,然后进行第2策略让利用率最大，3+7+7 = 17 24-17 = 7表明还剩下7个空间，从3，7，7最后一个数开始使其尽可能的大3，7，12 = 22，此时磁带还剩下空间2，再从倒数第二个数开始使其尽可能的大，但是最大上限不能超过12,3，8，12 = 23磁带还剩下1空间，然后在分析比8大的数9则3+9+12 是24,再从倒数第三个数开始重复上述操作，但是比3大一位是7，如果采用7，9，12已经超过磁带最大上限所以停止查找，既此时最大个数3最大利用率24。
六、 算法运行截图。
七、 算法复杂度分析。
时间复杂度为o(n)
第五章电路板问题。
一、 算法问题描述。
最小长度电路板排列问题是大规模电子系统设计中提出的实际问题。该问题的提法是，将n块电路板以最佳排列方案插入带有n个插槽的机箱中。n块电路板的不同的排列方式对应于不同的电路板插入方案。
设b=是n块电路板的集合。集合l=是n块电路板的m个连接块。其中每个连接块n i 是b的一个子集，且n i 中的电路板用同一根导线连接在一起。
二、 算法问题形式化表示。
在最小长度电路板排列问题中，连接块的长度是指该连接块中第1 块电路板到最后1块电路板之间的距离。例如在图示的电路板排列中，连接块n 4 的第1 块电路板在插槽3 中，它的最后1块电路板在插槽6中，因此n 4 的长度为3。同理n 2 的长度为2。
图中连接块最大长度为3。试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。对于给定的电路板连接块，设计一个队列式分支限界法，找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。
算法设计与分析课程设计报告
湖南理工学院课程 题目 0 1背包问题的设计与实现。课程名称数据结构与算法设计。姓名学号。专业班级年级 2014级。学院计算机学院日期 2015年6月25日。课程 评价标准。目录。1.问题描述3 2.算法设计分析3 3.程序编码与调试分析5 4.测试结果7 5.自学知识7 6.课程设计心得体会8 7...
算法设计与分析课程设计报告
湖南理工学院课程 题目 0 1背包问题的设计与实现。课程名称数据结构与算法设计。姓名学号 专业班级年级 2014级 学院计算机学院日期 2015年6月25日 课程 评价标准。目录。1.问题描述3 2.算法设计分析3 3.程序编码与调试分析5 4.测试结果7 5.自学知识7 6.课程设计心得体会8 7...
算法分析与设计课程设计报告
算法分析与设计。课程设计报告 课程名称算法分析与设计。实验学期 2013 年至 2014 年第 1 学期。所在学院理学院年级 2011 专业班级信息与计算科学3班 学生姓名郑松辉学号 201130760334 自评成绩 96 教师评成绩 指导教师赵峰 算法分析与设计 课程设计报告。目录。1课程实验概...