在QQ上做cpa网站说是恶意的,线上卖货平台有哪些,建网站要多少钱维护,wordpress 国内镜像目录 一、实验目的 二、问题描述 三、实验要求 四、算法思想和实验结果 1、动态规划法原理#xff1a; 2、解决方法#xff1a; 2.1 方法一#xff1a;常规动态规划 2.1.1 算法思想#xff1a; 2.1.2 时间复杂度分析 2.1.3 时间效率分析 2.2 方法二#xff1a;动态规划加… 目录 一、实验目的 二、问题描述 三、实验要求 四、算法思想和实验结果 1、动态规划法原理 2、解决方法 2.1 方法一常规动态规划 2.1.1 算法思想 2.1.2 时间复杂度分析 2.1.3 时间效率分析 2.2 方法二动态规划加二分查找最优x 2.2.1 算法思想 2.2.2 时间复杂度分析 2.2.3 时间效率分析 2.3 方法三动态规划加逆向求解 2.3.1 算法思想 2.3.2 时间复杂度分析 2.3.3 时间效率分析 3、结果输出示例 一、实验目的 1. 掌握动态规划算法设计思想。 2. 掌握扔鸡蛋问题的动态规划法。 二、问题描述 扔鸡蛋问题是计算机程序设计中的一个经典问题。从一幢楼房的不同楼层往下扔鸡蛋用最少的最坏情况试验次数确定鸡蛋不会摔碎的最高安全楼层。仅有一个鸡蛋供试验时只能采用顺序查找法。有足够多的鸡蛋时可以采用二分查找法。有多于一个但数量有限的鸡蛋时采用动态规划方法求解。双蛋问题(two-egg problem)是本问题的一个特例曾出现于谷歌的程序员面试题中。 有一幢楼房高层。某人准备了N个鸡蛋供试验。他想知道鸡蛋从几层扔下不会摔碎并确定出最高安全楼层。试验过程中鸡蛋没有摔碎则可以继续使用摔碎了则需要换一个鸡蛋继续试验。为保证试验成功此人要设计一个程序以最小化最坏情况的试验次数F(M, N)。作为一个数学抽象本问题采用一些理想化假设所有鸡蛋抗摔能力相同不计重复坠地的累积损伤且忽略试验结果的偶然性。试验成功的标准是在N个鸡蛋用完之前精确确定最高安全楼层是哪一层。允许有鸡蛋剩余。 如果只有N1个鸡蛋供试验则为了保证试验成功只能从一层开始逐层往上试验。这相当于采用顺序查找算法最坏试验次数F(M, 1)M。如果一层就碎了则最高安全楼层为0。如果M层还不碎则最高安全楼层为M。 三、实验要求 1. 给出解决问题的动态规划方程 2. 理论分析该算法的时间复杂度 3. 分别测试M10000, 20000, …, 100000, N20时以及M50000, N11, 12, …, 20时的算法运行时间并分析实验结果 4. 依次在终端输出M10000, N1~20时的F(M, N)值实验课时检查该代码限用C或C语言编写。 四、算法思想和实验结果 1、动态规划法原理 将复杂问题划分为更小的子问题通过子问题的最优解来重构原问题的最优解。求解过程中保存子问题的解以便在需要时直接查表而不是重复计算从而减少计算量。 2、解决方法 2.1 方法一常规动态规划 2.1.1 算法思想 用二维数组k[m][n]表示从第m层扔n个鸡蛋的动态规划法最优解即该实验所要求的最少的最坏情况试验次数。 对于m层、n个鸡蛋的求解当尝试从第x层扔下一个鸡蛋时有两种情况 1鸡蛋破碎剩余n-1个鸡蛋则在第1层至第x-1层共x-1层继续尝试即k[x-1][n-1]。 2鸡蛋未破碎仍剩余n个鸡蛋则在第x1至m层共m-x层继续尝试即k[m-x][n] 因为题目要求是最坏情况所以应该取上述两种情况的较大者。又由于要最少实验次数所以x应该取让前面的较大者尽量小些的值。 得动态规划方程如下 k[m][n]1min{max{k[x-1][n-1],k[m-x][n]}}(x1,2,3……,m) 实验时 1对于m0、m1或n1的情况取值依次为0、1、m在创建**k时就赋值完成。 2对于其他值用三层for循环自底向上依次确定k[i][j]的值。伪代码如下 F1(m,n)for i2 to mfor j2 to nfor x1 to ik[i][j]1max{k[x-1][j-1],k[i-x][j]}return k[m][n] 2.1.2 时间复杂度分析 由前面伪代码可知最外层m-1次中间层n-1次最里层ii23……m次则时间复杂度为O(n*m^2)。 2.1.3 时间效率分析 由于效率较低这里降低数据规模分别测试M1000, 2000, …, 10000, N20时以及M10000N11, 12, …, 20时的算法运行时间对每种情况都运行5次取平均值。 1N20时以M1000为基准 M 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 平均运行时间/ms 47 190 434 814 1310 1964 2750 3706.2 4722.4 5802 理论时间/ms 47 188 423 752 1175 1692 2303 3008 3807 4700 得下图N20时的实际效率曲线和理论效率曲线图。 两条曲线一开始较贴合但随着M的增大实际运行时间与理论运行时间的差非负呈现递增趋势。 2M等于10000时以N11为基准 N 11 12 13 14 15 16 17 18 19 20 平均运行时间/ms 2890.5 3152.25 3443 3832 4092.5 4408 4704 5180 5478 5825 理论时间/ms 2890.5 3153.27 3416.05 3678.82 3941.59 4204.36 4467.17 4729.91 4992.68 5255.45 得下图M10000时的实际效率曲线和理论效率曲线图。 与上一个图一样两条曲线一开始较贴合但随着N的增大实际运行时间与理论运行时间的差非负呈现递增趋势。 可能原因是 k[i][j]1max{k[x-1][j-1],k[i-x][j]}中的数据访问的耗时实际是随着规模的增大而增大的但分析时间复杂度和理论时间时忽略这个。实际效率与理论效率之间差某些常数因子 2.2 方法二动态规划加二分查找最优x 2.2.1 算法思想 对于 for x1 to mk[i][j]1max{k[x-1][j-1],k[i-x][j]} 当x增大时k[x-1][j-1]是x相关的非递减函数而k[i-x][j]是x相关的非递增函数。所以可以在前面的基础上用二分法求出最优的x而不是从1到m逐个的尝试、比较。 由于层数为整数二分到最后有两种情况 1二分到最后low!high如下图则应该取点1和点3中次数较小的那个最坏情况下的最少测试次数即 k[i][j]min{k[i-low][j],k[high-1][j-1]} 2分到最后刚好lowhigh如下图此时xlowhighk[x-1][j-1,k[i-x][j]。 伪代码如下 F2(m,n)for i2 to mfor j2 to nl1;hi;while l1hx(lh)/2if k[x-1][j-1]k[i-x][j]lxelse if k[x-1][j-1]k[i-x][j]hxelse lowhighxk1min{k[i-l][j],k[h-1][j-1]}return k[m][n] 2.2.2 时间复杂度分析 原来求最优x需m次循环现在为log m所以时间复杂度变为O(n*m*log m) 2.2.3 时间效率分析 分别测试M10000, 20000, …, 100000, N20时以及M50000, N11, 12, …, 20时的算法运行时间对每种情况都运行20次取平均值。 1N20时以M10000为基准 M 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 平均运行时间/ms 5 9.5 14.5 19.05 29.95 34.45 41.5 47.45 57.5 62.93 理论时间/ms 5 10.75 16.79 23.01 29.37 35.84 42.39 49.03 55.74 62.5 得下图N20时的实际效率曲线和理论效率曲线图。 两条曲线贴合度较高说明算法效率基本符合关于m的mlog m级关系。 2M等于50000时以N11为基准 N 11 12 13 14 15 16 17 18 19 20 平均运行时间/ms 17 18.5 19.45 20 22.5 24 26.25 27.25 28.25 29 理论时间/ms 17 18.55 20.09 21.64 23.18 24.73 26.27 27.83 29.36 30.91 得下图M50000时的实际效率曲线和理论效率曲线图。 两条曲线较贴合说明算法效率基本符合关于N的线性关系。 2.3 方法三动态规划加逆向求解 2.3.1 算法思想 不直接按照在m层、n个鸡蛋的情况下求解最少的最坏情况试验次数而是逆向求解在n个鸡蛋、r次试验次数且最坏情况下最多能测多少层。找到层数大于m时的最小r。 此时扔鸡蛋碎了就继续测楼下没碎就继续测楼上。 总的可测楼层数 楼上的可测楼层数 楼下的可测楼层数 1当前这层楼。即 k[n][r]k[n][r-1]k[n-1][r-1]1 此时的**k和前面的两种方法的不同分配的空间不再是k[m1][n1]而是为k[n][max]max为一个较大的值由于实验要求的最大规模M100000、N20的解为447所以这里max取1000实际未知该解时应取更大些。 伪代码如下 F3(m,n)r0while k[n][r]m //r不超过mrfor i1 to nk[i][r]k[i][r-1]k[i-1][r-1]1return r 2.3.2 时间复杂度分析 外层while循环不大于m次内层for循环n次所以时间复杂度为O(n*m)。 2.3.3 时间效率分析 效率较高m2000000000n20时运行时间仍然小于1ms。 3、结果输出示例
