《算法分析与设计》实验指导书_算法设计实验指导书

《算法分析与设计》实验指导书由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“算法设计实验指导书”。

计算机科学与技术学院

算法分析与设计

实验指导书

于洪 编写 2011年8月

目 录

实验一实验二实验三实验四附录1 附录2 排序问题求解…………………………..…..………3 背包问题求解…………………………..…………..5 最短路径问题求解………………..………………..8 N-皇后问题求解…………………………………..10关于文件的操作……………………………….….12 关于如何统计运算时间…………………………..13

实验一

排序问题求解

实验目的1）以排序（分类）问题为例，掌握分治法的基本设计策略。2）熟练掌握一般插入排序算法的实现； 3）熟练掌握快速排序算法的实现； 4)理解常见的算法经验分析方法； 实验环境

计算机、C语言程序设计环境 实验学时

2学时，必做实验。实验内容与步骤 1.生成实验数据.要求：编写一个函数datagenetare，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为后面算法的实验数据。2.实现直接插入排序算法.要求：实现insertionsort算法。

算法的输入是data.txt；

输出记录为文件：resultsIS.txt；同时记录运行时间为TimeIS。直接插入算法思想：

Procedure insertionsort(A,n)

A(0)=-

for j=2 to n do item=A(j);i=j-1 while item

repeat End insertionsort 3.实现快速排序算法.要求：实现QuickSort 算法。

算法的输入是data.txt；

输出记录为文件：resultsQS.txt；同时记录运行时间为TimeQS。

快速排序算法思想： Procedure QuickSort（p,q）

integer p,q；global n,A(1:n)

if p

j ← q+1

call Partition(p, j)

call QuickSort(p, j-1)

call QuickSort(j+1, q)

end if end QuickSort

实验报告：

实验报告应包括以下内容：

用A(m)划分集合A的函数： Procedure partition(m,p)

integer m,p, I;global A(m:p-1)v=A(m);I=m Loop

loop I=I+1 until A(I)>=v repeat loop p=p-1 until A(p)

then call interchange(A(i), A(p))

Else exit Endif Repeat

A(m)=A(p);A(p)=v End partition（1）题目；

（2）2个算法的基本思想描述；（3）算法理论分析（参考教材）；

（4）程序流程图；

（5）给出data.txt、resultsIS.txt、resultsQS.txt三个文件任选其一的清单；

TimeIS、TimeQS的记录结果；

（6）实验分析；以表或者图的形式给出这2个算法的经验对比分析结果；并和理论分析结论进行对比。

（7）说明本次调试实验的心得体会、经验等。如果程序未通过，应分析其原因。

实验二

背包问题求解

实验目的1）以背包问题为例，掌握贪心法的基本设计策略。

2）熟练掌握各种贪心策略情况下的背包问题的算法并实现；其中：量度标准分别取：效益增量P、物品重量w、P/w比值；

3)分析实验结果来验证理解贪心法中目标函数设计的重要性。

实验环境

计算机、C语言程序设计环境

实验学时

2学时，必做实验。

实验内容与步骤

1.理解需要求解背包问题.（1）背包问题的描述：已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为益，这里，0xi1wi。假定将物品i的一部分

xi放入背包就会得到

pixi的效,pi0。显然，由于背包容量是M，因此，要求所有选中要装入背包的物品总重量不得超过M.。如果这n件物品的总重量不超过M，则把所有物品装入背包自然获得最大效益。现需解决的问题是，在这些物品重量的和大于M的情况下，该如何装包，使得得到更大的效益值。由以上叙述，可将这个问题形式表述如下：

极 大 化目标函数

约束条件

1inpixi

w1inixiM

0xi1,pi0,wi0,1in（2）用贪心策略求解背包问题

首先需确定最优的量度标准。这里考虑三种策略： 策略1：按物品价值p降序装包，策略2：按物品重w升序装包 策略3：按物品价值与重量比值p/w的降序装包

（3）分别以上面三种策略分别求以下情况背包问题的解： n=7，M=15，（p1,,p7）=（10，5，15，7，6，18，3）（w1,,w7）=（2，3，5，7，1，4，1）。以策略3为例的背包问题的贪心算法描述：

procedure GREEDY-KNAPSACK(P,W,M,X,n)//P（1：n）和W（1：n）分别含有按P（i）/W（i）≥P（i+1）/ W（i+1）排序的n件物品的效益值和重量。M是背包的容量，而X（1：n）是解向量。//

real P(1：n)，W（1：n）,X（1：n），M，cu；

integer i，n;X0

//将解向量初始化为零 cuM //cu是背包剩余容量 for i1 to n do

if W(i)>cu then exit endif

X(i)1

cucu-W(i)repeat if i≤n then X(i)cu/W(i)endif end GREEDY-KNAPSACK 2.以策略1作为量度标准求解要求问题，记录解向量为X1、目标函数的值fp1（即最后装好包后背包的效益值

1in、背包的重量fw1； pixi）3.以策略2作为量度标准求解要求问题，记录解向量为X21、目标函数的值fp2（即最后装好包后背包的效益值

1in、背包的重量fw2；

pixi）4.以策略3作为量度标准求解要求问题，记录解向量为X3、目标函数的值fp3即最后装好包后背包的效益值实验报告：

实验报告应包括以下内容：

1in、背包的重量fw3；

pixi）（1）题目；

（2）算法的基本思想描述；（3）程序流程图；

（4）给出3个程序任意之一的程序清单；

（5）实验分析；通过实验结果对比分析说明哪种策略好。

（6）说明本次调试实验的心得体会、经验等。如果程序未通过，应分析其原因。

Tips：

1.解向量的表示。需要注意：因为算法中涉及到排序，如何保证各种物品的原始命名（如果以第几种，即序号，来命名物品）关系需要考虑。

#define MAX 200 typedef struct Solution //定义的解向量

{

int x[MAX];表示该号物品放了多少在背包里，这里0xi

1int order[MAX];表示物品的序号，相当于其名字

}Solution;Solution X;所以，初始化时，为： for(i=0;i

{

X.order[i]=i;

X.x[i]=0;

}

2.主要函数：

void GreedyKnapsack(float profit[],float weight[],float x[],int m, int n){

float cu;

int i;

cu=float(m);

for(i=0;i

{

x[i]=0;

}

for(i=0;i

{

if(weight[i]>cu)

break;

x[i]=1;

cu=cu-weight[i];

}

if(i

{

x[i]=cu/weight[i];

} } 实验三

最短路径问题求解

实验目的：

1）以最短路径问题为例，掌握动态规划的基本设计策略； 2）掌握dijkstra贪心法求解最短路径问题并实现；

3）掌握动态规划方法Floyd算法求解最短路径问题并实现； 3）分析实验结果。实验环境

计算机、C语言程序设计环境 实验学时

2学时，必做实验。实验内容与步骤

1.以下图作为输入，利用dijkstra贪心法获取由结点1到其余结点最短路径长度，输出保存到外部文件dijkstra－output1.txt3 4 5 2 1 2.然后改写你的程序，求得所有各点之间的最短距离;输出保存到文件dijkstra－output2.txt.3.以上图作为输入，利用Floyd算法求得所有各点直接的最短距离;输出保存到文件floyd－output1.txt.实验报告

实验报告应包括以下内容：

（1）题目；

（2）写出算法设计思想；

（3）程序清单；（4）运行的结果；

（5）对运行情况所作的分析以及本次调试程序所取的经验。如果程序未通过，应分析其原因。

Tips: 主要函数

void dijkstra::algorithm()//算法函数 { initialize();int count=0;int i;int u;while(count

u=minimum();

set[++count]=u;

mark[u]=1;

for(i=1;i

{

if(graph[u][i]>0)

{

if(mark[i]!=1)

{

if(pathestimate[i]>pathestimate[u]+graph[u][i])

{

pathestimate[i]=pathestimate[u]+graph[u][i];

predeceor[i]=u;

}

}

}} }}

//-------------float graph[maxsize][maxsize];//成本矩阵，邻接矩阵 //floyd algorithm

for(k = 0;k

{

// graph[i][j] = min {graph[i][j]}, graph[i][k] + graph[k][j]

for(i = 0;i

//每次找到最优的路径代替原来的路径

for(j = 0;j

if(graph[i][j] > graph[i][k] + graph[k][j])//状态转换条件

{

graph[i][j] = graph[i][k] + graph[k][j];//状态转换方程

}

}

实验四：N-皇后问题求解

实验目的：

1）以Q-皇后问题为例，掌握回溯法的基本设计策略。2）掌握回溯法解决Q-皇后问题的算法并实现； 3）分析实验结果。

实验环境 计算机、C语言程序设计环境

实验学时 2学时，必做实验。

实验内容与步骤

1.用回溯法求解N-Queen，参考教材算法思想，并实现你的算法。要求：用键盘输入N；输出此时解的个数，并统计运算时间。2.给出N=4,5,6时，N-Queen解的个数。

3.尝试增大N，观察运行情况；并理解该算法的时间复杂度。实验报告

实验报告应包括以下内容：

（1）题目；

（2）写出算法设计思想；

（3）运行的结果；

（4）对运行情况所作的分析以及本次调试程序所取的经验。（5）如果程序未通过，应分析其原因。

Tips: 主要函数等

while(k>0)//对所有行执行以下语句

{

X[k] = X[k]+1;//移到下一列

while(X[k]

{

X[k] = X[k]+1;//移到下一列，再判断

}

if(X[k]

{

if(k==n)//一个完整的解

{

//print

printf(“the soution is:n”);

for(t=1;t

printf(“%3d”,X[t]);

printf(“n”);

count +=1;

}

else

{k=k+1;X[k]=0;} //转向下一行

}

else

k=k-1;//回溯

}

printf(“n the number of the solutions is %d n”, count);

bool PLACE(int k){ i=1;while(i

if(X[i]==X[k] || abs(X[i]-X[k])==abs(i-k))

return false;

i=i+1;} return true;}

附录1关于文件的操作

以背包问题为例：

1，例如外部文件为knapsack-input.txt：

2, 读入文件的操作： FILE* fp;

/* Open for read(will fail if file “knapsack-input.txt” does not exist)*/

if((fp = fopen(“knapsack-input.txt”, “r”))== NULL)

printf(“The file 'knapsack-input.txt' was not openedn”);

else

printf(“The file 'knapsack-input.txt' was openedn”);

//读输入文件，写n,M,p[MAX],w[MAX] fscanf(fp,“n=%dn”,&n);

fscanf(fp,“M=%dn”,&M);

for(i=0;i

for(i=0;i

fscanf(fp,“%f”,&weight[i]);fscanf(fp,“n”);

/* Close stream */

if(fclose(fp))

printf(“The file 'knapsack-input.txt' was not closedn”);附录2关于如何统计运算时间

#include “time.h” …….//----start time-----设置计时开始

double duration;

clock_t finish, start;start = clock();

……

//----finish time-----设置计时结束

finish = clock();

duration =(double)(finish-start)/ CLOCKS_PER_SEC;

printf(“nThe CPU time is %2.6f seconds:n”, duration);

// 统计时间duration