能力说明:
了解变量作用域、Java类的结构,能够创建带main方法可执行的java应用,从命令行运行java程序;能够使用Java基本数据类型、运算符和控制结构、数组、循环结构书写和运行简单的Java程序。
爱技术也爱生活
给定n种物品(每种物品只有一件)和一个背包:物品i的重量是wi,其价值 为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物 品的总价值最大? 对于每种物品,只有两种选择:装(1)或者不装(0),不允许装物品的一部分
完全加括号的矩阵连乘积可递归地定义为: • 单个矩阵是完全加括号的 • 矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的矩阵连乘积B和C 的乘积并加括号,即A=(BC) 设有四个矩阵A, B, C, D ,它们的维数分别是: A = 50*10 B = 10*40 C = 40*30 D = 30*5 总共有五种完全加括号的方式:
输入母串的长度 循环输入母串数组以及母串的状态数组并初始化 外层循环,从左往右遍历,记录待更新数组为a[i] 里层循环,遍历母串的左闭右开区间[0,i),找到比a[i]小且状态值最大的数,更新a[i]的状态数组b[i] 用一个变量max记录状态数组b[i]的最大值就是最大子序列的数量
输入一个整型数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,-4,7,2,因此输出为该子数组的和18。
动态规划是将多阶段决策问题进行公式化的一种技术,它是运筹学的一个分支, 用于求解多阶段决策过程的最优化问题 动态规划方程又称为贝尔曼方程
对于一个规模为n的问题, 1. 若该问题可以容易地解决(比如说规模n较小)则直接解决, 2. 否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同, 3. 递归地解这些子问题, 4. 然后将各子问题的解合并得到原问题的解。 这种算法设计策略叫做分治法。
根据n和m的关系,考虑一下几种情况: (一)当n==1时,无论m的值为多少 ,只有一种划分,即{1} (二)当m==1 时,无论n的值为多少,只有一种划分,即1个n,{n} 。 (三)当n==m时,根据划分中是否包含n,可以分为以下两种情况: (1)划分中包含n的情况,只有一个,即 {n} (2)划分中不包含n的情况,这时划分中最大的数字也一定比n小,即n的所有(n-1)划分,即q(n,n-1)。 因此q(n,m)=1+q(n,n-1) (四)当n<m时,由于划分中不可能出现负数,因此就相当于q(n,n) (五)当n>m 时,根据划分中是否包含最大值m,可以分为以下两种情况:
使用递归编写一个程序实现汉诺塔问题,要求在输入圆盘数量之后,输出圆盘的移动步骤,输出格式示例如下: 第1步:1号盘从A柱移至B柱第2步:2号盘从A柱移至C柱
在调用一个函数的过程中又出现直接或间接调用该函数本身,称为函数的递 归(Recursion)调用,这种函数称为递归函数 • 若p函数定义中调用p函数,称之为直接递归 • 若p函数定义中调用q函数,而q函数定义中又调用p函数,称之为间接递归
算法(Algorithm)是指解决问题的方法或过程,它包含一系列步骤,用来将 输入数据转换成输出结果 算法具有以下性质: • 输入:有零个或多个输入 • 输出:至少有一个输出 • 确定性:组成算法的每条指令清晰、无歧义 • 有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限