信息学部算法分析上机报告学号0901******** 姓名陈龙指导老师秦明时间2011.11.1~11.23一．上机实验题目实验1比较归并排序和快速排序的区别。
实验2利用贪心算法对背包问题进行求解。
二．算法设计思路归并排序：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列，设定两个指针，最初位置分别为两个已经排序序列的起始位置，比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置，重复步骤直到某一指针达到序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。
快速排序：设置两个变量I、J，排序开始的时候：I=0，J=N-1；以第一个数组元素作为关键数据，赋值给key，即key=A[0]；从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与key交换；从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与key交换；重复第3、4、5步，直到I=J；(3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。
找到并交换的时候i，j指针位置不变。
另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。
)背包问题：用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。
可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]}三. 源程序归并排序#include<stdio.h>#include<stdlib.h># define N 50int b[N],a[N];int n,i;void Merge (int low, int mid,int high) //合并{int i; int l=low,h=mid+1,k=l;while ((l<=mid) && (h<=high)) //部分合并{if (a[l]<=a[h]) b[k++]=a[l++];else b[k++]=a[h++];}if(l>mid)while (h<=high) b[k++]=a[h++]; //转储剩余部分 elsewhile(l<=mid) b[k++]=a[l++];for (i=0;i<=high;i++) //将b数组转储到a a[i]=b[i];}int Merge2 (int l,int h) //分类{for (i=0;i<n;i++)printf("%d ",a[i]);printf("\n");int m;if (l<h){m=(l+h)/2;Merge2(l, m);Merge2(m+1, h);Merge ( l,m,h);}return a[i];}void main(){printf("请输入您要排序的数组大小（不超过50）：");while (scanf("%d",&n)!=EOF){for (i=0;i<n;i++)scanf("%d",&a[i]);Merge2(0,n-1);for (i=0;i<n-1;i++)printf("%d ",a[i]);printf("%d\n",a[n-1]);}}快速排序#include "stdio.h"#include "stdlib.h"# define N 50int a[N];int i,n;void Quick(int list[ ], int left, int right) //lfet为数组最左端, right为数组最右端{int s;int i, j;int temp;for (i=0;i<n;i++)printf("%d ",a[i]);printf("\n");if(left < right) //如果没有查询完所有数组，则继续递归{s = list[left];i = left-1;j = right + 1;while(i+1!=j){if(list[i+1]<=s)i++;else if(list[j-1]>s)j--;else{temp=list[i+1];list[++i]=list[j-1];list[--j]=temp;}}list[left] = list[i];list[i] = s;Quick(list, left, i - 1); //对左边递归Quick(list, i + 1, right); //对右边递归}}void main(){printf("请输入您要排序的数组大小（不超过50）：");while (scanf("%d",&n)!=EOF){for (i=0;i<n;i++)scanf("%d",&a[i]);Quick(a,0,n-1);for (i=0;i<n-1;i++)printf("%d ",a[i]);printf("%d\n",a[n-1]);}}背包问题#include <stdio.h>#include <stdlib.h>#define N 3struct Thing{int num ;int price;int weight;float aver;};void swap(int *i,int *j){int temp;temp = *i;*i = *j;*j = temp;}int main(){int M;int i,j,k=0,NUM = 1;struct Thing *p = (struct Thing *)malloc(N*sizeof(struct Thing));printf("请输入背包能承受的重量：");scanf("%d",&M);printf("\n");for(i=0;i<N;++i){// printf("请输入物品序列号(请从1开始顺序加1):");// scanf("%d",&p[i].num);p[i].num = NUM++;printf("请输入%d号物品的价值:",p[i].num);scanf("%d",&p[i].price);printf("请输入%d号物品的重量:",p[i].num);scanf("%d",&p[i].weight);p[i].aver = ((float)p[i].price / (float)p[i].weight);}for(i = 0;i<N-1;i++){for(j = i+1;j<N;j++){if(p[i].aver<p[j].aver){swap(&p[i].num,&p[j].num);swap(&p[i].price,&p[j].price);swap(&p[i].weight,&p[j].weight);}}}printf("\n");printf("按照物品单位重量的价值从大到小排序为：\n");for(i = 0;i<N;i++){printf("事件序列号：%d ",p[i].num);printf("物品价值%d ",p[i].price);printf("物品重量%d ",p[i].weight);printf("\n");}printf("\n");printf("\n");while(1){if(M > p[k].weight){printf("先装入%d号码的物品%d的重量,\n",p[k].num,p[k].weight);M = M - p[k].weight;k++;}elsebreak;}printf("再装入%d号的物品%d的重量\n",p[k].num,M);printf("\n");printf("\n");free(p);return 0;}三．实验结果归并排序快速排序背包问题五．实验心得通过实验可以知道，若数据比较无序，快排快，若数据中部分有序，归并快。
我觉得算法是一门理论和实践性都很强的课程，从算法和对算法的分析，几乎都是对具体问题的抽象。
因而，我们需要更多的时间来理解、掌握相关的知识，并利用电脑在机子上运行敲打代码，吸收算法的精髓。
当然在这一过程中也存在很多问题，比如我们不能完全理解算法，不能将之在上机实验中将之实现，对于算法的一些小细节不够清晰，影响了我们对算法的理解，但我觉得我们很幸运，因为秦老师在有限的课程中尽量将知识点以比较容易接受的方式给我们讲解，教我们用简单的方法理解记忆不同的知识，对于我们提出的问题，无论课上或是课外，老师一直是不厌其烦，甚至利用课余时间为我们讲解重要的难题。