算法设计与分析

1.一辆汽车加满油后可行驶n公里。指出应在哪些加油站停靠加油，使沿途加油次数最少。阅读程序1，回答问题。

代码的输入和输出分别是什么？

数据输入：

n：表示汽车加满油后可行驶nkm

k：旅途中有k个加油站

k+1个整数：表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。

数据输出：最少加油次数和具体在哪几个加油站加油。 

（2）代码选用的数据结构是什么？

数组 

（3）代码选用的算法设计策略是？

如果要使用贪心算法解决问题，那么需要检查每一小段路程是否超过汽车满油量时的最大支撑路程。如果有超过的，那么汽车不可能走完这段路。否则，找到汽车满油量时的最大支撑路程范围内的最后一个加油站，加油后继续用此方法前进

2.阅读算法1，回答问题。

middle=(low+high)/2;  //计算middle值(查找范围的中间值)

                 //x大于s[middle]，则在后半部分查找    return BinarySearch(s,x,middle+1,high);

}

（1）算法1的功能是什么？（3分）

 二分搜索

请你设计至少4组输入，验证算法1的正确性。（4分）

[1,2,3],[1,3,3],[1,3,3],[1,333],[123321]

请改用自然语言描述算法1。（3分）

折半查找，每次减少一半范围，log2时间即可找到

3.阅读算法2，回答问题。

算法2：kn(int w[],int v[],int n,int C)//参数分别为物品重量、物品价值、物品数量、容量

   算法2设计策略是什么？（1分）

贪心策略：选择单位重量价值最大的物品

请根据算法2，写出递归关系式。

if(j>=w[i-1])

       dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i-1]])+v[i-1];

else dp[i][j]= dp[i+1][j];

4.阿里巴巴走进了装满宝藏的藏宝洞。请问阿里巴巴最多可以拿走多少价值的金币？

（1）请给出存储已知数据的数据结构数组

请给出你选择的算法策略

先将每堆金币按金币的价值重量比进行排序，越高的排在越前面，然后从前往后一堆一堆的放入背包，当背包装不下某一堆金币时，则取这堆金币的部分装入，使得装入的金币总重量等于背包的承重量即可。

5.游艇俱乐部在长江上设置了n个游艇出租站。求解从游艇出租站1到游艇出租站n所需的最少的租金。

（1）写出选用的算法策略（2分）。

动态规划算法

（2）写出该算法策略的思想（4分）。

【令dp[i]表示从站点1到站点i所需的最少租金

dp[1]=r[1][1]=0,dp[2]=r[1][2],

递推关系：dp[i]=min(dp[i],dp[j]+r[j]),1】

dp[i][j]表示第i个站点到第j个站点的最少租金。枚举2个站点的最少租金，3个站点的最少租金，…，n个站点的最少租金。状态转移方程：

写出求解问题所用的数据结构

数据结构：两个二维数组r[][]和dp[][]。

写出求解问题的算法步骤

void rent(){

        for(int d=3;d<=n;d++){//区间长度d

          for(int i=1;i<=n-d+1;i++){//状态起点i，终点j

            int j=i+d-1;

            for(int k=i+1;k<j;k++){//枚举决策点k 

                if(dp[i][j]>dp[i][k]+dp[k][j])

                    dp[i][j]=dp[i][k]+dp[k][j];

            }

          }

   }

}

（5）分析算法的时间复杂度和空间复杂度。时间复杂度：O(n3)，空间复杂度：O(n2)。

6.分析算法3的时间复杂度和空间复杂度。

        while(i<j && r[j]>pivot)  j--; //从右向左扫描

        if(i<j)

            swap(r[i++], r[j]);

        while(i<j && r[i]<=pivot)  i++; //从左向右扫描

时间复杂度O(n)和空间复杂度O(n)

7.请分析算法4的时间复杂度和空间复杂度，并给出一个更好的求解方法及求解步骤。

算法4： nQueens (int t)

                  nQueens(t+1);

           }

}

时间复杂度 O(n*2^n) 空间复杂度 O(n*n)

8.请分析算法5的时间复杂度和空间复杂度，并给出算法5的非递归算法。

算法5：

Def  backtrack( t){//地图着色问题

Global colors,x,sum1,n,m,a

if(t>n){ //到达叶子,找到一个着色方案

本算法运算时需要对每个点的每个邻接进行判断，为(2×e)次判断操作，及给没上色的点上色，有v次操作，一共(2×e)+v次操作，由于在着色问题当中，边数（所有邻接省份数）比点数（省份数）多，所以时间复杂度可认为是θ(v)。

运算时创建了一个额外的队列来记录待遍历的点，所以空间复杂度为(e)。

9.三个矩阵大小分别为3*4、4*5、5*6，求其相乘的最优结合次序。

（1）写出所用的求解方法（4分）

动态规划方法

描述该方法求解的步骤（4分）

定义一个二维数组m存储最少乘法次数，二维数组s存储最优决策并分别初始化为0;（1分）

按照区间长度(即j-i)升序的原则，依次采用下式计算所有的m[i][j]和s[i][j]：

m[i][j]=min{m[i][k]+m[k+1][j]+P[i-1]P[k]P[j]},i<=k<j （1分）

而s[i][j]设置为达到最小值的k值；（1分）

根据从s[1][n]开始,从s的值依次构造最优解（1分）

给出求解过程（4分）

区间长度为1: （2分）

m[1][2]=P[0]P[1]P[2]=3*4*5=60,s[1][2]=1;

m[2][3]=P[1]P[2]P[3]=4*5*6=120,s[1][2]=2;

区间长度为2：（2分）

m[1][3]=min(m[1][2]+P[0]P[2]P[3],m[2][3]+P[0]P[1]P[3])=min(150,192)=150,s[1][3]=2

（4）给出求解结果（2分）。 

构造解：根据s的值可知最优相乘次序为 (A1*A2)*A3（2分）。

1.阅读“算法1”，分析算法1的功能、时间复杂度。

功能：求解汉诺塔问题，将n个盘子从A塔，借助B塔，移动到C塔上。

时间复杂度：

T(n)=2T(n-1)+O(1)=4T(n-2)+2O(1)+O(1)=....=(2^n-1+2^n-2+...+1)O(1)=O(2^n)

2.阅读“算法2”，分析算法2的功能，设计算法的一个输入，并给出对应的算法输出结果。

功能：将arr中的整数按照由小到大的顺序排序，选择排序法

输入：arr=[6,24,3,21,25,4]

输出：3，4，6，21，24，25

3.“算法3”为回溯法求无向不带权图G的最大团问题的递归函数backtrack（），请您依据递归函数，写出该问题解的形式、解空间的组织结构和搜索条件。假设用邻接矩阵g[][]存储无向不带权图G。

解的形式：(x1,x2,...,xn),其中xi表示第i个顶点是否在最大团中，xi=0：表示不在最大团中，xi=1：表示在最大团中.

解空间组织结构：满二叉树，深度为n或n+1

搜索条件：约束条件：任何两个顶点之间都有边相连

限界条件：预估的当前节点的最大团的顶点个数上界cn+rn大于当前找到的最大团中的顶点个数bestn

约束函数：

def place(t):

    OK=True

    for j in range(t):

        if x[j] and a[t][j]==0:

            OK=False

            break

    return OK

4.阅读“算法4”，算法4中的time为结构体数据类型，定义了开始时间start_time和结束时间end_time两个数据项，请您设计一个n=6的实例，并给出算法4得到的x的值。

输入：（2，3），（1，2），（3，8），（1，6），（7，9），（5，7）

按照结束时间由小到大排序结果为：（1，2），（2，3），（1，6），（5，7），（3，8），（7，9）

输出x的值为（1，1，0，1，0，1）

5.阅读“算法5”，分析算法的功能，并给出一个例子，展示算法的运行过程。

算法5： MergeSort (int A[]，int low，int high)

              Merge(A,low,middle,high); //将两个有序子序列A[low:middle]、

A[middle+1:high]合并为一个有序序列

算法功能：合并排序，将一个无序序列按照由小到大的顺序排列

例子：3，8，2，10，8，90

过程：

分：【3，8，2】，【10，8，90】

分：【3，8】【2】

分【3】【8】

治：【3，8】

治【2，3，8】

分：【10，8】【9】

分：【10】【8】

治【8，10】

治【8，9，10】

治【2，3，8，8，9，10】

6.给定5种字符a,b,c,d,e及它们出现的频率0.45,0.25,0.15,0.10,0.05，选择一种编码方法，求这5个字符的编码方案。

（1）哈夫曼编码，把字符看作孤立的根节点组树的集合，依次从集合中选择两个频率最小的字符，组成左右子树构造一个新树，新树的频率是左右子树频率之和，然后把新树插入到树的集合中，一次重复，直到树集合只剩下一课树为止。把左子树赋值为1，右子树赋值为0，从根到叶子的路径就是对应叶子字符的编码。

（2）a:0,b:10,c:110;d:1111,e:1110

（3）平均码长为：1*0.45+2*0.25+3*0.15+4*0.10+4*0.05=2

7.定序列X={E,F,G,A, B,E}和Y={E,B, D, F,A, G}，求它们的最长公共子序列。

（1）动态规划法

（2）最优子结构性质分析，建立最优值的递归关系式，自底向上求最优值，构造最优解

（3） 0 0 0 0 0 0 0

         0 1 1 1 1 1 1

         0 1 1 1 2 2 2

         0 1 1 1 2 2 3

         0 1 1 1 2 3 3

         0 1 1 1 2 3 3

         0 1 1 1 2 3 3

（4）最长公共子序列为E,F,G

8.0-1背包问题：给定n个物品，1个背包，背包容量为W，n个物品的重量和价值分别为：(wi,vi)i=1,2,3,...,n。物品不能分割，请设计一算法，求解在不超过背包容量的前提下，怎么装能够使得装入的物品总价值最大。

（1）回溯法

（2）搜索思想：

从根开始，以深度优先搜索的方式进行搜索。

根结点是活结点并且是当前的扩展结点。在搜索的过程中，当前的扩展结点向纵深方向移向一个新结点，判断该新结点是否满足隐约束。

如果满足，则新结点成为活结点，并且成为当前的扩展结点，继续深一层的搜索；

如果不满足，则换该新结点的兄弟结点（扩展结点的其它分支）继续搜索；

如果新结点没有兄弟结点，或其兄弟结点已全部搜索完毕，则扩展结点成为死结点，搜索回溯到其父结点处继续进行。

搜索过程直到找到问题的解或根结点变成死结点为止。 

（3）将物品数据用三元组（编号，重量，价值），然后用顺序表存储物品，用顺序表存储n维0-1向量。

（4）

def bound(i):

    global c,curW,goods,curV,n#goods物品物品集合：物品编号、物品重量、物品价值

    cleft = c - curW

    b=curV;

    while(i<=n and goods[i][1]<=cleft):

        cleft -= goods[i][1]

        b +=goods[i][2]

        i +=1

    if(i<=n):

        b += goods[i][2]/goods[i][1]*cleft;

    return b

def backtrack(t):

    global bestV,curW,curV,x,bestx,n,goods#物品集：物品编号、物品重量、物品价值

    if t>=n:

        if bestV < curV:

            bestV = curV

            bestx = x[:]

    else:

        if curW + goods[t][1] <= c:

            x[goods[t][0]] = 1

            curW += goods[t][1]

            curV += goods[t][2]

            backtrack(t+1)

            curW -= goods[t][1]

            curV -= goods[t][2]

        if bound(t) > bestV:

            x[goods[t][0]]=0

            backtrack(t+1)

9.最优装载问题：给定n个箱子，其重量为wi（i=1,2,3,...,n)），某艘船的载重量为C，船的体积不受限制，在不超过船的载重量的前提下，设计一算法，将尽量多的箱子装到船上。

（1）回溯法

（2）搜索思想：

从根开始，以深度优先搜索的方式进行搜索。

根结点是活结点并且是当前的扩展结点。在搜索的过程中，当前的扩展结点向纵深方向移向一个新结点，判断该新结点是否满足隐约束。

如果满足，则新结点成为活结点，并且成为当前的扩展结点，继续深一层的搜索；

如果不满足，则换该新结点的兄弟结点（扩展结点的其它分支）继续搜索；

如果新结点没有兄弟结点，或其兄弟结点已全部搜索完毕，则扩展结点成为死结点，搜索回溯到其父结点处继续进行。

搜索过程直到找到问题的解或根结点变成死结点为止。 

（3）用顺序表w存储箱子重量，用顺序表x存储n维0-1向量。

（4）

def backtrack(t):

    if t>n:

        if bestn< curn:

            bestn = curn

            bestx = x[:]

    else:

        if curW + w[t] <= C:

            x[t] = 1

            backtrack(t+1)

        if curn+rn > bestn:

            x[t]=0

            backtrack(t+1)

最后

以上就是刻苦灰狼为你收集整理的算法设计与分析的全部内容，希望文章能够帮你解决算法设计与分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。