6递推步骤
7算法描述(盒图 PAD图之类的老师说看看但我不懂怎么考)
1.算法的基本性质
(1) 目的性:算法有明确的目的,算法能够完成赋予它的功能。
(2) 分步性:算法为完成其复杂的功能,由一系列计算机可执行的步骤组成。
(3) 有序性:算法的步骤是有序的,不可能随意改变算法步骤的执行顺序。
(4) 有限性:算法是有限的指令顺序,算法所包含的步骤是有限的。
(5) 操作性:有意义的算法总是对某些对象进行操作,使其改变状态完成其功能。
2.算法的考量
对于算法的分析和评估,一般考虑正确性、可维护性、可读性、运算量、占用存储空间等方面考虑。三条主要标准:
(1) 算法实现所耗费的时间。
(2) 算法实现所耗费的空间,其中主要考虑辅助存储空间。
(3) 算法易于理解、易于编码、易于调试。
3.什么是迭代
迭代法也称“辗转法”,是一种不断用变量的旧值递推出新值的解决问题的方法。
4.分治法求解的过程
分治法求解问题的过程是,将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大,则可反复使用分治策略将这些子问题分成更小的同类型子问题,直至产生方便求解的子问题,必要时逐步合并这些子问题的解,从而得到问题的解。
(1) 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问
题。
(2) 解决:若子问题规模较小而容易被解决则直接解决,否则继续分解为更小的子
问题,直至容易解决。
(3) 合并:将已求解的各个子问题的解,逐步合并为原问题的解。
5.动态规划策略
基本思想:把求解问题分成许多阶段或多个子问题,然后按顺序求解各个子问题。 基本步骤:
(1) 划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。注意,着
若干个阶段一定要是有序的或者可排序的。
(2) 选择状态:将问题发展到各个阶段时所出现的各个客观情况用不同的状态表
示出来。当然,状态的选择要满足无后效性。
(3) 确定决策并写出状态转移方程:状态转移就是根据上一阶段的状态和决策来
导出本阶段的状态。这就像是“递推”,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
6.递推