《信息安全数学考题》由会员分享，可在线阅读，更多相关《信息安全数学考题（9页珍藏版）》请在金锄头文库上搜索。
1、一 简答类 1 成立吗 证明你的答案 解 当时 故为 但不是或 2 是和的吗 证明你的答案 解 令 则当时 而 故为 3 已知操作S的执行时间为常数时间 请写出以下各段代码中S的执行 频度及其复杂性 for int i 0 i n i for int j i j n j S i j 解 T n n n 1 2 O n2 二 简单分析解题类 1 二分搜索问题 设是已排好序的数组 请改写二分搜索算法 使得当搜索元素x不在数 字中时 返回小于x的最大元素位置i和大于x的最小位置j 当搜索元 素在数字中时 i和j相同 均为x在数组中的位置 int left 0 int right n 1 int mi
2、ddle left right 2 while left right and a middle x if x a middle left middle 1 else right middle 1 middle left right 2 if left 1 q n m q n n m n q n n 1 q n n 1 q n m q n m 1 q n m m n m 1 总结 而p n q n n 3 已知一组连乘矩阵A0A1A2A3A4的行列数如下面p向量所示 请用动态 规划法求解最优计算顺序 写出计算过程以及加括号的计算顺序表达 式 P 5 3 9 2 2 4 参考答案 用表示所需的最少
3、乘法次数 递推方程为 对于P 5 3 9 2 2 4 其运行结果如下 0 1 2 3 4 0 0 135 84 96 136 K 0 K 0 K 0 K 3 1 0 54 66 90 K 1 K 2 K 3 2 0 36 88 K 2 K 2 3 0 16 K 3 4 0 A0 A1A2 A3 A4 4 已知正整数集A 2 3 5 9 目标值M 14 用回溯法求解A的所 有和等于M的子集 请画出状态空间树 并写出回溯求解的过程 不 需要写算法 参考答案 用数组X表示A中某元素是否被选入子集 其中X i 1表示A中第i个元素 被选中 X i 0表示A中第i个元素未被选中 以下的二叉解空间树中 左
4、分支表示X i 0 右分支表示X i 1 sa表 示已被选中的元素之和 su表示剩余元素的和 剪枝策略 在某结点处 sa suM sa 0 su 19 sa 0 su 17 2 sa 2 su 17 sa 0 su 14 3 sa 3 su 14 2 sa 2 su 14 2 3 sa 5 su 14 sa 0 su 9 5 sa 5 su 9 3 sa 3 su 9 3 5 sa 8 su 9 2 sa 2 su 9 2 5 sa 7 su 9 2 3 sa 5 su 9 2 3 5 sa 10 su 9 5 sa 5 su 0 5 9 sa 14 su 0 2 3 sa 5 su 0 2
5、3 9 sa 14 su 0 沿状态空间树深度优先搜索 在结点 sa 0 su 9 处 因sa su M 回溯 在结点 5 sa 5 su 0 处 因sa su M 回溯 在结点 5 9 sa 14 su 0 处 得解 在结点 3 sa 3 su 9 处 因sa suM 回溯 在结点 2 sa 2 su 9 处 因sa suM 回溯 在结点 2 3 sa 5 su 0 处 因sa suM 回溯 最后得解 5 9 2 3 9 三 分析设计类 1 用回溯法解决下列问题 给定n种物品和一个背包 物品的重量为 价值为 背包最多能装的物 品重量为C 每个物品可以选择装入背包或不装装入 但不可部分装 入
6、应如何选择装入各种物品 使得背包中物品的总价值最大 设计 算法解决此问题 并作出时间复杂性分析 解 解空间 子集树 可行性约束函数 搜索策略 在搜索解空间时 只要其左儿子是一个可行结点 搜索就 进入左子树 当右子树有可能包含最优解时才进入右子树所速 否则 将右子树剪去 设r是当前剩余物品价值总和 cp是当前价值 bestp 是当前最优价值 当cp r bestp时 可剪去右子树 计算右子树中 解的上界的最好方法是将剩余物品依其单位重量价值排序 然后依次 装入物品 直至装不下时 再装入该物品的一部分而装满背包 由此 得到的价值右子树中解的上界 以下为计算上界的函数 前提是物品 依其单位重量价值排
7、序 double bound int i 计算上界 double cleft c cw 剩余容量 double bound cp 以物品单位重量价值递减序装入物品 while i n bound p i i 装满背包 if i n bestp cp rerurn 达到叶结点 搜索左子树 if cw w i bestp backtrack i 1 进入右子树 return 2 用贪心法解决下列问题 给定n种物品和一个背包 物品的重量为 价值为 背包最多能装 的物品重量为C 每个物品可以部分装入背包 也可不装或全部装入 应如何选择装入各种物品 使得背包中物品的总价值最大 设计算法 解决此问题 并作
8、出时间复杂性分析 参考答案 可以使用贪心算法 算法如下 先将所有物品按其单位重量的价值进行排序 然后 按照贪心策 略 将尽可能多的单位重量价值最高的物品装入 若装入后 背包内的 物品总重量未超过C 则选择单位重量价值次高的物品尽可能多地装 入 依此策略一直进行下去 直到背包装满或物品装完为止 贪心性质证明 不失一般性 只要对第一个步骤进行证明即可 设按以上方法第一个步骤装入地重量为 对单位价值最大的物品 若存在一种装入方式 单位价值最大的物品装入数为 且得到了最优结 果 不妨设其他的物品被装入重量为 现对该方案作部分调整 将单位价值最高的物品的装入量改为 而将由 此产生的超重在后面的各物品上分
9、摊 减少 这样的方案获得的价值 必然超过原方案价值且不超重 与假设矛盾 故单位价值最大的物品的 装入数必然为 算法如下 背包容量C 物品个数n 数组d为物品 d i w为第i个物品的重 量 d i v为第i个物品的价值 x i 表示装入第i个物品的百分比 0 不装 1全装入 其他为部分装入 MergeSort mergeSort d 对d按照其单位重量的价值从大 到小进行排序 int i float opt 0 for i 0 i n i x i 0 for i 0 ic break 第i个物品不能全部装入 后续进 行部分装入处理 x d i i 1 全装入 opt d i v c d i w
10、 if i n 第i个物品不能全部装入 选中部分装入 x d i i c d i w opt x d i i d i v return opt 时间复杂性 除了进行的排序预处理 其他为单循环 时间花费为 而排序的时间消耗 若采用合并排序 为 故总的时间消耗为 3 最长递减子序列问题 解 设f i 表示L中以为末元素的最长递减增子序列的长度 则有如下 的递推方程 这个递推方程的意思是 在求以为末元素的最长递减子序列时 找到所 有序号在i前面且大于等于的元素 即j i且 如果这样的元素存在 那 么对所有 都有一个以为末元素的最长递减子序列的长度f j 把其中 最大的f j 选出来 那么f i 就等
11、于最大的f j 加上1 即以为末元素 的最长递减子序列 等于以使f j 最大的那个为末元素的递减子序列最 末再加上 如果这样的元素不存在 那么自身构成一个长度为1的以为 末元素的递减子序列 这个算法的伪代码如下 lis float L int n L length int f new int n 用于存放f i 值 f 0 1 以第a1为末元素的最长递减子序列长度为1 for int i 1 i n i 循环n 1次 f i 1 f i 的最小值为1 for int j 0 j L i 更新f i 的值 输出f中值最大的元素 这个算法有两层循环 外层循环次数为n 1次 内层循环次数为i次 时
12、间复杂度T n O n2 4 平面点集最短折线连接问题 给定平面上n 个点 要求把这些点连成一条折线 使得连成的折线 长度最短 请用回溯法设计解决此问题的算法 并分析算法的时间复 杂性 Proc Go K CS Nowcost K为递归深度 CS为未连接的点集 NowCost 为当前连线长度 Begin If Nowcost Mincost then MinCost为当前最优解的值 Return Else IF K N Then 全部点都已连入 说明已找到更优的解 保存当前连接方案 MinCost NowCost ELSE FOR I 1 TO N DO IF I IN CS THEN 将I记
13、录到当前连接方案中 IF K 1 THEN GO K 1 CS I NowCost 点I与连接方案中前一点之间的距 离 ELSE GO K 1 CS I NowCost 第一点没有前面的点 End 5 设某种货币系统为 1 5 10 25 四种币值 单位 元 要用最 少的币数找出n元钱 问 能否用贪心算法进行求解 并证明 解 贪心性质证明 对n25时 设n 1 a1 5 a2 10 a3 25 a4 为了使a1 a2 a3 a4最小 易知 a1 5 可将5个1元兑换为1个5元 币数减少 a2 2 可将2个5元兑换为1个10元 币数减少 当a2 0时 a3 3 可将3个10元兑换为1个5元和1个25元 币 数减少 当a2 0时 a3 2 可将1个5元和2个10元兑换为1个25元 币 数减少 即 为了使a1 a2 a3 a4最小 所使用的1 5 10元币的币数的上限 为 a1 4 a2 0 a3 2 或 a1 4 a2 1 a3 1 则所使用的1 5 10元币的币值上限为 4 1 0 5 2 10 24 或 4 1 1 5 1 10 19 均不超过25 因此 为了使a1 a2 a3 a4最小 应使a4达到最大 贪心 选择性质得证 最优子结构性质证明 当a4的值确定后 为了使a1 a2 a3 a4达到最小 须使a1 a2 a3达到最 小 且由穷举可知 仍为同型的最优问题
