算法设计实验报告.doc

文档介绍：本科实验报告
课程名称：算法设计与分析
实验地点：
专业班级：学号：
学生姓名：
指导教师：
年月日
实验一 分治法
实验目的
掌握快速排序和对半搜索的基本思想
掌握快速排序和对半搜索的实现方法
学会分析算法的时间复杂度
学会用分治法解决实际问题
实验环境
程序设计语言：c
编程工具：visual c++
算法描述和程序代码
一、实验程序
1）快速排序
#include<>
void quicksort(int a[],int left,int right);
int main()
{
int a[10],n = 10,i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
quicksort(a,0,n-1);
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
return 0;
}
void quicksort(int a[],int left,int right)
{
int i,j,b;
if(left<right)
{
i = left,j =right,b = a[left];
while(i < j)
{
while(i < j && a[j] >= b)
j--;
if(i < j)
a[i++] = a[j];
while(i < j && a[j] < b)
i++;
if(i < j)
a[j--] = a[i];
}
a[i] = b;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}}
2）对半搜索
#include<>
int binarySearch(int a[],int left,int right,int x);
int main()
{
int a[10] = {5,7,6,9,10,11,12,16,18,20};
int x;scanf("%d",&x);
int m = binarySearch(a,0,9,x);
if(m==-1)
printf("\nNo such Element\n");
else
printf("\nX at %d",m);
return 0;
}
int binarySearch(int a[],int left,int right,int x)
{while(left<=right)
{int mid = (left + right)/2;
if(a[mid] == x)
return mid;
else if(a[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
试验结果
五、实验总结
在这次实验中更加认识了分治法，用递归程序能节省程序的长度。掌握了快速排序和对半搜索的基本思想和实现方法，分析了算法的时间复杂度，会用分治法解决实际问题。
实验二：贪心法
一、实验目的
掌握贪心算法的基本思想
掌握贪心算法的典型问题求解
进一步掌握多级调度的基本思想和算法设计方法
学会用贪心法分析和解决实际问题
二、实验环境
程序设计语言：c
编程工具：microsoft visual c++
三、方法描述和程序代码
一、实验程序
分数背包问题
#include<>
void quick_sort(long long A[][2],long long left,long long right);
float knapsack(long long p[][2],long long weight,long long left,long long right);
int main()
{
long long value,weight,i,n;
float maxvalue;
scanf("%lld %lld",&n,&weight);
long long A[n][2];
for(i=0;i<n;i++)
{
scanf("%lld %lld",&A[i][0],&A[i][1]);//价值，重量
}
quick_sort(A,0,n-1);
maxvalue = knapsack(A,weight,0,n-1);
print