算法分析及设计实验报告.docx

排序问题求解 实验日志实验题目： 排序问题求解实验目的：1）以排序（分类）问题为例，掌握分治法的基本设计策略。2）熟练掌握一般插入排序算法的实现；3）熟练掌握快速排序算法的实现；4) 理解常见的算法经验分析方法；实验要求：1. 生成实验数据.要求：编写一个函数datagenetare，生成2000个在区间1,10000上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为后面算法的实验数据。2. 实现直接插入排序算法.3. 实现快速排序算法.实验主要步骤：#include#include#include#include#define RAND_MAX 10000#define Max 1000int I_Change_count = 0; /插入排序比较计数器int I_Move_count = 0; /插入排序移动计数器int S_Change_count =0; /选择排序比较计数器int S_Move_count = 0; /选择排序移动计数器int Q_Change_count = 0; /快速排序比较计数器int Q_Move_count = 0; /快速排序移动计数器void main()long num;long ArrayMax,BrrayMax,CrrayMax;/分别用来保存随机数 作为两个排序的对象int A_Length;int Low = 0;int High;time_t t;void InsertSort(long Array,int A_Length);/void SelectSort(long Brray,int A_Length);void QuickSort(long Crray,int Low,int High);srand(unsigned) time(&t);/*用时间初始化随机函数*/int T,i;printf(输入你想要比较的数的个数，本算法是按照2的次方来计算的:);scanf(%d,&T);A_Length = (int)pow(2.,T);if(A_Length 1000)exit(0); /如果比较次数大于100000，退出程序High = A_Length - 1;printf(比较的个数为：%dn,A_Length);printf(=原序列=n);for(i=0;iA_Length;i+)Arrayi=rand()%1000000;/产生1000000内的第一个随机数Brrayi=Arrayi;Crrayi=Arrayi;printf(%ldt,Arrayi);printf(nn);printf(=插入排序后的序列=n);InsertSort(Array,A_Length);for(i=0;iA_Length;i+)printf(%ldt,Arrayi);printf(n=插入排序的时间复杂度=);printf(n插入排序：比较次数=%d,移动次数=%d,时间复杂度=%dnn,I_Change_count,I_Move_count,I_Change_count+I_Move_count);/*printf(=选择排序后的序列=n);SelectSort(Brray,A_Length);for(int i=0;iA_Length;i+)printf(%ldt,Brrayi);printf(n=选择排序的时间复杂度=);printf(n选择排序：比较次数=%d,移动次数=%d,时间复杂度=%dnn,S_Change_count,S_Move_count,S_Change_count+S_Move_count);*/printf(=快速排序后的序列=n);QuickSort(Crray,Low,High);for( i=0;iA_Length;i+)printf(%ldt,Crrayi);printf(n=快速排序的时间复杂度=);printf(n插入排序：比较次数=%d,移动次数=%d,时间复杂度=%dn,Q_Change_count,Q_Move_count,Q_Change_count+Q_Move_count); void InsertSort(long Array,int A_Length)int i,j;long signal; for(i = 1;i A_Length;i+) /依次插入Array1，Arrayn-1 if(ArrayiArrayi-1|(I_Change_count+&0)/比较失败时，比较计数器自加 I_Change_count +; /比较成功时因为“|”后面的不执行 所以比较计数器得自加 signal = Arrayi; j=i-1; /signal是哨兵，且是Arrayi的副本 do /从右向左在有序区Array1i-1中查找Arrayi的插入位置 I_Change_count +; /比较成功时直接执行 所以比较计数器放在此处 Arrayj+1=Arrayj;/将关键字大于Arrayi的记录后移 I_Move_count +; j-; while(signal Arrayj);/当signalArrayj时终止 I_Change_count +;/比较失败时，循环跳出 比较计数器自加一次 Arrayj+1=signal; /Arrayi插入到正确的位置上 /endifvoid SelectSort(long Brray,int A_Length)int i,j,k;long signal;for(i=0;iA_Length;i+)k = i;for(j=i+1;jA_Length;j+)S_Change_count +; /因为不管比较成不成功都要比较A_Length-j次/所以将比较计数器放在比较前if(Brrayj = High) return ;while(C_Low != C_High)while(C_Low = signal)C_High -;CrrayC_Low = CrrayC_High;while(C_Low C_High & CrrayC_Low = signal)C_Low +;CrrayC_High = CrrayC_Low;Q_Change_count +;CrrayC_Low = signal;Q_Move_count +;QuickSort(Crray,Low,C_Low-1);QuickSort(Crray,C_Low+1,High);实验结果：输入7共有128个数排序，运行结果如下心得体会： 通过本次实验更加深刻的了解的快速排序和直接插入排序算法，通过编写程序实现排序，掌握分治法的基本策略，明白了算法时间复杂度的分析，同一个要求，使用不同的算法，所需时间和空间不同，因此根据不同的实验要求，编写合适的算法是非常重要的，有利于缩短运行时间。通过本次实验，为后面学习各种复杂算法打下坚实的基础。 背包问题求解 实验日志实验题目：背包问题求解实验目的：1）以背包问题为例，掌握贪心法的基本设计策略。2）熟练掌握各种贪心策略情况下的背包问题的算法并实现；其中：量度标准分别取：效益增量P、物品重量w、P/w比值；3) 分析实验结果来验证理解贪心法中目标函数设计的重要性。实验要求：（1）用贪心策略求解背包问题首先需确定最优的量度标准。这里考虑三种策略：策略1：按物品价值p降序装包，策略2：按物品重w升序装包策略3：按物品价值与重量比值p/w的降序装包（2）分别以上面三种策略分别求以下情况背包问题的解：n=7，M=15，（）=（10，5，15，7，6，18，3）（）=（2，3，5，7，1，4，1）。实验主要步骤：void GreedyKnapsack(float profit,float weight,float x,int m, int n)float cu;int i;cu=float(m);for(i=0;in;i+) xi=0;for(i=0;icu)break; xi=1;cu=cu-weighti;if(in)xi=cu/weighti;实验结果：策略1运行结果如下：策略2运行结果如下：策略3运行结果如下：心得体会 通过本次实验，让我更加明白背包算法，编程实现气功能，使自己的编程能力得到提高，也让我明白在能力有限的情况下，怎么处理事情达到效果最佳，达到最优效果。对于不同的能力，可以有不同的最优解使之达到最优效果，这就是背包算法的真谛。 最短路径问题求解 实验日志实验题目：最短路径问题求解实验目的：1）以最短路径问题为例，掌握动态规划的基本设计策略；2）掌握dijkstra贪心法求解最短路径问题并实现；3）掌握动态规划方法Floyd算法求解最短路径问题并实现；实验要求：1. 以下图作为输入，利用dijkstra贪心法获取由结点1到其余结点最短路径长度，输出保存到外部文件dijkstraoutput1.txt5463122. 然后改写你的程序，求得所有各点之间的最短距离; 输出保存到文件dijkstraoutput2.txt.3. 以上图作为输入，利用Floyd算法求得所有各点直接的最短距离; 输出保存到文件floydoutput1.txt.实验主要步骤：#include#include#include#define M 999void main()int cost66=M,M,15,M,M,M,20,M,M,M,10,30,M,4,M, M,M,10 ,M,M,M, M, M,M,M,M,M, 15,M,M ,M,M,M, 4, 10,M ;typedef struct edgeint adjvex;/边的一个顶点int cost; /权值edge;int total=0; /计数变量，计算共选择节点多少个int adjvex6;/保存依次被选中的节点edge lowpathcost6;/初始值为矩阵的第一行。char path610=0,;/以0为初始节点开始计算最短路径 (路径)for(int i=1;i6;i+)lowpathcosti.cost=cost0i;/初始化为M，最短路径长度为矩阵的第一行权值if(cost0i!=M)lowpathcosti.adjvex=0;/有数据则adjvex置为0cout初始存在路径的是0-iendl;int min;/保存最小权值int minvex;/保存最小权值边的另一顶点int selected6=0;/次变量是作为控制已输出的节点不再参与的判断参数coutendl开始选择顶点：endl;for(int num=1;num=5;num+) /要选择的次数,共6个顶点,除掉起点min=M;for(i=1;ilowpathcosti.cost&!selectedi)min=lowpathcosti.cost;/第一次查找为10 即第一行中最小的值minvex=i;/此时i=2adjvex+total=minvex;/此时adjvex1为2，存放依次选出的顶点/adjvex2=1if(min!=M)cout第 num 次被选择的顶点是: minvex . 对应的边上的权值是 minendl;selectedminvex=1; /已参与的节点就置为1for(i=0;imin+costminvexi & min+costminvexiM)/3项都要满足lowpathcosti.cost=min+costminvexi;lowpathcosti.adjvex=minvex;for(i=1;i=5;i+)cout lowpathcosti.adjvex;coutendlendl;int eadjvex,sadjvex; char ep2;for(i=1;i=total;i+)eadjvex=adjvexi;sadjvex=lowpathcosteadjvex.adjvex;ep0=0+eadjvex; ep1=0;char tmp10;strcpy(tmp,pathsadjvex);strcpy(patheadjvex,strcat(tmp,ep);/ pathe=sp+ep;cout0 到顶点 eadjvex 的最短路径经历的节点依次是：patheadjvex 长度是：lowpathcosteadjvex.costendl;实验结果：心得体会：通过本次实验，了解了动态规划的基本设计策略。掌握了dijkstra贪心法求解最短路径问题的方法，并能够自己编写程序运行出结果，这让自己很有成就感。通过改写dijkstra算法，使之成为Floyd算法求解最短路径问题的方法。通过对比这两个算法的实现过程，更好地了解这两个算法的本质区别。 N-皇后问题求解 实验日志实验题目：N-皇后问题求解实验目的：1）以Q-皇后问题为例，掌握回溯法的基本设计策略。2）掌握回溯法解决Q-皇后问题的算法并实现；3）分析实验结果。实验要求：1. 用回溯法求解N-Queen，参考教材算法思想，并实现你的算法。要求：用键盘输入N；输出此时解的个数，并统计运算时间。2. 给出N=4,5,6时，N-Queen解的个数。3. 尝试增大