算法分析与设计实验报告.doc

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

目录

实验一 1

[实验题目] 1

[问题描述] 1

[算法设计] 1

[算法分析] 1

[源代码] 1

[运行结果] 2

实验二 2

[实验题目] 2

[问题描述] 2

[算法设计] 2

[算法分析] 2

[源代码] 2

[运行结果] 4

实验三 5

[实验题目] 5

[问题描述] 5

[算法设计] 5

[算法分析] 5

[源代码] 5

[运行结果] 6

1

实验一

[实验题目]

2-7集合划分问题

[问题描述]

n个元素的集合{1,2,…,n}可以划分为若干非空子集。例如，当n=4时，集合{1,2,3,4}可以划分为15个不同的非空子集。

[算法设计]

给定正整数n,计算出n个元素的集合{1,2,…,n}可以划分为多少个不同的非空子集。

[算法分析]

本算法实现采用分治法思想，F(n,m)=F(n-1,m-1)+m*F(n-1,m)。假设将m个

元素分解到n个集合中，首先考虑将(m-(n-1))个元素分到第一个集合中，

将余下的(n-1)个元素分别分配到余下的(n-1)个集合中，然后再考虑将

(m-(n-2))个元素分配到第一个集合中，将余下的(n-2)个元素分别分配

到余下的(n-1)集合中，依此类推，直到后面的有一个集合中的元素个数比第一个集合中的元素个数多为止。

[源代码]

#includeiostream

usingnamespacestd;

intcompute_bell(introw,intposition)

if(row==1)

return1;

if(row==2position==1)

return1;

else

{

if(position==1)

returncompute_bell(row-1,row-1);

else

returncompute_bell(row,position-1)+

compute_bell(row-1,position-1);

}

intmain(){

intn=0;

intm;

coutpleaseinputanumber.endl;

cinn;

m=compute_bell(n,n);

couttheresuleismendl;

2

[运行结果]

D:\ProgramFiles(x86)\DEV-CPP\work

D:\ProgramFiles(x86)\DEV-CPP\workspace\suanfe

pleaseinputanumber.

5

theresuleis,52

请按任意键继续..

实验二

[实验题目]

3-1独立任务最优调度问题

[问题描述]

用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai,若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i,有ai≥bi,而对于某些j,j≠i,有ajbj。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例：(al,a2,a3,a4,a5,a6)=

(2,5,7,10,5,2);(bl,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)。

[算法设计]

对于给定的2台处理机A和B处理n个作业，找出一个最优调度方案，使2台机器处理完这n个作业的时间最短。

[算法分析]

当完成k个作业，设机器A花费了x时间，机器B所花费时间的最小值肯定是x的一个函数，设F[k][x]表示机器B所花费时间的最小值。则

F[k][x]=Min{F[k-1][x]+b[k],F[k-1][x-a[k]]};其中F[k-1][x]+b[k]表示

第k个作业由机器B来处理(完成k-1个作业时机器A花费的时间仍是x),F[k-1][x-a[k]]表示第k个作业由机器A处理(完成k-1个作业时机器A花费的时间是x-a[k])。

那么单个点对较大值Max(x,F[k][x]),表示此时(即机器A花费x