算法分析及设计实验报告

z

. . .

算法分析与设计 实 验 报 告

专业班级： 姓 名： 学

号：

. . .

指导老师：

实验一 递归算法的设计与实现 • 计算整数的非负整数次幂

(1)设计思路

对于34按步骤可以分析： 34=32*32 32=31*31 31=31*1

对于33按步骤可以分析： 33=32*31； 32=31*31； 31=31*1；

分析可以得到：

当xn中n为奇数时，xn=x*(xn/2)2 当xn中n为偶数的，xn=（xn/2）2； 当n/2=0;return 1；

一步步进行递归返回计算，如果n位奇数，在进行一部乘以x 否则返回运算结果

(2)源程序代码

#include using namespace std;

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

z

. . .

y=y*y; if(n%2==1) { y=y*x; } } return y; }

void main() {

cout<<\"请输入一个底数X：\"; int x; cin>>x;

cout<<\"请输入一个指数Y: \"; int y; cin>>y; if(y<0) { cout<<\"你的输入有误：请重新输入:\"<>y; } int c;

c=power(x,y);

cout<z

. . .

(3)代码运行结果

(4)时间复杂度

令n=2k，则可以得到：f(n)=g(k)=k+1=logn+1=O(logn)

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

(1)设计思路

通过主函数传来一个数组的首地址和数组的长度，然后利用递归的原理，当n=0；程序返回，执行入栈的递归程序，依次比较2个数的大小，3个数的大小等，根据比较的结果将第n个数插入适当的位置。

(2)源程序代码

#include

z

. . .

using namespace std;

void insert (int a[],int n) { int k; int b; n=n-1; if(n>0) { insert(a,n); b=a[n]; k=n-1; while((k>=0)&&(a[k]>b)) { a[k+1]=a[k]; k=k-1; } a[k+1]=b; } }

void main() { int a[100]; int n; cout<<\"请输入数组A[]的元素个数n(1>n; cout<<\"请输入数组A[]的元素: \"; for(int i=0;i>a[i]; } insert(a,n); for(int j=0;jz

. . .

(3)代码运行结果

(4)时间复杂度

f(n)=f(n-1)+n-1=f(n-2)+n-1+(n+2)=n*(n-1)/2;

算法用于递归栈的工作单元数与n为同一数量级，即时间复杂度为O(n)

实验二 递归算法的实现 • 自然归并算法的设计与实现

• 设计思路

首先讲待排序的n个元素分成大致相同的子集合，然后分别对这两个子集进行排序最后将排好序的子集合归并成所要求的排好序的集合

• 源程序代码

#include #include

z

. . .

using namespace std; #define max 10

void Merger_Sort(int a[],int low,int high) { int temp[max]; if(lowvoid main() { int a[max]; int n;

z

. . .

}

cout<<\"请输入元素个数n: \"; cin>>n;

cout<<\"请输入\"<>a[i]; }

Merger_Sort(a,0,n-1); for(int j=0;jcout<(3)代码运行结果

(4)时间复杂度

自然规定排序算法的时间复杂度为：O(n).

z

. . .

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

• 设计思路

基本思想是通过一趟排序将要排序的数据分割成的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

• 源程序代码

#include using namespace std;

int Partition(int a[],int p ,int r) { int i = p,j=r+1,sub; int x = a[p]; while(true) { while(a[++i]x); if(i>=j) break; sub = a[i]; a[i] = a[j]; a[j] =sub; } a[p] = a[j]; a[j] =x; return j; }

void QuickSort(int a[],int p,int r) { if(pint main()

z

. . .

{ }

int a[100]; int n;

cout<<\"请输入数组元素个数n(0>n;

cout<<\"请输入数组元素: \"; for(int i=0;i>a[i]; }

QuickSort(a,0,n-1); for(int j=0;jcout<(3)代码运行结果

(4)时间复杂度

快速排序算法在最坏的情况下的运行时间是O(n^2)。如果选取数组中的中值元素作为划分元素，那么快速排序算法的时间复杂度应为O(nlogn)。此时快速排序算法的递归深度接

z

. . .

近于logn。因此，快速排序算法的的空间复杂度应为为O(logn)

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

(1)设计思路

将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为f[v]。所以按照这个程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值

(2)源程序代码

#include using namespace std; #define n 3

struct thing { float p; float w; float v; };

void quick (thing a[],int b) { int i; for(i=0;iz

. . .

for(int j=i+1;jfloat greedy(float M,thing a[],float x[],int b) { float m,p=0; for(int i=0;iz

. . .

return p; }

void main() { int i; cout<<\"输入三种物品的价格：\"<>a[i].p; } cout<<\"输入三种物品的重量：\"<>a[i].w; } float m=20; float x[n]; float p=greedy(m,a,x,n); cout<<\"最佳解\"<• 代码运行结果

z

. . .

(4)时间复杂度

背包问题算法的时间复杂度为O(n)

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

(1)设计思路

将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止

(2)源程序代码

#include using namespace std; typedef struct adj_list{

int v_num; float len; struct adj_list *next; }NODE;

#define MAX_FLOAT_NUM 3.14e38f #define N 50

void dijkstra(NODE node[], int n, int u, float d[], int p[]){ float temp; int i,j,t;

bool *s = new bool[n]; NODE *pnode; for( i=0; iif(!(pnode = node[u].next) ) { return; }

while(pnode)

z

. . .

{

d[pnode->v_num] = pnode->len; p[pnode->v_num] = u; pnode = pnode->next; }

d[u] = 0; s[u] = true; for( i=1; itemp = MAX_FLOAT_NUM; t = u;

for( j=0; jif(!s[j]&&d[j] temp = d[j]; } }

if(t==u){ // break; }

s[t] = true; pnode = node[t].next; while(pnode){

if(!s[pnode->v_num] && d[pnode->v_num] > d[t] + pnode->len ){

d[pnode->v_num] = d[t] + pnode->len;

p[pnode->v_num] = t; }

pnode = pnode->next; } }

delete s; }

void printWay(int i, int p[]) {

if(p[i]==-1)return; printWay(p[i], p);

cout<<\"->\"<void println() {

cout<<\"------------------------------------------------\"<z

. . .

int main() {

NODE node[N]; float d[N]; int p[N]; int n; int u; int i,v;

NODE *pnode;

cout<<\"请输入顶点个数：\"; cin>>n;

cout<<\"请输入源顶点u编号（0>u; u--;

cout<<\"请输入各个点到其他点的距离（输入顶点编号 距离，编号输入0表示结束）：\"<for( i=0; icout<<\"顶点\"<node[i] = *(new NODE); // 创建新结点 node[i].v_num = i; node[i].len = 0;

node[i].next = NULL;

while(cin>>v&&v>0){ pnode = new NODE; pnode->v_num = v-1; cin>>(pnode->len);

pnode->next = node[i].next; node[i].next = pnode; } }

dijkstra(node, n, u, d, p); println();

for( i=0; iif(u==i||d[i]==MAX_FLOAT_NUM)continue; //

cout<return 0; }

z

. . .

(3)代码运行结果

(4)时间复杂度

算法的时间主要消耗在将各种物品按照单位重量的价值从大到小的排序，因此，其时间复杂性为O(nlog2n)

实验心得

在计算机专业中，算法分析与设计是一门很重要的课程，很多人在编写程序的时候要依赖它，算法的学习对于培养一个人的逻辑思维能力有着极大的帮助，在一定程度上提高了我们思考分析及解决问题的能力。 如果一个算法有缺陷，或者该算法并不适合某个问题，执行这个算法，并不能解决这个问题。不同的算法也会导致不同的时间，空间及效率来完成同样的问题，所以如针对问题需求选择最合适的算法也需要我们日后深入学习。就目前来说，我们还不具备编写完整程序的能力，但是，我们现在最需要的是培养针对问题能迅速找准对应算法来解决问题的能力。最后，此次算法的学习，我收获颇丰。

z