模拟卷1
单项选择题
点击选项选择正确答案，每题有且仅有一个正确答案 1、下列是动态规划法而不是分治法的基本要素的是 （ ） 算出最优解 构造最优解 子问题重叠性质 定义最优解 2、备忘录法是哪种算法的变形（ ） 动态规划 回溯法 贪心法 分治法 3、下列不是动态规划法基本步骤的是（ ） 构造最优解 算出最优解 找出最优解的性质 定义最优解 4、使用分治法求解不需要满足的条件是（ ） 子问题的解可以合并 原问题和子问题使用相同的方法解 子问题必须是一样的 子问题不能够重复 5、二分搜索算法是利用（ ）实现的算法。 贪心法 回溯法 动态规划法 分治策略判断正误题
根据题干描述，点击下方的「正确」或「错误」选项 1、减治法需要把每个子问题都计算一遍. 2、折半查找的时间复杂性是O(nlgn). 3、分治法和减治法都能计算a的n次幂,两者的时间复杂性也相同。 4、利用减治法解决问题时，要求子问题中蕴含原问题的解. 5、最优化原理也称最优性原理,是动态规划的基础。程序设计题
程序设计题需要你亲自编写代码完成作答， 通常需要读取特定输入并输出特定的结果。 请点击下方题目进入作答找零问题（贪心算法求启发解）
类型：简单循环
描述
假设有面值为 5元、2元、1元、5 角、2 角、1 角的货币，需要找给顾客n角现金，付款问题（payment problem）要求找到一个付款方案，本题要求：贪心算法求启发解，付出的货币张数是多少？（编程模板中有三处错误，请您改正。并思考如何用动态规划法求最优解？）
输入
一个非负整数，应找金额，单位为角。
输出
一个非负整数（货币张数）。
示例
输入
50
输出
1
输入
100
输出
2鸡兔同笼问题
类型：约束条件比经典鸡兔同笼问题宽松，无头的个数约束，直接模拟法。
描述
【问题】笼子里有若干只鸡和兔子，鸡有两只脚、兔子有四只脚，没有例外情况。已知笼子里脚的个数，问笼子里至多有多少只动物？至少有多少只动物？
【想法】对于同样数目的动物，鸡脚的总数肯定比兔子脚的总数要少，因此在计算笼子里至多有多少只动物时，应该把脚都算作鸡脚，在计算笼子里至少有多少只动物时，应该尽可能把脚都算作兔子脚。
输入
脚的个数(大于0的整数)
输出
至多有多少只动物，至少有多少只动物，其中兔子多少只。（输出中标点符号为中文，无需加换行符）
示例
输入
-111
输出
不合常理
输入
333
输出
不合常理
输入
6
输出
至多有3只动物，至少有2只动物，其中1只是兔子。
约瑟夫环问题
要点.模拟法，做好问题向符号的映射，然后按照题目描述的过程，在符号上进行操作。
描述
设 n(n>0)个人围成一个环，n 个人的编号分别为1，2，…，n，从第 1 个人开始报数，报到 m 时停止报数，报 m 的人出环，再从他的下一个人起重新报数，报到 m 时停止报数，报m的人出环，……，如此下去，直到所有人全部出环为止。对于任意给定 n 和 m，求 n 个人出环的次序。
输入
空格分隔的两个小于10000的非负整数，第一个表示人数，第二个表示需要报的数目。
输出
最后一个出环人的编号
示例
输入
5 3
输出
4二分检索折半减少搜索区间的过程（减治法）
展示二分检索折半减少搜索区间的过程.类型：减治法
描述
在编程模板中已经声明并初始化了大小为15的整型数组，数组元素的值为其索引值的十倍，请大家不要修改该数组。利用二分检索算法在该数组中查找系统给出的整型关键字k。以字符可视化的方式输出算法执行过程中以减半的速度缩小问题实例规模的过程（一次减半用一行字符表示）。
输入
一个整数（需要查找的关键字）。
输出
由英文半角问号"?”、大写“X"和英文半角感叹号“!"组成的字符矩阵，要求每行15个字符，每行结尾处含换行符。每个字符对应算法在数组r中的搜索行为："X"表示不可能存在关键字k的区域，"?"表示有可能找到关键字k的区域，而"!"表示找到的位置，如果没找到则最后一行只有15个X。
示例
输入
120
输出
XXXXXXXX???????
XXXXXXXXXXXX???
XXXXXXXXXXXX?XX
XXXXXXXXXXXX!XX
输入
12
输出
???????XXXXXXXX
???XXXXXXXXXXXX
XX?XXXXXXXXXXXX
XXXXXXXXXXXXXXX
输入
-80000
输出
???????XXXXXXXX
???XXXXXXXXXXXX
?XXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
连续或分数背包问题
类型：贪心法、简单循环
描述
已知有n种物品和一个可容纳C重量的背包，每种物品I的重量为wi，假定将物品i的某一部分xi放入背包就会得到vi*xi的效益(0≤xi≤1, vi>0) ，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？（物品可部分装入,背包剩余重量小于剩余物品总重量时必然某个物品需要被切割，输出被切割的物品编号。注意，编号从0开始，输出无需换行。）
输入
背包可容纳的重量C，非负整数。
输出
需要切割装入背包的物品编号。
示例
输入
5
输出
1
输入
15
输出
4网格上的最长路径
类型：动态规划、简单循环
描述
给定一个包含正整数的 m×n 网格，（为降低难度m=5,n=3,存储在数组dist[5][3]中。）每次只能向下或者向右移动一步，定义路径长度是路径上经过的整数之和。请找出一条从左上角(位置为(0,0))到位置(k,l)的路径，使得路径长度最大。（注意，是求最长路径！！！）
输入
空格分隔的两个非负整数，表示目的方格的行标k和列标l。
输出
从左上角(位置(0,0))到位置(k,l)的最长路径的长度。
示例
输入
4 2
输出
396
输入
2 2
输出
253
八皇后问题
类型：函数、简单循环
描述
八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。对于某个满足满足要求的八皇后的摆放方法，定义一个皇后串X与之对应，即X=X1X2X3X4X5X6X7X8，其中Xi(1<=Xi<=8)为相应摆法中第i(1<=Xi<=8)行皇后所处的列数。有人用图论的方法解出92种结果，本题要求采用DFS算法求出第n个皇后串。皇后串的比较是这样的：皇后串X在皇后串Y之前，当且仅当将X视为整数时比Y小。
输入
一个正整数n，即第n个皇后串（1<=n<=92)。
输出
第n个皇后串(八位整数，无换行)。
示例
输入
1
输出
15863724
输入
92
输出
84136275