算法设计与分析课程的心得体会

《算法设计与分析》课程的心得体会

以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件,必须遵循软件工程的原则,设计出高效率的程序。一个高效的程序不仅需要编程技巧,更需要合理的数据组织和清晰高效的算法。这正是计算机科学领域里数据结构与算法设计所研究的主要内容。一些著名的计算机科学家认为,算法是一种创造性思维活动,并且处于计算机科学与技术学科的核心。

在计算机软件专业中算法分析与设计是一门非常重要的课程,很多人为它如痴如醉。很多问题的解决,程序的编写都要依赖它,在软件还是面向过程的阶段,就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的,它可以培养我们养成思考分析问题,解决问题的能力。

如果一个算法有缺陷,或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。

计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件,都必须使用具体的算法来实现。

算法设计与分析是计算机科学与技术的一个核心问题。因此,学习算法无疑会增强自己的竞争力,提高自己的修为,为自己增彩。

那么,什么是算法呢?算法是指解决问题的方法或过程。算法满足四个性质,即输入、输出、确定性和有限性。为了了解算法,这个学期马老师带我们走进了算法的世界。

马老师这学期提出不少实际的问题,以及解决问题的算法。我在此只说比较记忆深刻的问题,即0-1背包的问题。

0-1背包问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

首先,0-1背包问题具有最优子结构性质和子问题重叠性质,适于采用动态规划方法求解。动态规划算法与分治法类似,其基本思想是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的,若用分治法解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。

用动态规划法解决问题的思路如下:

最优决策序列由最优决策子序列组成。假设f (i,y)表示剩余容量为y,剩余物品为i, i+1, …, n时的最优解的值,即:

       f (n,y) = Pn,if y≥Wn

       f (n,y) = 0,  if 0≤y≤Wn

f(i,y)=max(f(i+1,y),f(i+1,y-Wi)+Pi) y≥Wi

     f(i,y)=f(i+1,y) 0≤y≤Wi

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的,所以有必要将它详细解释一下:“将前i件物品放入容量为y的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为y的背包中”,价值为f[i-1][y];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为y-Wi的背包中”,此时能获得的最大价值就是f[i-1][y-Wi]再加上通过放入第i件物品获得的价值Pi。

用贪心算法解决问题的基本思路如下:

由所有解元素组合成问题的一个可行解;从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。

实现该算法的过程: 从问题的某一初始解出发;while 能朝给定总目标前进一步do求出可行解的一个解元素;

该算法存在问题:首先不能保证求得的最后解是最佳的;其次不能用来求最大或最小解问题,并且只能求满足某些约束条件的可行解的范围。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。所以0-1背包问题也可以用回溯法解决。其基本思路是可先将物品依其单位重量价值从大到小排序,此后只要顺序考察各物品即可,这是为了便于计算上界,。在实现时,由bound计算当前结点处的上界。在搜索解空间树时,只要其左儿子节点是一个可行结点,搜索就进入左子树,在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。

当然0-1背包问题还有许多的解决方案,此处就不一一列出。不过通过0-1背包问题,我深刻体会到算法的魅力,体会到同一个问题用不同的方法解决的妙处。学无止境,《算法设计与分析》仅仅是我学习算法知识入门课,我不会停下脚步,在此之后我依然会努力学习算法知识。

 

第二篇:算法设计与分析课程报告

1.蛮力算法(25分)

数值问题:设x=2,n=30,a0= n,a1= n-1,a3= n-2,…,an-2=2,an-1=1,要求用蛮力算法求解多项式p(x)= a0x0+a1x1+…+an-2 xn-2+an-1 xn-1的值。

1.1算法基本思想;(2分)

答:蛮力算法是根据问题的定义,根据问题的步骤,直接了当地对问题进行求解。蛮力算法的核心就是直接去做,直接去解决问题。

1.2算法描述(可以用流程图、自然语言或伪代码来描述);(3分)

答:据p(x)= a0x0+a1x1+…+an-2 xn-2+an-1 xn-1基于问题定义设计算法:直接先分别算出两个乘数,再求两个数的成绩,最后累加。

1.3算法实现的C源程序代码;(6分)

#include<stdio.h>

#include<math.h>

void main()

{

int x,n,i,A,X;

double p=0,sum=0;

printf("请输入x n:");

scanf("%d %d",&x,&n);

for(i=0;i<n;i++)

{

X=pow(x,i);

A=n-i;

sum=A*X;

p=p+sum;

}

printf("多项式的值为:%.0f\n",p);

}

1.4程序运行结果的屏幕截图;(6分)

1.5算法分析(可以从算法复杂度、优缺点或改进方法等角度来分析)。(6分)

答:①该算法时间复杂度为O(n),简短清晰便于阅读。

②在健壮性方面,此算法只对少量输入能做出正确的处理,在使用范围上有很大的限制性。如输入x=2,n=32,结果出错,如下图所示:

2 .分治算法(25分)

查找问题:输入100个整数,使用分治算法实现折半查找,统计某个整数出现的次数。

2.1算法基本思想;(2分)

答:将要求解的原问题划分成k个较小规模的子问题,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子问题划分为k个规模更小的子问题,如此分解下去,直到问题规模足够小,很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。

步骤:①划分 ②求解子问题 ③合并

2.2算法描述(可以用流程图、自然语言或伪代码来描述);(3分)

答:1、low=1;high=n;//设置初始查找区间

2、测试查找区间[low,high]是否存在,若不存在,则查找失败;否则

3、取中间点mid=(low+high)/2;比较k与[mid],有一下三种情况:

①若k<r[mid],则high=mid-1;查找在左半区进行,转2;

②若k>r[mid],则low=mid+1;查找在左半区进行,转2;

③若k<r[mid],则查找成功,统计k出现次数,返回统计记录

2.3算法实现的C源程序代码;(6分)

#include <iostream>

using namespace std;

void InsertSort(int A[] , int n)//插入排序

{

int i,j,temp;

for(i=1;i<n;i++)

{

j=i;

temp=A[i];

while(j>0&&temp<A[j-1])

{

A[j]=A[j-1];

j--;

}

A[j]=temp;

}

}

int BinSearch(int A[] , int key,int low,int high)//二分查找

{

int mid;

static int j=0;

while(low<=high)

{

mid=(low+high)/2;

if(key==A[mid]){

j++;

BinSearch( A,key,low,mid-1);

BinSearch( A,key,mid+1,high);

return j;

}

else if(key<A[mid])

high=mid-1;

else

low=mid+1;

}

return -1;

}

void main()

{

int n,i,key,j;

int low=0;

int high;

printf("请输入要排序的数的个数:");

scanf("%d",&n);

high=n;

int *a=new int[n];

printf("请输入要排序的数:");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

printf("排序后的数为:");

InsertSort(a,n);

for(i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

printf("请输入要查找的数:");

scanf("%d",&key);

j=BinSearch(a,key,low,high);

if(j==-1)

printf("未查到你要找的数!\n");

else

printf("查找结果为:%d\n",j);

}

2.4程序运行结果的屏幕截图;(6分)

2.5算法分析(可以从算法复杂度、优缺点或改进方法等角度来分析)。(6分)

答:该算法有很大的局限性,在查找完成之后并不能准确统计出某个整数出现的次数。

3. 贪心算法(25分)

活动安排问题:根据下表各个活动的时间,用贪心算法找出一个最大兼容活动集合。

活动编号

1

2

3

4

5

6

7

8

9

10

开始时间

3

2

5

1

7

12

8

6

11

13

结束时间

7

4

9

6

13

15

10

8

17

14

3.1算法基本思想;(2分)

从问题的某一个初始解出发逐步逼近给定的目标,对每一子问题求解,得到子问题的局部最优解,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。

3.2算法描述(可以用流程图、自然语言或伪代码来描述);(3分)

答:设有n个活动的集合e={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在半开时间区间[si,fi]内占用资源。若区间[si,fi]与区间[sj,fj]不相交,则称活动i与活动j是相容的。也就是说,当si≥fi或sj≥fj时,活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

3.3算法实现的C源程序代码;(6分)

#include<stdio.h>

void sort(int s[],int f[])

{

int a,b;

int i,j;

for(i=0;i<10;i++)

{

for(j=i+1;j<10;j++)

{

if(f[i]>f[j])

{a=f[i];f[i]=f[j];f[j]=a;

b=s[i];s[i]=s[j];s[j]=b;}

}

}

}

int activemanage(int s[],int f[],bool a[])

{

a[0]=1;

int i;

int j=1,count=1;

for(i=1;i<10;i++)

{

if(s[i]>=f[j])

{

a[i]=1;

j=i;

count++;

}

else a[i]=0;

}

return count;

}

void main()

{

int i,p;

int s[10],f[10];

bool a[10];

printf("请依次输入节目的开始和结束时间:\n");

for(i=0;i<10;i++)

{

scanf("%d %d",&s[i],&f[i]);

}

sort(s,f);

p=activemanage(s,f,a);

printf("安排的节目个数为:%d\n",p);

printf("节目的选取情况为(0表示不选 1表示选):\n");

for(i=0;i<10;i++)

printf("%d ",a[i]);

printf("\n");

}

3.4程序运行结果的屏幕截图;(6分)

3.5算法分析(可以从算法复杂度、优缺点或改进方法等角度来分析)。(6分)

答:执行效率不够高,算法不具备有较强的健壮性。

4. 回溯算法(25分)

0/1背包问题:对给定容量的背包,分别输入n(n>=10)个物品的重量、价值,然后用回溯算法求解使得总价值最大的装包方案。

4.1算法基本思想;(2分)

答: 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。

4.2算法描述(可以用流程图、自然语言或伪代码来描述);(3分)

答:n个物品,物品i的重量是Wi,其中其价值为Vi,其中0<=i<=n-1,背包的容量为C。用Xi表示物品i被装入背包的情况,如果物品Pi被选中,则Xi=1;否则Xi=0。求满足目标函数和约束方程的物品组合(x0,x1,x2,„,xn-1) 与相应的总价值V。

4.3算法实现的C源程序代码;(6分)

#include<stdio.h>

#define N 10 // 物品个数

#define C 200 //容积

int result[N]; //存储结果:0表示不在集合内,1表示在集合内

int tempR[N]; //当前结果

int w[N]; //重量

int v[N]; //价值

int tempV = 0; //当前价值

int maxV = 0 ; //最大价值

int tempW = 0 ; //当前的容量

void traceBack(int i )

{

if

(i>=N){

if(tempV>maxV){

maxV = tempV;

int j = 0;

for(j=0;j<N;j++){

result[j] = tempR[j];

}

}

return;

} //边界情况考虑

if(tempW+w[i]<=C){

tempR[i] = 1;

tempV+=v[i];//当前价值增加

tempW+=w[i]; //当前重量增加

traceBack(i+1);//进入下一层

tempV-=v[i]; //当前价值增加

tempW-=w[i]; //当前重量增加

} //左子树

//直接进入右子树

int k=0;

int cp = 0;

for(k=i+1;k<N;k++){

cp+= v[k];

}

if(tempV+cp>maxV){

tempR[i] = 0;//当前值舍弃

traceBack(i+1);

}

}

void main()

{ int i=0;

printf("请成对输入各个物品重量和价值:\n");

for(i=0;i<N;i++){

scanf("%d %d",&w[i],&v[i]);

}

traceBack(0);

printf("最大价值为%d\t",maxV);

printf("\n取值情况为\n");

for

(i=0;i<N;i++){

printf("%d\t",result[i]);

}

printf("\n");

for

(i=0;i<N;i++){

printf("%d\t",w[i]);

}

printf("\n");

for(i=0;i<N;i++){

printf("%d\t",v[i]);

}

printf("\n");

}//背包问题的调用

4.4程序运行结果的屏幕截图;(6分)

算法设计与分析课程报告

4.5算法分析(可以从算法复杂度、优缺点或改进方法等角度来分析)。(6分)

答:时间复杂度为O(2n+1),执行效率有待提高。在输入方面也需要改进,输入错误时无法提示。

相关推荐