算法与程序设计上机报告

上机实验一

一、实验题目

用分治法进行归并分类

二、 算法介绍

将A(1),......,A(n)均分成两个集合，在对每个集合单独分类，然后将已分类的两个序列归并成一个含n个元素的分好类的序列；merge（）函数负责把两个已分类集合归并在一起，mergesort（）函数通过使用递归和调用merge（）函数完成该处理过程

三、程序流程图：

说明：A[N]、B[N]是全程数组，A[] 存放待分类的元素，B[]是辅助数组

归并分类算法mergesort（递归算法）的具体扩展：

说明：入口参数：待分类集合A(low:high)的头和尾元素位置low、high

merge函数的具体扩展：//使用辅助数组归并两个已分类的集合

说明：入口参数：集合A(low:high)的头和尾元素位置low、high及该集合的分割点（二分）

2

四、源程序及实验结果

程序代码如下： #include #include #define N 1024

int A[N],B[N]; //A[N]、B[N]是全程数组，A[] 存放待分类的元素，B[]是辅助数组 void merge(int low,int mid,int high) //使用辅助数组归并两个已分类的集合

/*数组A（low：high）包含两个放在A(low:mid)和A(mid+1:high)中的已分类的子集合 *此函数是使用一个辅助数组B（low：high）将这两个已分类的集合归并成一个集合，并存放到A（low：high）中 */

{ int h,k,i,j; h=low; i=low; j=mid+1;

while(h<=mid&&j<=high) //当两个集合都没取尽时 { if(A[h]<=A[j]) { B[i]=A[h]; h++; }

else { B[i]=A[j]; j++; } i++; }

//处理剩余的元素

if(h>mid) /*A(low:mid)数组取完时，将A(mid+1:high)中剩余元素依次复制到数组B(low： high)尾部*/ { for(k=j;k<=high;k++) { B[i]=A[k]; i++; } }

else for(k=h;k<=mid;k++) /*A(mid+1:high)数组取完时，将A(low:mid)中剩余元素依次复制 到数组B(low：high)尾部*/

{ B[i]=A[k]; i++; }

for(k=low;k<=high;k++) //将已归并的集合复制到A中 { A[k]=B[k]; }

3

}

void mergesort(int low,int high) //归并分类

/*将本集合二分为两个集合，再递归调用merge（）函数对每个集合单独分类并将已分类的 *两个序列归并为一个分好类的序列 */

{ int mid;

if(low

{ mid=(int)floor((low+high)/2); //求这个集合的分割点 mergesort(low,mid); //将一个子集合分类 mergesort(mid+1,high); //将另一个子集合分类

merge(low,mid,high); //归并两个已分类的子集合 } }

void main()

{ int i=1,cx; //cx中存放待排序元素的个数 printf(\ //显示提示信息

scanf(\ //输入待排序元素的个数 printf(\

for(i=1;i<=cx;i++) //输入待排序的各个元素的值，并存放到集合A中 { scanf(\ }

mergesort(1,i-1); //调用归并分类算法对数组A（1：i-1）进行归并排序 printf(\

for(i=1;i<=cx;i++) //输出进行归并排序后的集合A { printf(\ }

getch(); }

运行结果如下图：(运行结果与理论结果一致)

五、结果分析

运行源程序后，先输入待排序元素的个数，回车。再分别输入打乱的元素的值序列，回车，显示按升序排列的元素值序列。

最坏情况：输入数据按非增次序排列,每次内层while循环执行j次（j=2,3,…, n)。则有，Ω(n(n+1)/2-1)= Ω(n2);

4

最好情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为Ω(n)。

上机实验二

一、实验题目

用分治法进行快速分类

二、算法介绍

在集合A(1:n)中选一元素t=A[s]，然后将其它元素重新排列，使A(1:n)中所有在t以前出现的元素都小于或等于t，而在t后出现的元素都不小于t,元素t为划分元素，快速分类就是通过反复对产生的集合进行划分来实现的。

三、程序流程图

说明：A[1024]是全程数组，其中存放待分类的元素 快速分类算法quicksort（递归算法）的具体扩展如下： 说明：入口参数:集合A（p:q）的p、q

5

partition函数的具体扩展如下：

说明：入口参数:集合A（m:q）的头m和尾后一个位置q

出口参数：划分元素A[m]在集合A排序后的集合中的位置

6

四、源程序及实验结果

程序代码如下：

#include

int A[1024]; //A[1024]是全程数组，其中存放待分类的元素void interchange(int i,int j) //将A[i]与A[j]换位 { int t; t=A[i]; A[i]=A[j]; A[j]=t;

7

}

int partition(int m,int p) //用划分元素A[m]划分集合A(m:p-1),并返回划分元素定位后的位置 //划分元素定位后其左边的元素不大于它，其右边的元素不小于它 { int i,v;

v=A[m]; //记下划分元素的值

i=m; //记下划分元素的起始位置

while(1) //查找划分元素在排序后的集合中的位置 { do //由左向右查找不小于划分元素的元素A[i] {

i++;

}while(A[i]

do //由右向左查找不大于划分元素的元素A[p] { p--;

}while(A[p]>v);

if(i

else break; }

A[m]=A[p]; //划分元素最终定位在集合A中p处 A[p]=v; return p; }

void quicksort(int p,int q) //快速分类（本算法为递归算法）

/*将全局数组A(1:n)中的元素A[p],.....,A[q]按递增的方式分类，认为A[n+1]已被定义，且不小于A(p:q)的所有元素，即A[n+1]为正无穷大（在主函数令正无穷大为1000） */ { int j; if(p

{ j=q+1; //此时j为划分元素的起始位置

j=partition(p,j); //此时j存放的是划分元素应在排序后的集合中的位置 //依次对由划分元素划分出的两个子集合进行快速分类 quicksort(p,j-1); quicksort(j+1,q); } }

void main()

{ int i,n; //n中存放待排序元素的个数 printf(\

scanf(\ //输入待排序元素的个数 printf(\

for(i=1;i<=n;i++) //输入待排序的各个元素的值，并存放到集合A中

8

scanf(\

A[n+1]=1000;

quicksort(1,n); //调用快速分类算法对数组A（1：n）进行归并排序 for(i=1;i<=n;i++) //输出进行快速排序后的集合A printf(\ getch(); }

运行结果如下图：(运行结果与理论结果一致)

五、结果分析

运行源程序后，先输入待排序元素的个数，回车。再分别输入元素的值序列，回车，就会显示按升序排列的元素值序列。不难看出，运行结果与理论结果一致。

记最坏情况下的元素比较次数是Cw(n)；PARTITION一次调用中的元素比较数是p-m+1，故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。

最坏情况下，每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和。 即：Cw(n)=Ο(n2)

9

上机实验三

一、 实验题目

贪心算法求背包问题

二、算法介绍

1、将若干物品装入背包，装入情况有三种：部分装入、全部装入和未装入； 2、量度标准：物品效益集合和容量集合分别按单位容量的效益增量的降序排列 3、排序方法：快速排序

三、程序流程图

说明：

存放物品的数目的变量n，数组A[1024]存放待分类元素，数组X[1024]存放解向量，数组W[1024]存放各物品的容量，数组P[1024]存放各物品的效益， 以上变量均是全局变量。

贪心算法greedy-knapsa的具体扩展如下： 说明：入口参数:背包容量m

10

四、源程序及实验结果

程序代码如下： #include

int n; //n用于存放物品的数目

float A[1024]; //数组A[]存放待分类元素（在本问题中是指物品的单位容量增量） float X[1024]; //数组X[]存放解向量，即各个物品在背包中的存放情况，0=

void interchangeP(int i,int j) //交换两整型效益的位置 { int t; t=P[i]; P[i]=P[j]; P[j]=t;

11

}

void interchangeW(int i,int j) //交换两整型容量的位置 { int t; t=W[i]; W[i]=W[j]; W[j]=t; }

int partition(int m,int p) //用划分元素A[m]划分集合A(m:p-1),并返回划分元素定位后的位置 { int i; float v; v=A[m]; i=m; while(1) { do {

i++;

}while(A[i]>v); do { p--;

}while(A[p]

if(i

{ interchange(i,p); //将A[i]与A[j]换位 interchangeP(i,p); //将P[i]与P[j]换位 interchangeW(i,p);//将W[i]与W[j]换位 }

else break; }

A[m]=A[p]; A[p]=v;

interchangeP(m,p); interchangeW(m,p); return p; }

void quicksort(int p,int q) //快速分类（本算法为递归算法） //将全局数组A(1:n)中的元素A[p],.....,A[q]按递减的方式分类{ int j; if(p

j=partition(p,j); quicksort(p,j-1); quicksort(j+1,q); } }

12

void greedy_knapsa(int m)//背包问题的贪心算法

/*P(1:n)和W(1:n)分别含有按P[i]/W[i]>=P[i+1]/W[i+1]排序的n件物品的效益值和容量。 X(1:n)是解向量，m存放背包的容量，物品存放入背包有三种情况：未放、部分放入和全 部放入 */

{ int cu,i; //cu用于存放背包的剩余容量 for(i=1;i<=n;i++) //将解向量初始化为0 X[n]=0; cu=m;

for(i=1;i<=n;i++) //存放物品 { if(W[i]>cu)break; X[i]=1; cu-=W[i]; }

if(i<=n)X[i]=(float)cu/W[i]; }

void main() { int i,M;

printf(\

scanf(\ //输入物品数目 printf(\

scanf(\ //输入背包容量 printf(\

for(i=1;i<=n;i++) //输入各物品的效益值 scanf(\ printf(\

for(i=1;i<=n;i++) //输入各物品的容量 scanf(\

for(i=1;i<=n;i++) //A[i]存放第i个物品的单位容量的效益增量 A[i]=(float)P[i]/W[i];

quicksort(1,n); //将效益集合和容量集合按物品单位容量的效益增量降序进行排序 greedy_knapsa(M); //执行贪心算法求出解向量 printf(\

for(i=1;i<=n;i++) //输出解向量 printf(\ printf(\}

运行结果如下图所示：(运行结果与理论结果一致)

13

五、结果分析

运行源程序后，先输入物品的数量，回车，再输入背包的容量，回车，然后依次输入各物品的效益值，回车，最后对应输入各物品的容量，回车，就会得到解向量（各物品存放情况，此时物品的顺序不一定与初始时一样）。不难看出，运行结果与理论值一致。

将物体事先按Pi/Wi的非增次序分好类，若物品分类的时间不算在内，则此算法所用时间为O（n）。

上机实验四

一、实验题目

贪心方法求带有限期的作业排序

二、算法介绍

度量标准的选择

pi作为量度。 以目标函数 i?J 量度标准：下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下得到最大增加的作业。

处理规则：按pi的非增次序来考虑这些作业。

?三、程序流程图 四、源程序及实验结果

#include #define N 8 typedef struct {

int p; int d; }job;

job j1[N]={{0,0},{35,4},{30,2},{25,4},{20,3},{15,4},{10,8},{5,3}};

void back(job *ps,int m,int n) {

int i;

for(i=n;i>=m;i--)

14

{

ps[i+1].p=ps[i].p; ps[i+1].d=ps[i].d; } }

void main() {

int t,t1,i,m;//t为所用时间,t1为预计时间 job j[N];

printf(\输出待处理的作业：效益值,截止期限\ printf(\ for(i=1;i

printf(\ printf(\ }

//初始化

j[0].p=j1[0].p; j[0].d=j1[0].d;

j[1].p=j1[1].p; j[1].d=j1[1].d; t=1;

for(i=2;i

t1=t+1;

if(j1[i].d>=t1 || j[i-1].d>=t1) {

m=1;

while(m<=t) {

if(j1[i].d

back(j,m,t); j[m].p=j1[i].p; j[m].d=j1[i].d; break; }else m++;

15

}

if(m>t) {

j[t1].p=j1[i].p; j[t1].d=j1[i].d; }

t=t1; }else t1--; }

printf(\输出得到的结果：效益值,截止期限\ printf(\ for(i=1;i<=t;i++) {

printf(\ printf(\ } }

运行结果如下图所示：(运行结果与理论结果一致)

五、结果分析

将待作业的信息直接放入程序中，并显示。运行源程序后，直接得到可行解的效益值与截止期限。不难看出，运行结果与理论值一致。

设s是最终计入J中的作业数，则算法JS所需要的总时间是O(sn)。s≤n，故 最坏情况：TJS = О(n2)，特例情况：pi=di=n-i+1,1≤i≤n； 最好情况：TJS = О(n)，特例情况：di=i,1≤i≤n。

16

上机实验五

一、实验题目

贪心方法求单源点的最短路径问题

二、算法介绍

1、限定有向图中所有的权都是正的；

2、逐条构造所求最短路径，量度标准是使用迄今已生成的所有路径长度之和，单独的每一条路径都必须具有最小长度，按照路径长度的非降次序生成从源点（起始结点）到所有其它结点的最短路径。

三、程序流程图

说明：集合S表示对其已经生成了最短路径的那些结点（包括起始结点V0）的集合； cost[][]（是全局变量）中存放各结点之间的直接距离并规定无穷大为1024，表示两结点之间不可直达，cost[i][i]表示结点Vi与Vi的距离，规定其值为0。

四、源程序及实验结果

程序代码如下： #include #include

/*二维数组cost[6][6]存放的是一个有向图中各个结点的直接距离，其中从i到j不能直接到 达时它们的距离为无穷大，用1024表示 */

int cost[6][6]={ {0,50,10,1024,45,1024}, {1024,0,15,1024,10,1024}, {20,1024,0,15,1024,1024}, {1024,20,1024,0,35,1024}, {1024,1024,1024,30,0,1024}, {1024,1024,1024,3,1024,0}};

int min(int a,int b) //求a与b的最小值并返回该值 { if(a>b)a=b; return a; }

void shortest_paths(int v) { int u,num,i,w,tmin;

int dist[6]; //数组dist[i]中存放的是起始节点v与结点Vi的路径长度

int S[6]; //S[i]是结点Vi加入集合S的情况，不在S中时为0，在时为1 int n=6;

for(i=0;i

dist[i]=cost[v][i];

17

}

printf(\输出v到所有结点的直接距离：\\n\

for(i=0;i

S[v]=1; //将起始结点v加入集合S中 dist[v]=0; //结点v到v的路径长度为0

for(num=1;num<=n-1;num++) //确定由结点v出发的n-1条路 { i=0;

while(S[i]==1) //找到一个不在集合S中的结点 { i++; }

tmin=i; //tmin存放的是dist[i]值最小的结点下标i,默认初值为前面找到的

不在集合S中的结点的下标

for(i=0;i

if(S[i]==1)continue;

else if(dist[i]

u=tmin; //将不在集合S中且dist[i]值最小的结点的下标记入u中 S[u]=1; //将结点Vtmin记入集合S中

for(w=0;w

dist[w]=min(dist[w],dist[u]+cost[u][w]); } }

printf(\输出所有结点加入集合S[]的情况:\\n\ for(i=0;i

{ printf(\ }

printf(\分别输出v与各结点的最短路径长度:\\n\ for(i=0;i

{ printf(\ }

printf(\}

void main() { int v; char c;

18

do

{ c=getchar(); //输入起始结点的下标值 v=c-'0';

if(v>=0&&v<6) //当所输下标合法时求从该结点到所有结点（包括该结点）的路径长度 { shortest_paths(v); c=getchar(); }

else break; //当所输下标不合法时结束 }while(c=='\\n'); }

运行结果如下：(运行结果与理论结果一致)

五、结果分析

运行源程序后，输入起始结点v的下标，回车，就会输出v到所有结点的直接距离，以及各结点加入集合S的情况，和v到各结点的最短路径长度。不难看出，运行结果与理论值一致。

由于任何一条边都有可能是最短路径中的边，所以求任何最短路径的算法都必须至少检查图中的每条边一次，所以这样的算法的最小时间是О(e)。

上机实验六

一、实验题目

动态规划求有向图最短路径 二、算法介绍

考察i到j的最短路径：首先确定哪个节点是该路径上具有最大编号的中间结点k，计算由i、j分别到k的最短路径，这2条路径都不可能有比k-1还大的中间节点。求解递推；用Ak（i，j）表示从i到j且不经过比k还大的结点的最短路径长度，由于G中不存在比n

19

还大的结点，因此A（i，j）=An（i，j），即由i到j的最短路径上不通过比n标号还大的结点。这条路径可能通过结点n也可能不通过节点n，如果通过结点n则An（i，j）=An-1（i，n）+An-1（n，j），如果不通过结点n，则An（i，j）=An-1（i，j）。组合起来得到

An（i，j）=min{An-1（i，j），An-1（i，n）+An-1（n，j）} 同理Ak（i，j）=min{Ak-1（i，j），Ak-1（i，k）+Ak-1（k，j）}，k》1.

简单的描述最短路径算法如下：

I 从某一点k开始，根据cost[n][n]（比较A(i,j)与A(i,k)+A(k,j)的大小）修改从i到j的最短路径值，若A(i,k)+A(k,j)

II. 重复1直到所有点均考虑完。

三、程序流程图

四、源程序及实验结果

#include #define N 10

#define INIFITY 1000

struct { int vexnum;//结点个数 int arcs[N][N];//邻接矩阵 }G;//图

void output (int a[N][N]) { int i, j;//循环参数 for (i=1; i

20

for (j=1; j 900) { printf (\输出无穷大标记 } else { printf (\依次输出邻接矩阵 } } printf (\ } printf (\}

void initialize () { FILE *fp;//文件指针 int i, j;//循环参数 fp = fopen (\数据.txt\ fscanf (fp, \.vexnum);//读入结点数 for (i=1; i

void all_path () { int temp[N][N];//临时存储矩阵 int i, j;//循环参数 int k;//循环尝试次数参数 for (i=1; i

21

} for (k=1; k

int main (void) { initialize ();//从文件中读取图的数据 all_path (); return 0; }

导入数据后的显示的结果：

处理后的最短路径：

22

23

五、结果分析

从数据文件中导入数据，并显示，如上图。用动态规划一步一步求取没对结点间的最短路径长度，并一一显示。

心得体会

通过这段时间的上机课，我对分治法、贪心方法、动态规划有了进一步的认识，通过用分治法实现归并分类和快速分类，用贪心方法解决背包问题和求单源点最短路径，让我学习到解决不同类型问题的两种方法，也让我认识到它们的区别，分治法用于解决将整个问题分成若干个小问题所得到的小问题均与原问题是相同类型的这类问题，而贪心方法用于求目标函数的最优解，这种方法是选取一种量度标准，对n个输入进行排序，求出的解是贪心解（不一定是最优解)。

在上机的过程中，我也在不断改变自己固有思维方式，像做贪心算法的过程中，做背包问题是没想过用结构体，结果就不是很有层次感。在室友的提醒下，在做带有权限的作业中，我尝试用了结构体，虽然加大了写程序的难度，但使得程序易于理解了。 存在问题：

通过此次上机，我发现自己普遍使用全局变量，所写的程序中各函数普遍依赖于全局变量，虽然使用全局变量可以简化模块之间的接口处理，但同时也导致模块的移植性或者说是独立性差，所以我觉得以后要注意慎用全局变量。

24

本文来源：https://www.bwwdw.com/article/y9h6.html