算法实验报告.doc

《算法分析与设计》上机实验报告
姓名:郑翔
学号:120105031108
班级:软件三班
上机实验题目
上机实验一递归算法的设计与实现
计算整数的非负整数次幂
基于递归算法的插入排序
上机实验二递归算法的实现
自然归并算法的设计与实现
快速排序算法的设计与实现
上机实验三贪心算法的实现
背包问题的设计与实现
2. 单源点最短路径问题的设计与实现
算法设计思路
上机实验一递归算法的设计与实现


源程序代码
上机实验一递归算法的设计与实现

#include <iostream>
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:"<<endl;
cin>>x>>n;
sum=power(x,n);
cout<<"x的n次幂为:"<<sum<<endl;
return 0;
}
时间复杂度○(logn)
基于递归算法的插入排序
#include <iostream>
#include <string>
#include <fstream>
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(item<a[i])
a[i+1]=a[i];
else
break;
}
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<<a[i]<<";";
}
时间复杂度: ○(NlogN)
上机实验二递归算法的实现
自然归并算法的设计与实现
#include<iostream>
#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(low<high)
{
mid=(low+high)/2;
mergesort(A,low,mid);
mergesort(A,mid+1,high);
merge(A,low,mid,high);
}
}
void main()
{
cout<<"Please input ten numbers:"<<endl;
for(int i=0;i<=9;i++)
{
cin>>A[i];
}
cout<<"The input numbers