为什么有字数限制呢~~哎~~好麻烦~~ 一、 设数组A有n个元素，需要找出其中的最大最小值。（20分）1.请给出一个解决方法，并分析其复杂性。2.。把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。 答：（1）基本思想：从头到尾逐个扫描，纪录最大和最小元素。输入：具有n个元素的数组。输出：最大值和最小值。步骤： void FindMaxMin(int A[], int n, int max, int min) { max=min=A[0]; for (i=1;i
max) max=A[i];if (A[i] int BinarySearch(Type a[], const Type& x, int L, int R){ while (R >= L){ int m = (L+R)/2; if (x == a[m]) return m; if (x < a[m]) R = m-1; else L = m+1; } return -1;} 5. .掌握动态规划算法的基本要素：（1）最优子结构性质；（2）重叠子问题性质。 6.掌握
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 7.掌握贪心算法的基本要素 （1）最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 （2）贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 8. 理解贪心算法与动态规划算法的差异：贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 9. 贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 10.子集树：当所给问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间数。排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树。 11. 常见的两种分支限界法的算法框架 （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中
规定
关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定
的优先级选取优先级最高的节点成为当前扩展节点。 12.分支限界法与回溯法：（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 13. 四种随机化算法的特点和区别：数值随机化算法的设计思想(近似解) ；蒙特卡罗算法的设计思想(能求得一个解,但未必正确)；拉斯维加斯算法的设计思想(若能得到一个解,必正确,但未必能找到)；舍伍德算法的设计思想(必能求得一个正确解)。
浙公网安备 33021202002483