免费智能真题库 > 历年试卷 > 软件设计师 > 2019年下半年 软件设计师 下午试卷 案例
  第4题      
  知识点：   常量   递归式   数组   常量和变量   结构性   问题定义

 
【说明】
0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1...i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。
0-1背包问题具有最优子结构性质。定义c[i][T]为最优装包方案所获得的最大价值，则可得到如下所示的递归式。

【c代码】
下面是算法的C语言实现。
(1)常量和变量说明
T: 背包容量
v[]:价值数组
w[]:重量数组
c[][]:c[i][j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值

(2) C程序
本人将不方便阅读的图片梳理成文字

#include <stdio.h>
#include <math.h>
#define N 6
#define maxT 1000
int c[N][maxT]={0};

int Memoized_Knapsack(int v[N],int w[N],int T) {
int i;
int j;
for(i=0; i<N; j++){
for(j=0; j<=T; j++){
c[i][f]= -1;
}
}
return Calculate_Max_Value(v, w, N-1, T);
}

int Calculate_Max_Value(int v[N],int w[N], int i, int j){
int temp =0;
if (c[i][j]!=-1){
(1)
}
if (i==0||j==0){
c[i][j]=0;
}else{
c[i][j]=Calculate_Max_Value(v, w, i-1, j);
if( (2) ){
temp=(3);
if(c[i][j]<temp){
(4)
}
}
}
return c [i][j];
}
 
问题：4.1   根据说明和C代码，填充C代码中的空(1)~(4)。
 
问题：4.2   根据说明和C代码，算法采用了 (5) 设计策略。在求解过程中，采用了（6）(自底向上或者自顶向下)的方式。
 
问题：4.3   若5项物品的价值数组和重量数组分别为v[]= {0,1,6,18,22,28}和w[]= {0,1,2,5,6,7}背包容量为T=11,则获得的最大价值为 (7) 。
 
 
 

   知识点讲解    
   · 常量    · 递归式    · 数组    · 常量和变量    · 结构性    · 问题定义
 
       常量
        与C语言不同，使用final关键字，C++语言则是const，如final float pi=3.14f、 final byte c=12。浮点常数后面要加"f"，如12.7f、 1.02f。
 
       递归式
        从算法的结构上看，算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单，本小节主要讨论递归算法的时间复杂度分析方法。
        （1）展开法。将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直至得到一个求和表达式及其结果。
        （2）代换法。这一名称来源于当归纳假设用较小值时，用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤：猜测解的形式；用数学归纳法找出使解真正有效的常数。
        （3）递归树法。递归树法弥补了代换法猜测困难的缺点，它适于提供"好"的猜测，然后用代换法证明。在递归树中，每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时，递归树的方法尤其有用。
        （4）主方法。也称为主定理，给出求解以下形式的递归式的快速方法，即
        T(n)=aT(n/b)+f(n)
        式中，a≥1和b>1是常数；f(n)是一个渐进的正函数。
 
       数组
               数组的定义及基本运算
               n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。
               对数组进行的基本运算有以下两种。
               （1）给定一组下标，存取相应的数据元素。
               （2）给定一组下标，修改相应的数据元素中某个数据项的值。
               数组的顺序存储
               一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((i-1)n+(j-1))L
               同样的，以列为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((j-1)m+(i-1))L
 
       常量和变量
        按照程序运行时数据的值能否改变，将程序中的数据分为常量和变量。程序中的数据对象可以具有左值和（或）右值，左值指存储单元（或地址、容器），右值是值（或内容）。变量具有左值和右值，在程序运行过程中其右值可以改变；常量只有右值，在程序运行过程中其右值不能改变。
 
       结构性
        界面设计应该有结构和层次，避免在同一个界面上堆积过多内容。使用不同的界面安排不同的知识，可突出不同的分主题，有利于用户快速理解和接收界面所包含的内容。
 
       问题定义
        软件系统的目的是为了解决问题，因此在建模之初最重要的步骤是问题的分析与定义，并在此基础上归结模型，这样才能够获得切实有效的模型。定义问题的过程包括理解真实世界中的问题和用户的需要，并提出满足这些需要的解决方案的过程。问题分析的目标就是在开始开发之前对要解决的问题有一个更透彻的理解。为了达到这一目标，通常需要经过在问题定义上达成共识、理解问题的本质、确定项目干系人（stakeholders，风险承担着、涉众）、定义系统的界限、确定系统实现的约束这5个步骤。
        （1）在问题定义上达成共识。要检验大家是否在问题的定义上达成了共识，最简单的方法就是把问题写出来，看看是否能够获得大家的认可。而要使得这个过程更加有效，应该将问题用标准化的格式写出来。在问题定义上达成共识，就能够有效地将开发团队的理解与用户的需求形成一致，这样就能够使得整个系统的开发沿着合理的方向进展。
        （2）理解问题的本质。每一句描述都会夹杂着叙述者的个人理解和判断，因此透过表面深入本质，理解问题背后的问题，是在问题分析阶段的一个十分关键的任务。其中一种技术是“根本原因”分析，这是一种提示问题或其表象的根本原因的系统化方法。在实际的应用中，常使用因果鱼骨图和帕雷托图两种方法。
        （3）确定项目干系人。要想有效地解决问题，必须了解用户和其他相关的项目干系人（任何将从新系统或应用的实现中受到实质性影响的人）的需要。不同的项目干系人通常对问题有不同的看法和不同的需要，这些在解决问题时必须加以考虑。
        （4）定义系统的连界。系统的边界是指解决方案系统和现实世界之间的边界。在系统边界中，信息以输入和输出的形式流入系统并由系统流向系统外的用户，所有和系统的交互都是通过系统和外界的接口进行的。要描述系统的边界有两种方法：一种是结构化分析中的上下文范围图，另一种则是面向对象分析中的用例模型。
        （5）确定系统实现的约束。由于各种因素的存在，我们会对解决方案的选择进行一定的限制，称这种限制为约束。每条约束都将影响到最后的解决方案的形成，甚至会影响是否能够提出解决方案。在考虑约束时，首先应该考察到不同的约束源，其中包括进度、投资收益、人员、设备预算、环境、操作系统、数据库、主机和客户机系统、技术问题、行政问题、已有软件、公司总体战略和程序、工具和语言的选择、人员及其他资源限制等等。
        通过对问题进行细致周密的分析，就可以对其进行综合的定义。对于一个问题的完整定义，通常应包括目标、功能需求和非功能需求3个方面。
        （1）目标。目标是指构建系统的原因，它是最高层次的用户需求，是业务上的需要，而功能、性能需求则必须是以某种形式对该目标做出贡献。
        （2）功能。功能性需求是用来指明系统必须做的事情，只有这些行为的存在，才有系统存在的价值。功能需求应该源于业务需求，它只与问题域相关，与解决方案域无关。
        （3）非功能需求。非功能需求（性能）是系统必须具备的属性，这些属性可以看作是一些特征或属性，它们使产品具有吸引力、易用、快速或可靠。
   题号导航      2019年下半年 软件设计师 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
 
第4题    在手机中做本题