深圳网站建设伪静态 报价 jsp 语言,茶的网站制作,北京网站建设 案例,网站开发需要准备什么材料目录
简答题
计算题
时间复杂度的计算
递归算法计算
背包问题#xff08;0-1背包问题#xff09;
回溯法
动态规划法
编程题
用回溯法解方程
动态规划法解决蜘蛛吃蚊子
用分治法解决抛硬币问题
用二分法分两边求最大值 简答题 1、什么是算法#xff1f;算法有哪…目录
简答题
计算题
时间复杂度的计算
递归算法计算
背包问题0-1背包问题
回溯法
动态规划法
编程题
用回溯法解方程
动态规划法解决蜘蛛吃蚊子
用分治法解决抛硬币问题
用二分法分两边求最大值 简答题 1、什么是算法算法有哪些特征 算法是求解问题的一系列计算步骤。算法具有有限性、确定性、可行性、输入性和输出性。 2、什么是直接递归和间接递归消除递归一般要用什么数据结构 直接递归一个 f 函数定义中直接调用 f 函数自己。
间接递归一个 f 函数定义中调用 g 函数而 g 函数的定义中调用 f 函数。消除递归一般要用栈实现。 3、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 问题规模不同问题性质相同。 4、在寻找 n 个元素中第 k 小元素问题中如快速排序算法思想运用分治算法对 n个元素进行划分如何选择划分基准 随机选择一个元素作为划分基准、取子序列的第一个元素作为划分基准、用中位数的中位数方法寻找划分基准。 5、快速排序算法是根据分治策略来设计的简述其基本思想。 对于无序序列 a[low..high]进行快速排序整个排序为“大问题”。选择其中的一个基准 basea[i]通常以序列中第一个元素为基准将所有小于等于 base 的元素移动到它的前面所有大于等于 base 的元素移动到它的后面即将基准归位到 a[i]这样产生a[low..i-1]和 a[i1..high]两个无序序列它们的排序为“小问题”。当 a[low..high]序列只有一个元素或者为空时对应递归出口。
所以快速排序算法就是采用分治策略将一个“大问题”分解为两个“小问题”来求解。由于元素都是在 a 数组中其合并过程是自然产生的不需要特别设计。 6、假设含有 n 个元素的待排序的数据 a 恰好是递减排列的说明调用 QuickSort(a0n-1)递增排序的时间复杂度为 O()。 此时快速排序对应的递归树高度为 O(n)每一次划分对应的时间为 O(n)以整个排序时间为 O()。 7、哪些算法采用分治策略。 其中二路归并排序和折半查找算法采用分治策略。 8、适合并行计算的问题通常表现出哪些特征 1将工作分离成离散部分有助于同时解决。例如对于分治法设计的串行算法可以将各个独立的子问题并行求解最后合并成整个问题的解从而转化为并行算法。 2随时并及时地执行多个程序指令。 3多计算资源下解决问题的耗时要少于单个计算资源下的耗时。 9、设有两个复数 xabi 和 ycdi。复数乘积 xy 可以使用 4 次乘法来完成即xy(ac-bd)(adbc)i。设计一个仅用 3 次乘法来计算乘积 xy 的方法。 xy(ac-bd)((ab)(cd)-ac-bd)i。由此可见这样计算 xy 只需要 3 次乘法即ac、bd 和(ab)(cd)乘法运算。 10、 有 4 个数组 a、b、c 和 d都已经排好序说明找出这 4 个数组的交集的方法。 采用基本的二路归并思路先求出 a、b 的交集 ab再求出 c、d 的交集 cd最后求出 ab 和 cd 的交集即为最后的结果。也可以直接采用 4 路归并方法求解。 11、简要比较蛮力法和分治法。 蛮力法是一种简单直接地解决问题的方法适用范围广是能解决几乎所有问题的一般性方法常用于一些非常基本、但又十分重要的算法排序、查找、矩阵乘法和字符串匹配等蛮力法主要解决一些规模小或价值低的问题可以作为同样问题的更高效算法的一个标准。而分治法采用分而治之思路把一个复杂的问题分成两个或更多的相同或相似的子问题再把子问题分成更小的子问题直到问题解决。分治法在求解问题时通常性能比蛮力法好。 12、在采用蛮力法求解时什么情况下使用递归 如果用蛮力法求解的问题可以分解为若干个规模较小的相似子问题此时可以采用递归来实现算法 13、回溯法在问题的解空间树中按什么策略从根结点出发搜索解空间树 深度优先 14、对于回溯法说法错误的是 回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 15、回溯法的效率依赖于哪些因素 满足显约束的值的个数、计算约束函数的时间、计算限界函数的时间 16、什么函数是回溯法中为避免无效搜索采取的策略 剪枝函数 17、回溯法的搜索特点是什么 回溯法在解空间树中采用深度优先遍历方式进行解搜索即用约束条件和限界函数考察解向量元素 x[i]的取值如果 x[i]是合理的就搜索 x[i]为根结点的子树如果x[i]取完了所有的值便回溯到 x[i-1]。 18、用回溯法解 0/1 背包问题时该问题的解空间是何种结构用回溯法解流水作业调 度问题时该问题的解空间是何种结构 用回溯法解 0/1 背包问题时该问题的解空间是子集树结构。用回溯法解流水作业调度问题时该问题的解空间是排列树结构。 19、对于递增序列 a[]{12345}采用回溯法求全排列以 1、2 开头的排列一定最先出现吗为什么 是的。对应的解空间是一棵排列树如图所示给出前面 3 层部分显然最先产生的排列是从 G 结点扩展出来的叶子结点它们就是以 1、2 开头的排列。 20、考虑 n 皇后问题其解空间树为由 1、2、…、n 构成的 n!种排列所组成。现用回溯法求解如下 1通过解搜索空间说明 n3 时是无解的。
n3 时的解搜索空间如图所示不能得到任何叶子结点所有无解。 2给出剪枝操作。
剪枝操作是任何两个皇后不能同行、同列和同两条对角线。
3最坏情况下在解空间树上会生成多少个结点分析算法的时间复杂度。
最坏情况下每个结点扩展 n 个结点共有个结点算法的时间复杂度为O() 21、分枝限界法在问题的解空间树中按什么策略从根结点出发搜索解空间树。 广度优先 22、常见的两种分枝限界法为 队列式FIFO分枝限界法与优先队列式分枝限界法。 23、分枝限界法求解 0/1 背包问题时活结点表的组织形式是 大根堆 24、采用最大效益优先搜索方式的算法是 分枝限界法 25、优先队列式分枝限界法选取扩展结点的原则是 结点的优先级 26、简述分枝限界法的搜索策略。 分枝限界法的搜索策略是广度优先遍历通过限界函数可以快速找到一个解或者最优解。 27、有一个 0/1 背包问题其中 n4物品重量为4753物品价值为40422512背包最大载重量 W10给出采用优先队列式分枝限界法求最优解的过程。 求解过程如下 1根结点 1 进队对应结点值e.i0e.w0e.v0e.ub76x:[0000]。 2出队结点 1左孩子结点 2 进队对应结点值e.no2e.i1e.w4e.v40e.ub76x:[1000]右孩子结点 3 进队对应结点值e.no3e.i1 e.w0e.v0e.ub57x:[0000]。 3出队结点 2左孩子超重右孩子结点 4 进队对应结点值e.no4e.i2e.w4e.v40e.ub69x:[1000]。 4出队结点 4左孩子结点 5 进队对应结点值e.no5e.i3e.w9e.v65e.ub69x:[1010]右孩子结点 6 进队对应结点值e.no6e.i3e.w4e.v40e.ub52x:[1000]。 5出队结点 5产生一个解maxv 65bestx:[1010]。 6出队结点 3左孩子结点 8 进队对应结点值e.no8e.i2e.w7e.v42e.ub57x:[0100]右孩子结点 9 被剪枝。 7出队结点 8左孩子超重右孩子结点 10 被剪枝。 8出队结点 6左孩子结点 11 超重右孩子结点 12 被剪枝。 9队列空算法结束产生的最优解maxv 65bestx:[1010]。 28、有一个流水作业调度问题n4a[]{51097}b[]{7598}给出采用优先队列式分枝限界法求一个解的过程。 求解过程如下 1根结点 1 进队对应结点值e.i0e.f10e.f20e.lb29 x[0000]。 2出队结点 1扩展结点如下 进队j1结点 2e.i1e.f15e.f212e.lb27x[1000]。 进队j2结点 3e.i1e.f110e.f215e.lb34x[2000]。 进队j3结点 4e.i1e.f19e.f218e.lb29x[3000]。 进队j4结点 5e.i1e.f17e.f215e.lb28x[4000]。 3出队结点 2扩展结点如下 进队j2结点 6e.i2e.f115e.f220e.lb32x[1200]。 进队j3结点 7e.i2e.f114e.f223e.lb27x[1300]。 进队j4结点 8e.i2e.f112e.f220e.lb26x[1400]。 4出队结点 8扩展结点如下 进队j2结点 9e.i3e.f122e.f227e.lb31x[1420]。 进队j3结点 10e.i3e.f121e.f230e.lb26x[1430]。 5出队结点 10扩展一个 j2 的子结点有 e.i4到达叶子结点产生的一个解 是 e.f131e.f236e.lb31x[1432]。 该解对应的调度方案是第 1 步执行作业 1第 2 步执行作业 4第 3 步执行作业 3第 4 步执行作业 2总时间36。 29、贪心算法的基本要素的是 贪心选择性质 30、什么问题不能使用贪心法解决。 n 皇后问题 31、采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序故算法的时间复杂度为 O(nlog2n) 32、关于 0/ 1 背包问题 对于同一背包与相同的物品做背包问题取得的总价值一定大于等于做 0/1 背包问题。 33、一棵哈夫曼树共有 215 个结点对其进行哈夫曼编码共能得到 个不同的码字。 108 34、求解哈夫曼编码中如何体现贪心思路 在构造哈夫曼树时每次都是将两棵根结点最小的树合并从而体现贪心的思路。 35、举反例证明 0/1 背包问题若使用的算法是按照 vi/wi的非递减次序考虑选择的物品即只要正在被考虑的物品装得进就装入背包则此方法不一定能得到最优解此题说明 0/1 背包问题与背包问题的不同。 例如n3w{322}v{744}W4 时由于 7/3 最大若按题目要求的方法只能取第一个收益是 7。而此实例的最大的收益应该是 8取第 2、3个物品。 36、通常以自底向上的方式求解最优解的是 动态规划法 37、备忘录方法是什么算法的变形。 动态规划法 38、动态规划算法基本要素的是。 子问题重叠性质 39、一个问题可用动态规划算法或贪心算法求解的关键特征是问题的 最优子结构性质 40、简述动态规划法的基本思路。 动态规划法的基本思路是将待求解问题分解成若干个子问题先求子问题的解然后从这些子问题的解得到原问题的解。 41、简述动态规划法与贪心法的异同。 动态规划法的 3 个基本要素是最优子结构性质、无后效性和重叠子问题性质而贪心法的两个基本要素是贪心选择性质和最优子结构性质。所以两者的共同点是都要求问题具有最优子结构性质。 两者的不同点如下 1求解方式不同动态规划法是自底向上的有些具有最优子结构性质的问题只能用动态规划法有些可用贪心法。而贪心法是自顶向下的。 2对子问题的依赖不同动态规划法依赖于各子问题的解所以应使各子问题最优才能保证整体最优而贪心法依赖于过去所作过的选择但决不依赖于将来的选择也不依赖于子问题的解。 42、简述动态规划法与分治法的异同。 两者的共同点
是将待求解的问题分解成若干子问题先求解子问题然后再从这些子问题的解得到原问题的解。
两者的不同点是
适合于用动态规划法求解的问题分解得到的各子问题往往不是相互独立的重叠子问题性质而分治法中子问题相互独立另外动态规划法用表保存已求解过的子问题的解再次碰到同样的子问题时不必重新求解而只需查询答案故可获得多项式级时间复杂度效率较高而分治法中对于每次出现的子问题均求解导致同样的子问题被反复求解故产生指数增长的时间复杂度效率较低 43、哪些属于动态规划算法 判断算法是否具有最优子结构性质、无后效性和重叠子问题性质。直接插入排序算法、简单选择排序算法 和 二路归并排序算法 均属于动态规划算法。
计算题
时间复杂度的计算
一、 二、 三、 递归算法计算
一、 二、 三、 四、 五、 六、 背包问题0-1背包问题 回溯法 动态规划法 编程题
用回溯法解方程
#includeiostream
using namespace std;int a[6] { 0 };
int solution(int b[], int m, int n)
{if (m n){if (b[0] * b[1] - b[2] * b[3] - b[4] 1){printf(解为a%d b%d c%d d%d e%d\n, b[0], b[1], b[2], b[3], b[4]);}return 0;}for (int i 1; i n; i){if (a[i] 0){a[i] 1;b[m] i;solution(b, m 1, n);a[i] 0;}}
}
int main()
{int c[6];solution(c, 0, 5);return 0;
} 动态规划法解决蜘蛛吃蚊子
#include iostream
#include vector
#include algorithm
#include string
#include cstdlibint main(int argc, char** argv)
{int n 5, i, j;if (argc 2) n std::stoi(argv[1]);std::vectorstd::vectorint dp(n, std::vectorint(n, 1));for (i 1; i n; i)for (j 1; j n; j){dp[i][j] dp[i - 1][j] dp[i][j - 1];}std::cout total path for n x n grid: dp[n - 1][n - 1] std::endl;return 0;
} 用分治法解决抛硬币问题
#include iostream
#include vector
#include string
#include cstdlib
#include numeric
#include time.h int solve(std::vectorint a, int low, int high);int main(int argc, char** argv)
{int n 100, m, ans;if (argc 2) n std::stoi(argv[1]);std::vectorint a(n, 2);srand((unsigned)time(NULL));m rand() % n; std::cout m: m std::endl;a[m] 1;std::cout solving ... std::endl;ans solve(a, 0, n - 1);std::cout coin ans is fake std::endl;return 0;
}int solve(std::vectorint a, int low, int high)
{int sum1, sum2, mid, ret_val;if (low high) return low; // 只有一个硬币if (low high - 1) // 只有两个硬币{std::cout weighing coin low and high std::endl;if (a[low] a[high]) ret_val low;else ret_val high;std::cout -- coin ret_val is lighter std::endl;return ret_val;}mid (low high) / 2;if ((high - low 1) % 2 0) // 硬币数量为偶数{sum1 std::accumulate(a.begin() low, a.begin() mid 1, 0);sum2 std::accumulate(a.begin() mid 1, a.begin() high 1, 0);std::cout weighing coin low - mid and mid 1 - high std::endl;}else // 硬币数量为奇数{sum1 std::accumulate(a.begin() low, a.begin() mid, 0);sum2 std::accumulate(a.begin() mid 1, a.begin() high 1, 0);std::cout weighing coin low - mid - 1 and mid 1 - high std::endl;}std::cout sum1 sum1 , sum2 sum2 std::endl;if (sum1 sum2){std::cout -- equal std::endl;return mid;}else if (sum1 sum2){std::cout -- the former is lighter std::endl;if ((high - low 1) % 2 0) return solve(a, low, mid); // 偶数else return solve(a, low, mid - 1); // 奇数}else{std::cout -- the latter is lighter std::endl;return solve(a, mid 1, high);}
} 用二分法分两边求最大值
#includestdio.h
void maxmin(int a, int b, int* min, int* max);
int array[9] { 1,3,4,5,6,7,8,9,2 };int main() {int _max, _min;maxmin(0, 8, _min, _max);printf(MAX:%d, MIN:%d, _max, _min);
}void maxmin(int a, int b, int* min, int* max) {int lmax, lmin, rmax, rmin;if (a b) *min *max array[a];else if (a b - 1) {if (array[a] array[b]) {*min array[a];*max array[b];}else {*min array[b];*max array[a];}}else {int mid (a b) / 2;maxmin(a, mid, lmin, lmax);maxmin(mid 1, b, rmin, rmax);if (lmin rmin) *min lmin;else *min rmin;if (rmax lmax) *max lmax;else *max rmax;}}
