免费智能真题库 > 历年试卷 > 软件设计师 > 2016年下半年 软件设计师 上午试卷 综合知识
  第65题      
  知识点:   动态规划法
  章/节:   计算机软件知识       

 
两个矩阵Am*n和Bn*p相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M(i+1),…,Mj多个矩阵连乘的最优顺序,即所需要的乘法次数最少。最少乘法次数用m[i,j]表示,其递归式定义为:

其中i、j和k为矩阵下标,矩阵序列中Mi的维度为(pi-1)*pi采用自底向上的方法实现该算法来确定n个矩阵相乘的顺序,其时间复杂度为(64)。若四个矩阵M1、 M2、M3、M4相乘的维度序列为2、6、3、10、3,采用上述算法求解,则乘法次数为(65)。
 
 
  A.  156
 
  B.  144
 
  C.  180
 
  D.  360
 
 
 

 
  第62题    2018年下半年  
   62%
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的..
  第64题    2016年下半年  
   68%
两个矩阵Am*n和Bn*p相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘..
  第62题    2022年下半年  
   29%
折半查找在有序数组A中查找特定的记录K:通过比较K和数组中的中间元素A[mid]进行,如果相等,则算法结束∶如果K小于[Amid],则对..
   知识点讲解    
   · 动态规划法
 
       动态规划法
               动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立的。
               动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解,每个解都对应于一个值,希望找到具有最优值(最大值或最小值)的那个解。当然,最优解可能会有多个,动态规划算法能找出其中的一个最优解。设计一个动态规划算法,通常可按照以下几个步骤进行。
               (1)找出最优解的性质,并刻画其结构特征。
               (2)递归地定义最优解的值。
               (3)以自底向上的方式计算出最优值。
               (4)根据计算最优值时得到的信息,构造一个最优解。
               对一个给定的问题,若其具有以下两个性质,则可以考虑用动态规划法来求解。
               (1)最优子结构。如果一个问题的最优解中包含其子问题的最优解,就说该问题具有最优子结构。当一个问题具有最优子结构时,表示动态规划法可能会适用,但是此时贪心策略可能也是适用的。
               (2)重叠子问题。它指用来解原问题的递归算法可反复地解同样的子问题,而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时,就说明该问题包含重叠子问题。此时若用分治法递归求解,则每次遇到子问题都会视为新问题,会极大地降低算法的效率,而动态规划法总是充分利用重叠子问题,对每个子问题仅计算一次,把解保存在一个在需要时就可以查看的表中,而每次查表的时间为常数。
   题号导航      2016年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第65题    在手机中做本题