c++递推算法详解.ppt

递推算法 递推问题求解过程 确定状态 确定递推关系和边界条件 程序实现 例1 计算系数 NOIP2011day2 题目描述 给定一个多项式 ax by k 请求出多项式展开后xnym项的系数 输入 共一行 包含5个整数 分别为a b k n m 每两个整数之间用一个空格隔开 输出 输出共1行 包含一个整数 表示所求的系数 这个系数可能很大 输出对10007取模后的结果 输入输出样例 factor infactor out113123 数据范围 对于30 的数据 有0 k 10 对于50 的数据 有a 1 b 1 对于100 的数据 有0 k 1 000 0 n m k 且n m k 0 a b 1 000 000 方法一 根据二项式定理可知 ax by k 取i n xnym的系数为其中an和bm可以用快速幂来计算 在lg n lg m 内完成 计算可以用递推来求解 状态 f i j 表示从i个数中选j个数的方案数 f k n 就是答案 根据第i数选还是不选来进行分析 1 选择第i个数 此情况的方案数等价于从i 1个数中选择j 1个数的方案数即f i 1 j 1 2 不选第i个数 此情况的方案数等价于从i 1个数中选择j个数的方案数即f i 1 j 所以f i j f i 1 j 1 f i 1 j 边界条件 f i 0 1 f i i 1 时间复杂度为O n k 方法二 当k达到106的时候 方法一会超时 由于10007是素数 在计算C k n mod10007时可以采用扩展GCD来解决 时间复杂度为O k 参考代码 include includeusingnamespacestd ifstreamfin factor in ofstreamfout factor out constintMAXN 1005 intdp MAXN MAXN a b k n m ans intmain fin a b k n m dp 1 1 dp 1 2 1 for inti 2 i k i for intj 1 j i 1 j dp i j dp i 1 j dp i 1 j 1 10007 ans dp k m 1 for inti 1 i n i ans ans 10007 a 10007 10007 for inti 1 i m i ans ans 10007 b 10007 10007 fout ans endl return0 例2 B光滑数 问题描述 B为一个正整数 如果一个自然数N的质因子分解式中没有大于B的因子 我们就称N是一个B光滑数 请你编一个程序 求出某个区间中所有的B光滑数的个数 输入 输入文件名为bnum in 仅有一行 包含三个用空格隔开的整数N M B 其中1 N 2 000 000 000 1 M 100 000 000 1 B 1 000 000 输出 输出文件名为bnum out 仅一行 一个整数 表示区间 N N M 之间的B光滑数的个数 样例输入 30105 样例输出 4 参考题解 首先我们定义一个表pri max pri i 表示第i个质数 第一个质数为2 设数组max 其中max i 记录i的最大质因子 定义f b x1 x2 表示区间 x1 x2 之间不包括大于第b个质数的质因子的所有正整数 则有如下递归关系 F b x1 x2 f b 1 x1 x2 f b x1 1 divpri b 1 x2divpri b 该递归式的边界条件为 F 0 x1 x2F x2 x1 1x2 pri b 可直接验证x1 x2F trunc log2 x2 trunc log2 x1 b 1 例3 出栈序列统计 问题描述 栈是常用的一种数据结构 有n个元素在栈顶端一侧等待进栈 栈顶端另一侧是出栈序列 你已经知道栈的操作有两种 push和pop 前者是将一个元素进栈 后者是将栈顶元素弹出 现在要使用这两种操作 由一个操作序列可以得到一系列的输出序列 请你编程求出对于给定的n 计算并输出由操作数序列1 2 n 经过一系列操作可能得到的输出序列总数 输入 输出 就一个数n 1 n 1000 一个数 即可能输出序列的总数目 样例 stack instack out35 算法分析 我们通过回溯的方法计算并输出不同的出栈序列 这里只要求输出不同的出栈序列总数目 所以我们希望能找出相应的递推公式进行处理 从排列组合的数学知识可以对此类问题加以解决 我们先对n个元素在出栈前可能的位置进行分析 它们有n个等待进栈的位置 全部进栈后在栈里也占n个位置 也就是说n个元素在出栈前最多可能分布在2 n位置上 出栈序列其实是从这2n个位置上选择n个位置进行组合 根据组合的原理 从2n个位置选n个 有C 2n n 个 但是这里不同的是有许多情况是重复的 每次始终有n个连续的空位置 n个连续的空位置在2n个位置里有n 1种 所以重复了n 1次 所以出栈序列的种类数目为 算法分析 C 2n n n 1 2n 2n 1 2n 2 n 1 n n 1 2n 2n 1 2n 2 n 2 n 考虑到这个数据可能比较大 所以用高精度运算来计算这个结果 本题实际是一个经典的Catalan数模型 有关Catalan数的详细解释请参考 组合数学 等书 参考程序 include includeusingnamespacestd typedeflonglonglld lldi n ans lldh 1000 intmain freopen stack in r stdin freopen stack out w stdout h 2 1 cin n n n 2 for lldi 3 i n i for lldk 2 k i k h i h i h k h i k 1 cout h n endl return0 思考与提高 我们知道 在某个状态下 所能做的操作 移动方法 无非有两种 1 将右方的等待进栈的第一个元素进栈 2 将栈顶的元素出栈 进入左边的出栈序列 设此时右方 栈 左方的元素个数分别为a b c 我们就能用 a b c 表示出当前的状态 显然n a b c 则c n a b 即已知a和b c就被确定 所以我们可以用 a b 来作为状态的表示方法 则起始状态为 n 0 目标状态为 0 0 又由上面的两种移动方法 我们可类似的得到两种状态转移方式 思考与提高 思考与提高 再设f a b 为从状态 a b 通过移动火车变为状态 0 0 的所有移动方法 类似于动态规划的状态转移方程 我们可写出以下递归式 边界值 f 0 0 1 有了这个递归公式后 再写程序就比较简单了 例4 骨牌覆盖问题 有2行n列的长方形方格 要求用n个1 2的骨牌铺满 有多少种铺法 如n 3时有以下3种覆盖方法 方法一 状态 f i 表示铺满2 i的长方形的方案数找规律 手工或搜索求出i 1 2 3 4 5的方案数分别为1 2 3 5 8 容易发现f i f i 1 f i 2 i 3 边界条件 f 1 1 f 2 2递推关系式1i 1f i 2i 2f i 1 f i 2 i 3答案为f n 时间复杂度为O n 方法二 对于i 3 分析第一列的两个格子覆盖情况 有两种情况 1 用1 2的骨牌竖着覆盖第一列 这种情况的方案数等于后面2 i 1 的长方形的覆盖方案数 即f i 1 2 用两个1 2的骨牌横着覆盖 这种情况的方案数等于后面2 i 2 的长方形的覆盖方案数 即f i 2 所以f i f i 1 f i 2 方法三 分析用1 2的骨牌覆盖列的位置来计算方案数1 如果i为偶数 覆盖方案分为两类 1 没有竖立覆盖其中一列的情况 全部用横向覆盖的方案 方案数为1 2 有竖立覆盖的情况 为了避免重复 考虑第一次竖立覆盖的位置在x列 x必须是奇数 而且前1到x 1列覆盖方法唯一 全部采用横向覆盖 方案数等于后面i x列的覆盖情况 即f i x 所以当i为偶数时 f i 1 f 1 f 3 f i 3 f i 1 2 如果i是奇数 一定有竖立覆盖的情况 f i 1 f 2 f 4 f i 3 f i 1 如何证明该递推关系式等价于f i f i 1 f i 2 试着用横向覆盖的来分析递推关系式 方法四 分治 一分为二来考虑 左边为ndiv2列 右边为n ndiv2列 如果左右独立则方案数为f ndiv2 f n ndiv2 如果有横向覆盖第ndiv2列和第ndiv2 1列 则方案数为f ndiv2 1 f n ndiv2 1 所以f n f ndiv2 f n ndiv2 f ndiv2