2023年7月29日发(作者：)

实验一 递归与分治策略

一、实验目的

1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；

2．提高学生利用课堂所学知识解决实际问题的能力；

3．提高学生综合应用所学知识解决实际问题的能力。

二、实验内容

1、

①设a[0:n-1]是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

②写出三分搜索法的程序。

三、实验要求

（1）用分治法求解上面两个问题；

（2）再选择自己熟悉的其它方法求解本问题；

（3）上机实现所设计的所有算法；

四、实验过程设计（算法设计过程）

1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。

2、将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。如果x>a[2(n-1)/3]，则只需在数组a的右三分之一部分中继续搜索x。上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。

五、实验结果分析

二分搜索法：

三分搜索法：

时间复杂性：

二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。（n代表集合中元素的个数）

三分搜索法：O（3log3n）

空间复杂度：O（1）。

六、实验体会

本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。

七、附录：（源代码）

二分搜索法：

#include

#include

int binarySearch(int a[],int x,int n)

{

int left=0;int right=n-1;int i,j;

while(left<=right)

{

int middle=(left+right)/2;

if(x==a[middle]){i=j=middle;return 1;}

if(x>a[middle])left=middle+1;

else right=middle-1;

}

i=right;j=left;

return 0;

}

int main()

{ int a[10]={0,1,2,3,4,5,6,7,8,9};

int n=10;

int x=9;

if(binarySearch(a,x,n))

cout<<"找到"<

else

cout<<"找不到"<

return 0;

}

实验二 动态规划——求解最优问题

一、实验目的

1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；

2．提高学生利用课堂所学知识解决实际问题的能力；

3．提高学生综合应用所学知识解决实际问题的能力。

二、实验内容

1、用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是a[i]，若由机器B来处理，则所需要的时间是b[i]。由于各作业的特点和机器的性能关系，很可能对于某些i，有a[i]>=b[i]，而对于某些就j，j!=i,有a[i]

(b[1],b[2],b[3],b[4],b[5],b[6])= (3, 8, 4, 11, 3, 4)。

2、长江游艇俱乐部在长江上设置了n个游艇出租站1，2„„n。游客可在游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金r（i，j）1<=i

三、实验要求

（1）用动态规划思想求解最优问题；

（2）再选择自己熟悉的程序设计语言实现所有算法；

（3）分析所设计的算法的时间/空间复杂性。

四、实验过程设计（算法设计过程）

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

2、对于给定的游艇出租站i到游艇出租站j之间的租金为r（i，j），1<=i

五、实验结果分析

独立任务最优调度问题：

租用游艇问题：

时间复杂性：独立任务最优调度问题：O(n*Sum)

六、实验体会

对于算法来说，没有最好，只有更好，算法的结果不一定是最佳答案，但至少是最接近最佳答案的。在权衡算法时间复杂度和空间复杂度的情况下，找到一个在时间和空间都能接受的算法才是上上之策。

七、附录：（源代码）

独立任务最优调度问题：

using System;

namespace zydd

{

class Program

{

static void DlrwZydd(int[] a, int[] b, int n, int[] least, string[] result)

{

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

{

least[i] = 99;

}

int aSum = 0, bSum = 0;

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

{

aSum += a[i];

bSum += b[i];

}

int Sum = 1 + (aSum, bSum);

int[,] timeA = new int[n, Sum];

int[,] timeB = new int[n, Sum];

int[,] timeMax = new int[n, Sum];

char[,] who = new char[n, Sum];

char[] tempRlt = new char[n];

for (int i = 0; i <= a[0]; i++)

{

timeA[0, i] = i;

if (i < a[0])

{

timeB[0, i] = b[0];

who[0, i] = 'b';

}

else

{

timeB[0, i] = 0;

who[0, i] = 'a';

}

timeMax[0, i] = (timeA[0, i], timeB[0, i]);

}

if (a[0] <= b[0])

{

least[0] = a[0];

tempRlt[0] = 'a';

}

else

{

least[0] = b[0];

tempRlt[0] = 'b';

}

result[0] = new String(tempRlt);

for (int k = 1; k < n; k++)

{

int tempSum = 0;

for (int temp = 0; temp <= k; temp++)

{

tempSum += a[temp];

}

for (int i = 0; i <= tempSum; i++)

{ timeA[k, i] = i;

if (i < a[k])

{

timeB[k, i] = timeB[k - 1, i] + b[k];

who[k, i] = 'b';

}

else

{

if ((timeB[k - 1, i] + b[k]) <= timeB[k - 1, i - a[k]])

{

timeB[k, i] = timeB[k - 1, i] + b[k];

who[k, i] = 'b';

}

else

{

timeB[k, i] = timeB[k - 1, i - a[k]];

who[k, i] = 'a';

}

}

timeMax[k, i] = (timeA[k, i], timeB[k, i]);

}

for (int i = tempSum + 1; i < aSum; i++)

{

timeA[k, i] = tempSum;

timeB[k, i] = 0;

}

int flag = 0;

for (int i = 0; i <= tempSum; i++)

{

if (timeMax[k, i] > 0 && timeMax[k, i] < least[k])

{

least[k] = timeMax[k, i];

flag = i;

}

}

tempRlt[k] = who[k, flag];

for (int i = k; i > 0 && flag > 0; i--)

{

if (tempRlt[i] == 'a')

{

flag -= a[i];

tempRlt[i - 1] = who[i - 1, flag];

}

if (tempRlt[i] == 'b')

{

tempRlt[i - 1] = who[i - 1, flag];

}

}

result[k] = new String(tempRlt);

}

}

static void Main(string[] args)

{

const int N = 6;

int[] a = new int[N] { 2, 5, 7, 10, 5, 2 };

int[] b = new int[N] { 3, 8, 4, 11, 3, 4 };

int[] least = new int[N];

string[] result = new string[N];

DlrwZydd(a, b, N, least, result);

ine();

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

{

ine(" 按要求完成前{0}项任务的机器顺序为：" + result[i] +

" 时间为：{1}" ,i+1,least[i]);

}

}

}

}

实验三 贪心算法

一、实验目的

1．进一步理解算法设计的基本步骤及各步的主要内容、基本要求

2．加深对贪婪法算法设计方法的理解与应用

3．掌握将算法转化为计算机上机程序的方法

4．培养学生应用所学知识解决实际问题的能力。

二、实验内容

1、设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti，1<=i<=n。应如何安排n个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是每个顾客等待服务时间的综合。

2、一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，之处应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。

三、实验要求

（1）设计用贪婪法求解“最优服务次序问题”及“汽车加油问题”的算法；

（2）上机实现所设计的算法；

（3）分析所设计的算法的时间/空间复杂性。

四、实验过程设计（算法设计过程）

1、首先将每个顾客所需要的服务时间从小到大排序。然后申请2个数组：st[]是服务数组，st[j]为第j个队列上的某一个顾客的等待时间；su[]是求和数组，su[j]的值为第j个队列上所有顾客的等待时间；

2、设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3„„n

1.始点到终点的距离小于Ｎ，则加油次数k=0；

2.始点到终点的距离大于N，

① 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n；

② 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点；

③ 加油站间的距离相等，即ａ[i]=a[j]=L

④ 加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过下面的算法求解。

五、实验结果分析

最优服务次序问题：

时间复杂度为O(nlogn)

汽车加油问题：

时间复杂度为O(n)。

六、实验体会

七、附录：（源代码）

汽车加油问题：

#include

#include

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

("请输入汽车加满油后可行驶路程： ");

int n = 32(ne());

("请输入途经加油站总数： ");

int k = 32(ne());

int[] distance = new int[k + 1];//加油站间距

int[] note = new int[k];//记录加油站点

ine("请输入加油站间距！");

for (int i = 0; i <= k; i++)

{//从始点起，加油站间距

("站点间距{0}: ", i + 1);

distance[i] = 32(ne());

}

int count;//记录加油次数

Problem p = new Problem();

count = (distance, note, n);

if (count >= 0)

{

if (count == 0)

ine("汽车不用加油就可到达终点！");

else

{

ine("汽车在旅途中需加{0}次油！", count);

ine("分别在以下加油站加了油：");

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

{

if (note[i] != 0)

{//输出需加油站点

ine("第" + note[i] + "个加油站！");

}

}

}

}

else

ine("汽车无法到达终点！");

y();

}

}

class Problem

{

public int Greedy(int[] d, int[] note, int n)

{

int i, j, s, add = 0, p = 0, k = ;

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

{

if (d[i] > n)

{//不能到达目的地

return -1;

}

}

for (j = 0, s = 0; j < k; j++)

{

s += d[j];

if (s > n)

{//需要加油

add++;

note[p++] = j;

s = d[j];

}

}

return add;

}

}

}

实验四 回溯法

一、实验目的

1．掌握能用回溯法求解的问题应满足的条件；

2．加深对回溯法算法设计方法的理解与应用；

3．锻炼学生对程序跟踪调试能力；

4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

二、实验内容

1、设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设w[i][j]是从供应商j处购得的部件i的重量，c[i][j]是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。

2、设有n 件工作分配给n 个人。将工作i 分配给第j 个人所需的费用为c[i][j]。试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用达到最小。

三、实验要求

（1）用回溯法算法设计方法求解最小重量机器设计问题和工作分配问题；

（2）上机实现所设计的算法；

（3）分析所设计的算法的时间/空间复杂性。

四、实验过程设计（算法设计过程）

1、a.部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。

b.用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。

① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。

② 若cw>=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。

③ 若i>n，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行；

④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。

c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。

2、a. 用c[i][j]存储将工作i分配给第j个人所需的费用，用v[j] 标记第j个人是否已分

配工作；

b. 用递归函数backtrack （i， total）来实现回溯法搜索排列树（形式参数i表示递归深

度，n用来控制递归深度，形式参数total表示当前总费用，s表示当前最优总费用）：

① 若total>=s，则不是最优解，剪去相应子树，返回到i-1层继续执行；

② 若i >n，则算法搜索到一个叶结点，用s对最优解进行记录，返回到i-1层

继续执行；

③ 采用for循环针对n个人对工作i进行分配（1≤j≤n）：

1> 若v[j]==1 ，则第j个人已分配了工作，找第j+1个人进行分配；

2> 若v[j]==0，则将工作i分配给第j个人（即v[j]=1 ），对工作i+1调用递归函数backtrack（i+1，total+c[i][j]）继续进行分配；

3> 函数backtrack（i+1，total+c[i][j]）调用结束后则返回v[j]=0，将工作i对

第j+1个人进行分配；

4> 当j>n时，for循环结束；

④ 当i=1时，若已测试完c[i][j]的所有可选值，外层调用就全部结束；

c. 主函数调用一次backtrack（1，0）即可完成整个回溯搜索过程，最终得到的s即为

所求最小总费用。

五、实验结果分析

最小重量机器设计问题：

程序中最大的循环出现在递归函数backtrack(i)中，而此函数遍历排列树的时间复杂度为O(n!),故该算法的时间复杂度为O(n!)。

工作分配问题：

递归函数backtrack（i，total）遍历排列树的时间复杂度为O（n！），主函数调用递归函

数backtrack（1，0），故该算法的时间复杂度为O（n！）。

六、实验体会

七、附录：（源代码）

最小重量机器设计问题：

#include

#define N 1000

using namespace std;

int n,m,d,cp=0,cw=0,sum=0;

int c[N][N],w[N][N];

void backtrack(int i){

if(i>n){

if(cw

sum = cw;

return ;

}

for(int j=1;j<=m;j++){

cw+=w[i][j];

cp+=c[i][j];

if(cw

backtrack(i+1);

cw-=w[i][j];

cp-=c[i][j];

}

}

int main(){

cin>>n>>m>>d;

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

for(int j=1;j<=m;j++)

cin>>c[i][j];

sum+=c[i][1];

}

for(int k=1;k<=n;k++)

for(int j=1;j<=m;j++)

cin>>w[k][j];

backtrack(1);

cout<

system("pause");

return 0;

}