文档介绍：实验一
实验名称: 二分制法的快速排序
实验时间: 2012年12月6日成绩:
一、实验目的:
利用分治策略的快速排序算法,对一组数按照从小到大的方式进行排序,此算法在C++语言上的实现。
二、实验内容:
快速排序法的基本思想为分治法,通过一次分割,将无序序列分为两部分,其中,前一部分的元素值均小于后一部分的元素值。然后每一部分再各自递归进行上述过程,直到每一部分的长度为1为止。我们知道排序的计算量通常是与序列长度的平方成正比,所以分治法将序列一分为二,再各自排序,将大大降低计算量,所以快速排序是一种高效的排序方法。
三、实验过程
#include<>
int part(int s[],int p,int r)   //把大于s[p]的数放一边,小于它的数放一边
{
 int x = s[p];
 int i = p+1;
 int j = r;
 while(true)
 {
  while(s[i] < x && i<=r)  i++;
  while(s[j] > x && j
>=1)  j--;
  if(i >=j)
   break;
  int temp = s[i];
  s[i] = s[j];
  s[j] = temp;
 }
 s[p] = s[j];
 s[j] = x;
 return j;
}
void quicksort(int s[],int p,int r)
{
 if(p < r)
 {
  int q = part(s,p,r);
  quicksort(s, p,q-1);
  quicksort(s,q+1,r);
 }
}
int main()
{
 int s[] = {4,65,12,43,67,5,78,10,3,70};
 int p = 0;
 int r= sizeof s/sizeof *s -1;
 cout<<"排序前: "<<endl;
 for(int i=0;i<=r;i++)
  cout<<s[i]<<"  ";
 cout<<endl;
 quicksort(s,p,r);
 cout<<"排序后: "<<endl;
 for(i=0;i<=r;i++)
  cout<<s[i]<<"  ";
 cout<<endl;
}
四、实验结果(总结/方案)
程序运行的结果:
实验二
实验名称: 应用贪心算法求解背包问题
实验时间: 2012-12-6 成绩:
一、实验目的:
了解贪心算法的内涵,以及实现求解背包问题。
二、实验内容
背包问题指的是:有一个承重为W的背包和n个物品,它们各自的重量和价值分别是和(),假设,求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候,只能全部拿走,则这一问题称为离散(0-1)背包问题;如果每次
可以拿走某一物品的任意一部分,则这一问题称为连续背包问题。
三、实验过程
首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策