实验内容

实验一：分治算法 循环赛日程表

一、实验目的与要求

1、掌握网球循环赛日程表的算法； 2、初步掌握分治算法 二、实验题：

问题描述：有n=2^k个运动员要进行循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1天

实验二：分治算法 邮局选址问题

一、实验目的与要求

1、掌握分治算法的基本原理

2、利用分治策略编程解决邮局选址问题 二、实验题：

[问题描述]

在一个按照东西和南北方向划分成规整街区的城市里，n 个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y 坐标表示南北向。各居民点的位置可以由坐标(x,y) 表示。街区中任意2 点(x1,y1) 和(x2,y2) 之间的距离可以用数值|x1-x2|+|y1-y2| 度量。

居民们希望在城市中选择建立邮局的最佳位置，使n 个居民点到邮局的距离总和最小。

给定n 个居民点的位置，编程计算n 个居民点到邮局的距离总和的最小值。

实验三：动态规划 最长公共子序列问题

一、实验目的与要求

1、明确子序列公共子序列的概念

2、最长公共子序列(Longest Common Subsequence,简称LCS) 的概念 3、利用动态规划解决最长公共子序列问题 二、实验题：

问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，?，xm-1”，序列Y=“y0，y1，?，yk-1”是X的子序列，存在X的一个严格递增下标序列，使得对所有的j=0，1，?，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。

给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。

实验四：动态规划 0-1背包问题

一、 实验目的与要求 1、明确0-1背包问题的概念

2、利用动态规划解决0-1背包问题问题 二、实验题：

0-1背包问题(knapsack problem)， 某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数, 背包的容量为W，W为一非负数。目标是如何选择装入背包的物品， 使装入背包的物品总价值最大，所选商品的一个可行解即所选商品的序列如何？背包问题与0-1背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分， 而不一定要选择物品的全部。可将这个问题形式描述如下：

约束条件为：

max?vxi1?i?ni?w1?i?nixi?W,xi?{0,1}举例: 若商店一共有5类商品，重量分别为：3，4，7，8，9

价值分别为：4，5，10，11，13

则：所选商品的最大价值为24

所选商品的一个序列为：0 0 0 1 1

实验五：贪心算法 背包问题

一、实验目的与要求

1、掌握背包问题的算法 2、初步掌握贪心算法 二、实验题：

问题描述：与0-1背包问题相似，给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。与0-1背包问题不同的是，在选择物品i装入背包时，背包问题的解决可以选择物品i的一部分，而不一定要全部装入背包，1< i < n。

实验六：作业调度问题

一、实验目的与要求

1、作业调度问题的算法 2、掌握贪心算法 二、实验题：

问题描述：要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。 [实验提示]

1)把作业按加工所用的时间从大到小排序；

2)如果作业数目比机器的数目少或相等，则直接把作业分配下去；

3)如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。

实验七：回溯法 装载问题

一、实验目的与要求

1、掌握装载问题的算法； 2、初步掌握回溯算法 二、实验题： 问题描述：

有两艘船，它们的可装载的货物重量分别为c1，c2，给定一批货物，其重量保存在数组w[i]中了，问这批货物能否用此两艘船送出。\\

实验八：分支限界法 最佳调度问题

一、实验目的与要求

1、掌握最佳调度问题的算法； 2、初步掌握分支限界法 二、实验题： 问题描述：

假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。

#include \ #include \ int aSize=0;

#include \ #include \

int Path(int X[],int Y[],int n) { int i,total=0,mid_X,mid_Y,*Q,*P; P=(int *)malloc(sizeof(int)*n); Q=(int *)malloc(sizeof(int)*n); if (n==1)return 0; else if(n==2)

return sqrt((X[1]-X[0])^2+(X[1]-Y[0])^2); else

{ for(i=0;i

{ P[i]=X[i];Q[i]=Y[i];} quitsort(X,0,n-1); quitsort(Y,0,n-1); mid_X=X[n/2]; mid_Y=Y[n/2]; for(i=0;i

{ /*total=total+sqrt((mid_X-P[i])*(mid_X-P[i])+(mid_Y-Q[i])*(mid_Y-Q[i])); */ total=total+(fabs(mid_X-P[i])+fabs(mid_Y-Q[i])); }

return total; }}

int quitsort(int L[],int s,int t) { int p,j=s,k=t; p=L[j]; while(j

{ while(j=L[j])j++; L[k]=L[j];} L[j]=p;

if(s

}

void main()

{ int *x,*y,n,add,i;

freopen(\ freopen(\ scanf(\

x=(int *)malloc(sizeof(int)*n); y=(int *)malloc(sizeof(int)*n);

for(i=0;i

#include #include #define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) { int i, j;

for(i = 0; i <= m; i++) c[i][0] = 0; for(j = 1; j <= n; j++) c[0][j] = 0; for(i = 1; i<= m; i++) {

for(j = 1; j <= n; j++) {

if(x[i-1] == y[j-1]) {

c[i][j] = c[i-1][j-1] + 1; b[i][j] = 0; }

else if(c[i-1][j] >= c[i][j-1]) {

c[i][j] = c[i-1][j]; b[i][j] = 1; }

else {

c[i][j] = c[i][j-1]; b[i][j] = -1; } } } }

void PrintLCS(int b[][MAXLEN], char *x, int i, int j) {

if(i == 0 || j == 0) return; if(b[i][j] == 0) {

PrintLCS(b, x, i-1, j-1); printf(\ }

else if(b[i][j] == 1) PrintLCS(b, x, i-1, j); else

PrintLCS(b, x, i, j-1); }

int main(int argc, char **argv) {

char x[MAXLEN] = {\ char y[MAXLEN] = {\ int b[MAXLEN][MAXLEN]; int c[MAXLEN][MAXLEN]; int m, n;

m = strlen(x);

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