BX110937李建辉算法设计实验六

电子信息学院实验报告书课程名： 算法设计与分析题目：实验六动态规则实验类别 【设计型】 班级： 学号： 姓名： 李建辉评语：实验态度：认真（）一般 （） 较差（）实验结果：正确（）部分正确（） 错（）实验理论：掌握（）熟悉（） 了解（）生疏（）操作技能：较强（）一般 （） 较差（）实验报告：较好（）一般 （） 较差（）成绩：指导教师：王淮亭批阅时间:2014年05月05日1□实验目的（） 初步掌握动态规划算法（） 能够运用动态规划的思想解决实际问题，如矩阵连乘问题等21实验要求（） 个矩阵连乘问题。（） 应用顺推实现动态规划求解行列边数值矩阵最大的路程，已知行列的边数值矩阵，每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路程。（） 求解点数值矩阵最小路径，随机产生一个行列的整数矩阵在整数矩阵中寻找从左上角至右下角每步可向下或向右或斜向右下的一条数值和最小的路径。（） 应用递推实现动态规划求解序列的最小子段和。（） 插入加号求最小值，在一个位整数中插入个加号，将它分成 个整数，找出一种加号的插入方法，使得这 个整数的和最小。31实验原理动态规划的基本思想：动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题41实验设备机51实验步骤（） 刻画最优解的结构特性；（） 递归定义最优解值；（） 以自底向上方式计算最优解值；（） 根据计算得到的信息构造一个最优解。其中，第（）至（）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值61实验结果《数据库原理及应用》实验报告图6-1n个矩阵连乘问题r・F:丽风细雨口盘\计算机常用算法和程序设出^用计茸机茸法实验\Dcbug相为1小回、请输入数字三角形的行数n：4A223211 122101 2 731 931图6-2应用顺推实现动态规划求解n行m列边数值矩阵最大的路程a・F:丽闻细雨U用位+菖机嵬用菖法M程庠沙萍淳用计彦疝苴法实际Dehua\5v6-3.eke'回12T较■■■左力n6以定"库确.•31请.134第*2LMJ.2-白列曾褊为序梃个4,"八n12-2鬟中的6,子子I-I-2\!\|歹歹医誓薯取*□Pfessanykeytoc口ntimiE图6-3递推实现动态规划求解序列的最小子段和图6-4插入加号求最小值71实验体会通过这次实验加深了我对动态规划算法的理解，通过这五个实验使我熟练掌握动态规划算法，使我对动态规划算法，分治法，贪心算法有了区别的认识，动态规划算法融合了分治法和贪心法的优点，更好的解决问题，实验有利于加深理论的理解，非常实用。口：源程序第一题源程序：请输入矩阵的个数请输入第个矩阵的行数请输入第个矩阵的列数，也是第 个矩阵的行数请输入第个矩阵的列数个矩阵连乘的乘法次数的最小值为第二题源程序:请输入数字三角形的行数底边最短路程为：最短路径为：顶点底边。第三道题程序：随机产生一个行列的整数矩阵在整数矩阵中寻找从左上角至右下角每步可向下或向右或斜向右下的一条数值和最小的路径。应用动态规划，即从右下角逐行反推至左上角。确定 后，随机产生的整数二维数组作矩阵输出，同时赋给部分和数组 。这里数组 为点 到右下角的最小数值和，是点向右（）或向下（）或向右下（）的路标字符数组。注意到最后一行与最后一列各数只有一个出口于是由开始向左逐个推出同行的向上逐个推出同列的与同一行其右边的整数 或其右下方的首先作赋值然后求 与 的最小值的值由同一列其下面的整数 与的值决定其中变量为原 的值）如果 说明前面为 赋值不对作修改若为 则 否则这样反推所得 即为所求的最小路径数字和。为了打印最小路径利用数组从上而下操作先打印若 则增即 然后打印 与右边整数若 则增即 然后打印 与下面整数若 则均增即 然后打印 与斜向右下整数依此类推直至打印到终点 。第四道题