实验一  递归与分治策略

一、实验目的

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<iostream.h>

#include<stdio.h> 

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<<"找到"<<endl;

else

       cout<<"找不到"<<endl;

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[j]。既不能将一个作业分开由两台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。研究一个实例:（a[1],a[2],a[3],a[4],a[5],a[6]）=(2, 5, 7, 10, 5, 2); (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<j<=n。设计一个算法，计算出游艇1到游艇n所需最少租金。

三、实验要求

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

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

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

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

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

2、对于给定的游艇出租站i到游艇出租站j之间的租金为r（i，j），1<=i<j<=n，计算出游艇1到游艇n所需最少租金。

五、实验结果分析

独立任务最优调度问题：

租用游艇问题：

时间复杂性：独立任务最优调度问题：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 + Math.Min(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] = Math.Max(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] = Math.Max(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);

            Console.WriteLine();

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

            {

                Console.WriteLine(" 按要求完成前{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<N，则加油次数k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；

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

五、实验结果分析

最优服务次序问题：

时间复杂度为O(nlogn)

汽车加油问题：

时间复杂度为O(n)。

六、实验体会

七、附录：（源代码）

汽车加油问题：

#include<iostream.h>

#include<stdio.h>

namespace ConsoleApplication1

{     

class Program    

{         

static void Main(string[] args)        

{             

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

int n = Convert.ToInt32(Console.ReadLine());            

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

int k = Convert.ToInt32(Console.ReadLine());            

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

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

Console.WriteLine("请输入加油站间距！");            

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

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

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

distance[i] = Convert.ToInt32(Console.ReadLine());            

}

 int count;//记录加油次数            

Problem p = new Problem();             

count = p.Greedy(distance, note, n);            

if (count >= 0)            

{                

if (count == 0)                     

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

else                

{                     

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

Console.WriteLine("分别在以下加油站加了油：");                    

for (int i = 0; i < note.Length; i++)                    

{                         

if (note[i] != 0)                        

{//输出需加油站点                              

Console.WriteLine("第" + note[i] + "个加油站！");                        

}                    

}                

}            

}            

else                 

Console.WriteLine("汽车无法到达终点！");            

Console.ReadKey();        

}    

}      

class Problem    

{         

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

{             

int i, j, s, add = 0, p = 0, k = d.Length;            

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<iostream>  

#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)  

         sum = cw;  

       return ;  

     }  

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

         cw+=w[i][j];  

         cp+=c[i][j];  

         if(cw<sum && cp<=d)  

           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<<sum<<endl;  

    system("pause");  

    return 0;  

}