下载文档原格式
算法分析与设计实验报告学号姓名班级上课地点教师上课时间实验一算法分析基础1. 实验目的1.1．熟悉Eclipse中编辑、编译和运行JA V A程序的方法；1.2．了解算法的定义与特点；1.3．学会分析算法的时间复杂度和空间复杂度。
2. 实验环境2.1 Eclipse2.2 Window XP3. 实验内容3.1 排序问题：实现冒泡排序、插入排序算法，并分析它们的算法复杂度。
3.2 合并问题：合并两个已排序的表，并分析算法复杂度。
（首先判断两个表是否已排序）4. 教师批改意见成绩签字：日期：实验报告细表1插入排序1.1 算法设计思想快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法流程图为：1.2 程序源码插入排序代码：package实验1;import java.util.Scanner;public class InsertionSort {public static void main(String anr[]){i nt[] a=new int[7];a[6]=99999999;Scanner s = new Scanner(System.in);for(int i=1;i<6;i++){System.out.println("请输入第"+i+"个数字");a[i]=s.nextInt();}for(int i=1;i<6;i++){if(a[i+1]<a[i]){a[0]=a[i+1];for(int j=i+1;j>0;j--){a[j]=a[i];i--;}}}System.out.println("插入排序后的顺序为：");for(int i=1;i<6;i++)System.out.println(a[i]);}}1.3 实验结论第一组数据：当输入数据为5,9,7,11,6时，结果如下：第二组数据：当输入数据为6,9,1,11,10时，结果如下：第三组数据：当输入数据为55,16,25,48,10时，结果如下：1.4 心得体会快速排序的运行时间与划分是否对称有关，算法的实现和理解与代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。
算法实验报告快速排序1. 问题描述：实现对数组的普通快速排序与随机快速排序(1)实现上述两个算法(2)统计算法的运行时间(3)分析性能差异，作出总结2. 算法原理：2.1快速排序快速排序是对冒泡排序的一种改进。
它的基本思想是：选取一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准元素小，另外一部分的所有数据都要比基准元素大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
设要排序的数组是A[0]……A[N-1]，首先选取一个数据（普通快速排序选择的是最后一个元素, 随机快速排序是随机选择一个元素）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
一趟快速排序的算法是：1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]；4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]；5）重复第3、4步，直到i=j；(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。
找到符合条件的值，进行交换的时候i，j指针位置不变。
另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
2.2随机快速排序快速排序的最坏情况基于每次划分对主元的选择。
基本的快速排序选取第一个或者最后一个元素作为主元。
这样在数组已经有序的情况下，每次划分将得到最坏的结果。
一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。
这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。
实习报告一、前言算法是计算机科学的核心，是解决复杂问题、优化问题的重要手段。
作为一名计算机专业的学生，我深知算法在实际应用中的重要性。
因此，在大学期间，我积极参加了多次算法实习，以提高自己的算法能力和实践经验。
本文将对我最近的算法实习经历进行总结和报告。
二、实习内容本次实习主要涉及以下几个方面的内容：1. 算法基础：复习了常见的数据结构（如数组、链表、栈、队列、树等）和基本算法（如排序、查找、递归等）。
2. 算法设计与分析：学习了贪心算法、动态规划、分治算法等常见算法设计方法，并通过实例进行了实践。
3. 算法竞赛：参加了国内外知名的算法竞赛，如LeetCode、Codeforces等，完成了约200道算法题目。
4. 实际项目：参与了一个实际项目的算法设计与实现，涉及大数据处理、分布式计算和机器学习等技术。
三、实习过程1. 学习算法基础：通过阅读教材、在线课程和博客，复习了算法基础知识，并对重点概念和算法进行了总结。
2. 学习算法设计与分析：阅读了相关教材和论文，学习了贪心算法、动态规划、分治算法等设计方法，并通过实例进行了练习。
3. 参加算法竞赛：注册了LeetCode、Codeforces等平台，参加了算法竞赛，逐步提高自己的算法能力。
4. 实际项目：与团队成员一起讨论项目需求，设计算法方案，实现了相关功能模块。
四、实习收获1. 算法能力：通过实习，提高了自己的算法能力，熟练掌握了常见数据结构和基本算法，学会了运用各种算法设计方法解决实际问题。
2. 编程技巧：在实习过程中，提高了自己的编程技巧，熟悉了多种编程语言（如Python、C++、Java等），并掌握了相关开发工具和库。
3. 团队协作：在实际项目中，学会了与团队成员沟通、协作，共同解决问题，提高了自己的团队协作能力。
4. 解决问题能力：在实习过程中，学会了分析问题、拆解问题、解决问题，提高了自己的逻辑思维能力和独立解决问题的能力。
五、总结通过本次算法实习，我对算法有了更深入的了解，提高了自己的算法能力和实践经验。
第8次作业答案16.1-116.1-2543316.3-416.2-5参考答案：16.4-1证明中要三点：1.有穷非空集合2.遗传性3.交换性第10次作业参考答案16.5-1题目表格：解法1：使用引理16.12性质（2），按wi单调递减顺序逐次将任务添加至Nt（A），每次添加一个元素后，进行计算，{计算方法：Nt（A）中有i个任务时计算N0 (A),…,Ni(A)，其中如果存在Nj (A)>j,则表示最近添加地元素是需要放弃地，从集合中删除}；最后将未放弃地元素按di递增排序，放弃地任务放在所有未放弃任务后面，放弃任务集合内部排序可随意.解法2：设所有n个时间空位都是空地.然后按罚款地单调递减顺序对各个子任务逐个作贪心选择.在考虑任务j时，如果有一个恰处于或前于dj地时间空位仍空着，则将任务j赋与最近地这样地空位，并填入; 如果不存在这样地空位，表示放弃.答案（a1，a2是放弃地）：<a5, a4, a6, a3, a7,a1, a2>or <a5, a4, a6, a3, a7,a2, a1>划线部分按上表di递增地顺序排即可，答案不唯一16.5-2（直接给个计算例子说地不清不楚地请扣分）题目：本题地意思是在O(|A|)时间内确定性质2（性质2：对t=0，1，2，…，n，有Nt(A)<=t,Nt(A)表示A中期限不超过t地任务个数）是否成立.解答示例：思想：建立数组a[n],a[i]表示截至时间为i地任务个数，对0=<i<n，如果出现a[0]+a[1]+…+a[i]>i,则说明A不独立，否则A独立.伪代码：int temp=0;for(i=0;i<n;i++) a[i]=0; ******O(n)=O(|A|)for(i=0;i<n;i++) a[di]++; ******O(n)=O(|A|)for(i=0;i<n;i++) ******O(n)=O(|A|) {temp+=a[i];//temp就是a[0]+a[1]+…+a[i]if（temp>i）//Ni(A)>iA不独立；}17.1-1（这题有歧义，不扣分）a) 如果Stack Operations包括Push Pop MultiPush,答案是可以保持,解释和书上地Push Pop MultiPop差不多.b) 如果是Stack Operations包括Push Pop MultiPush MultiPop,答案就是不可以保持,因为MultiPush,MultiPop交替地话,平均就是O(K).17.1-2本题目只要证明可能性，只要说明一种情况下结论成立即可17.2-1第11次作业参考答案17.3-1题目：答案：备注：最后一句话展开：采用新地势函数后对i 个操作地平摊代价：)1()())1(())(()()(1''^'-Φ-Φ+=--Φ--Φ+=Φ-Φ+=-Di Di c k Di k Di c D D c c i i i i i i17.3-2题目：答案：第一步：此题关键是定义势能函数Φ,不管定义成什么首先要满足两个条件 对所有操作i ，)(Di Φ>=0且)(Di Φ>=)(0D Φ比如令k j+=2i ，j,k 均为整数且取尽可能大，设势能函数)(Di Φ=2k;第二步：求平摊代价，公式是)1()(^-Φ-Φ+=Di Di c c i i 按上面设置地势函数示例：当k=0，^i c =…=2当k ！=0,^i c =…=3 显然，平摊代价为O(1)17.3-4题目：答案：结合课本p249，p250页对栈操作地分析很容易有下面结果17.4-3题目：答案：αα=(第i次循环之后地表中地entry 假设第i个操作是TABLE_DELETE, 考虑装载因子:inum size数)/(第i次循环后地表地大小)=/i i第12 次参考答案19.1.1题目：答案：如果x不是根，则degree[sibling[x]]=degree[child[x]]=degree[x]-1如果x是根，则sibling为二项堆中下一个二项树地根，因为二项堆中根链是按根地度数递增排序，因此degree[sibling[x]]>degree[x]19.1.2题目：答案：如果x是p[x]地最左子节点，则p[x]为根地子树由两个相同地二项树合并而成，以x为根地子树就是其中一个二项树，另一个以p[x]为根，所以degree[p[x]]=degree[x]+1;如果x不是p[x]地最左子节点，假设x是p[x]地子节点中自左至右地第i个孩子，则去掉p[x]前i-1个孩子，恰好转换成第一种情况，因而degree[p[x]]=degree[x]+1+（i-1）=degree[x]+i;综上,degree[p[x]]>degree[x]19.2.2题目：题目：19.2.519.2.6第13次作业参考答案20.2-1题目：解答：20.2-3 题目：解答：20.3-1 题目：答案：20.3-2 题目：答案：第14次作业参考答案这一次请大家自己看书处理版权申明本文部分内容，包括文字、图片、以及设计等在网上搜集整理.版权为个人所有This article includes some parts, including text, pictures, and design. Copyright is personal ownership.6ewMy。
实验报告一、实验目的在计算机科学与数学中，排序算法是一种基本并且常用的算法，一个排序演算法是一种能将一串资料依照特定排序方式的一种演算法。
有效的排序演算法在一些演算法中是重要的，如此这些演算法才能得到正确解答。
排序演算法也用在处理文字资料以及产生人类可读的输出结果。
由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。
通过实现相关一些排序算法，加深对于算法知识的理解与学习。
二、实验题目要求实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法，并比较这些算法的性能。
三、实验要求（一）在随机产生的空间大小分别为N = 10，1000，10000，100000 的排序样本（取值为[0,1]）上测试以上算法。
（二）结果输出:1） N=10时，排序结果。
2） N=1000，10000，100000时，对同一个样本实例，不同排序完成所需的时间。
3） N=1000，10000，100000时，每个排序用不同的样本多试验几次（最低5次）得出平均时间，比较不同排序算法所用的平均时间。
四、实验内容各种排序算法相关代码的实现及其原理说明如下：1.合并排序对于合并排序，算法过程说明如下：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。
合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。
合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕，此时将另一非空的子文件中剩余记录依次复制到R1中即可。
2.插入排序关于直接插入排序的算法说明如下：假设待排序的记录存放在数组R[1..n]中。
算法实验报告Ex.1 若将y ← uniform(0, 1) 改为 y ← x, 则上述的算法估计的值是什么？实验结果如下：可见结果趋近于2*sqrt(2) Ex.2 在机器上用2041x dx -⎰估计π值，给出不同的n 值及精度。
计算方法就采用课上讲到的HitorMiss 算法，伪代码如下： f ←sqrt(1 – x*x) HitorMiss (f, n) { k ← 0;for i ← 1 to n do { x ← uniform(0, 1); y ← uniform(0, 1);if y ≤ f(x) then k++;}//endfor return 4*k/n;}实验结果如下：从总的趋势来看，n的值越大，给出的pai的精度越高。
但对应到两次实验结果未必n 大的精度一定高，这是概率算法的特点。
EX.3 采用算法类似HitorMiss算法，不过加入了一些特殊处理，以便能够正确计算穿越x 轴、周期函数等的积分。
算法伪代码如下：f ← x^2 / - sqrt(x) / sin(x)MyCalc(f , minx, maxx, miny, maxy, n){k ← 0;for i ← 1 to n do {x ← uniform(minx, maxx);y ← uniform(miny, maxy);if f(x) >= 0//函数在x轴上方，积分是f与x轴之间的部分，积分值为正then if y <= f(x) && y >=0k++;else//函数在x轴下方，积分是f与x轴之间的部分，积分值为负if y >= f(x) && y <= 0k--;}//endforif miny > 0//函数在x轴上方then return k / n * (maxx - minx) * (maxy - miny) + miny * (maxx - minx));else if maxy < 0//函数在x轴下方then return k / n * (maxx - minx) * (maxy - miny) + maxy * (maxx - minx);else//函数穿越x轴then return k / n * (maxx - minx) * (maxy - miny);}运行结果如下：可见程序运行结果还是很准确的，能正常处理在x轴单侧、穿越x轴的连续函数积分。
快速排序实验报告
SA14225010
一、题目
当输入数据已经“几乎”有序时，插入排序速度很快。
在实际应用中，我们可以利用这一特点来提高快速排序的速度。
当对一个长度小于k的子数组调用快速排序时，让它不做任何排序就返回。
当上层的快速排序调用返回后，对整个数组运行插入排序来完成排序过程。
试证明：这一排序算法的期望时间复杂度为O （nk+nlg（n/k））。
分别从理论和实践的角度说明我们应该如何选择k？
二、算法思想
当输入数据已经“几乎”有序时，插入排序速度很快。
当对一个长度小于k的子数组调用快速排序时，让它不做任何排序就返回。
当上层的快速排序调用返回后，对整个数组运行插入排序来完成排序过程。
累加k的值，计算出当k为不同值时算法运行的时间，来算出当k大约为什么值时运行的时间最短，并与传统的快速排序算法的运行时间进行比较。
三、实验结果
输入100个不同的整数值，选取不同的k的值，观察所用时间
四、实验分析
理论上看，k的值选取为20到25较好；但是，从实际上来看，当k为50左右时间为39毫秒，最少，但不同的时刻运行后的时间都不相同，而且不同的输入时刻的运行时间也不相同，当数据较大时候，对k 的值的选取有会有所不同，同时不同性能的机器对测试结果也不同，所以对于k值的选取没有固定的数值。
#include<iostream>
#include<sys/timeb.h>
using namespace std;
#define M 40
void swap(int * a,int * b)
{
int tem;
tem=*a;
*a=*b;
*b=tem;
}
int partition(int v[],const int low,const int high)
{
int i,pivotpos,pivot;
pivotpos=low;
pivot=v[low];
for(i=low+1;i<=high;++i)
{
if(v[i]<pivot)
{
pivotpos++;
if(pivotpos!=i)swap(v[i],v[pivotpos]);
}
}
v[low]=v[pivotpos];
v[pivotpos]=pivot;
//cout<<"the partition function is called\n";
return pivotpos;
}
/*
void QuickSort(int a[], const int low,const int high) {
int item;
if(low<high)
{
item=partition(a,low,high);
QuickSort(a,low,item-1);
QuickSort(a,item+1,high);
}
}
*/
void QuickSort(int a[], const int low,const int high) {
int item;
if(high-low<=M)return;
if(low<high)
{
item=partition(a,low,high);
QuickSort(a,low,item-1);
QuickSort(a,item+1,high);
}
// cout<<"the QuickSort is called"<<endl;
}
void InsertSort(int a[],const int low,const int high)
{
int i,j;
int tem;
for(i=1;i<high+1;++i)
{
tem=a[i];
j=i-1;
while(j>=0&&tem<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=tem;
}
//cout<<"the InsertSort is called"<<endl;
}
void HybridSort(int a[],const int low,const int high)
{
QuickSort(a,low,high);
InsertSort(a,low,high);
cout<<"the HybidSort is called"<<endl;
}
int main()
{
int i,a[100];
//int *a=NULL;
long int t;
struct timeb t1,t2;
/*cout<<"please input the number of the element:"<<endl;
cin>>n;
a = (int*)malloc(n*sizeof(int));
cout<<"please input every element:"<<endl;
*/
for( i=0; i<100; i++)
{
a[i]=i+10;
}
//QuickSort(a,0,n-1);
ftime(&t1);
HybridSort(a,0,99);
cout<<" after sorted quickly,the result is"<<endl;
for(i=0; i<100; i++)
{
cout<<a[i]<<" ";
if(i%10==0)cout<<endl;
}
cout<<endl;
ftime(&t2);
t=(t2.time-t1.time)*1000+(litm); /* 计算时间差 */ printf("k=%d 用时%ld毫秒\n",M,t);
//cout<<"the memory of array a is free"<<endl;
//free(a);
cout<<"\n"<<endl;
return 0;
}。
