算法实验报告

《算法分析与设计》上机实验报告

姓名：郑翔学号：班级：软件三班

120105031108

一、 上机实验题目

上机实验一 递归算法的设计与实现 1. 计算整数的非负整数次幂 2. 基于递归算法的插入排序 上机实验二 递归算法的实现 1. 自然归并算法的设计与实现 2. 快速排序算法的设计与实现 上机实验三 贪心算法的实现 1. 背包问题的设计与实现

2. 单源点最短路径问题的设计与实现 二、 算法设计思路

上机实验一 递归算法的设计与实现 1.计算整数的非负整数次幂

2.基于递归算法的插入排序

三、 源程序代码

上机实验一 递归算法的设计与实现 1.计算整数的非负整数次幂

#include

using namespace std;

int power(int x,int n) {

int y;

if(n==0) y=1; else{ y=power(x,n/2); y=y*y; if(n%2==1) y=y*x; }

return y; }

int main() {

int x,n;

int sum=0;

cout<<\"请输入整数x,非负整数n：\"<>x>>n;

sum=power(x,n);

cout<<\"x的n次幂为：\"<时间复杂度○（logn） 2. 基于递归算法的插入排序

#include #include

#include

using namespace std;

void insertionSort(int *a,int item,int size) {

if(size==0) a[0]=item; else {

for(int i=size-1;i>=0;i--) {

if(itembreak; }

a[i+1]=item; size--;

insertionSort(a,a[size],size); } }

void main() {

int a[7]={3,2,4,7,6,8,1}; insertionSort(a,1,6); for(int i=0;i<7;i++) cout<时间复杂度: ○（NlogN） 上机实验二 递归算法的实现 1. 自然归并算法的设计与实现

#include #define N 10

using namespace std; int A[N];

void merge(int A[],int low, int mid, int high) { int i=low; int j=mid+1; int T[N]; int k=0; while (i<=mid && j<=high) { if (A[i] <= A[j]) { T[k] = A[i]; i++; k++; } else { T[k] = A[j]; j++; k++; } } if (i == mid+1) { while (j <= high) { T[k] = A[j]; k++; j++; } } else { while (i <= mid) {

T[k] = A[i]; k++; i++; } } for (i=low,k=0; i<=high; i++,k++) A[i] = T[k]; }

void mergesort(int A[],int low,int high) { int mid=0; if(lowvoid main() { cout<<\"Please input ten numbers:\"<>A[i]; } cout<<\"The input numbers are:\"<○（nlog n）

2. 快速排序算法的设计与实现

#include using namespace std; int a[10];

void qs(int s,int e) {

int x=a[s],l=s,r=e;//以第一个数为参照做比较 if(l>=r)return; while(lwhile(l=x)

r--; //不小于分界值的留在右边，遇到小于的停止 a[l]=a[r];

while(ll++; //小于分界值的留在左边，遇到不小于的停止 a[r]=a[l]; }

a[r]=x; qs(s,r-1);

qs(r+1,e);//递归 }

int main() {

int i; cout<<\"请输入十个数：\"<cin>>a[i]; //输入数组元素 qs(0,9); //执行排序函数

for(i=0;i<10;i++) //输出排序后结果 cout<○（nlog n）

上机实验三 贪心算法的实现 1. 背包问题的设计与实现

#include using namespace std; struct goodinfo { float p;//物品效益 float w;//物品重量 float X;//物品该放的数量 int flag;//物品编号 };//物品信息结构体

void Insertionsort(goodinfo goods[],int n)//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序 { int j,i;

for(j=2;j<=n;j++) {

goods[0]=goods[j]; i=j-1; while(goods[0].p>goods[i].p) { goods[i+1]=goods[i]; i--; }

goods[i+1]=goods[0]; }

}//按物品效益，重量比值做升序排列

void bag(goodinfo goods[],float M,int n) { float cu; int i,j;

for(i=1;i<=n;i++) goods[i].X=0;

cu=M;//背包剩余容量? for(i=1;icu-=goods[i].w;//确定背包新的剩余容量 } else { goods[i].X=0; }

for(j=2;j<=n;j++)/*按物品编号做降序排列*/ { goods[0]=goods[j]; i=j-1;

while(goods[0].flaggoods[i+1]=goods[0]; } } cout<<\"最优解为:\"<void main() { cout<<\"|--------运用贪心法解背包问题---------|\"<goodinfo*goods;//定义一个指针 while(j) { cout<<\"请输入物品的总数量：\"; cin>>n; goods=new struct goodinfo [n+1]; cout<<\"请输入背包的最大容量：\"; cin>>M; cout<>goods[i].w; cout<<\"请输入第\"<>goods[i].p; goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比 cout< to run agian\"< to exit\"<>j; } }

3. 单源点最短路径问题的设计与实现

#include #include using namespace std; #define MAX 999

void getdata(int **c,int n) { int i,j; int begin,end,weight; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(i==j) c[i][j]=0; else c[i][j]=MAX; } } do { cout<<\"请输入 起点 终点 权值(-1退出)：\"; cin>>begin; if(begin==-1) break;

cin>>end>>weight; c[begin][end]=weight; } while(begin!=-1); }

void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i<=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j]void PrintPath(int *prev,int n,int begin,int end) { int *path=new int [n+1]; int i,m=n; bool k=true;

path[end]=end; for(i=end-1;i>1;i--) { path[i]=prev[path[i+1]]; //构造路径 m--; } for (i=m;i<=end;i++) { cout<\"; //输出路径 } cout<<\"\\b\\b\"<<\" \"<void main() { int n,i; int v=1; cout<<\"请输入顶点个数：\"; cin>>n; int *dist=new int [n+1]; int *prev=new int [n+1]; int **c; c=new int *[n+1]; for (i=0;i<=n;i++) { c[i]=new int [n+1]; } getdata(c,n); //获取数据 int begin=1,end; cout<<\"请输入所求单源路径的 起点 终点：\"; cin>>begin>>end; v=begin; Dijkstra(n,v,dist,prev,c); //计算路径 PrintPath(prev,n,begin,end); //输出路径 system(\"pause\"); }