算法设计与分析问答题每日一练(2019.11.25)

问答题
设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。
答案：
问答题
一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？
答案：按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解。
问答题
a.为一个分治算法编写伪代码，该算法求一个n个元素数组中最大元素的位置.b.如果数组中的若干个元素都具有最大值，该算法的输出是怎样的呢？c.建立该算法的键值比较次数的递推关系式并求解.d.请拿该算法与解同样问题的蛮力算法做一个比较
答案：
问答题
试述回溯法的基本思想及用回溯法解题的步骤。
答案：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含...
问答题
编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。
答案：