常见的NOIP基础算法综合.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * 分析 我们用坐标(x,y)唯一确定一个点，其中(m,n)表示图的右上角，而人的出发点是，受人前进方向的限制，能直接到达点(x,y)的点只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到点(x,y)的路径中和最大的路径必然要从(m/2,0)到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，关系式如下： Fx,y= Max{Fx+2,y-1 ,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1}+Numx,y， 其中Numx,y 表示(x,y) 点上的数字。 边界条件为： 动态规划与递推的关系 上题实质上是采用动态规划来求解,那么与递推动态规划之间到底是什么关系呢？ 我们不妨画个图(如下图)。而通常人们理解的递推关系就是一般递推关系，故认为动态规划与递推关系是两个各自独立的个体。 动态规划 一般递推关系 递推关系 动态规划与递推的关系 1、一般递推边界条件很明显,动态规划边界条件比较隐蔽,容易被忽视 2、一般递推数学性较强,动态规划数学性相对较弱 3、一般递推一般不划分阶段,动态规划一般有较为明显的阶段 递推进阶 【例题1】位数问题 【问题描述】在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案mod 12345的值。 【文件输入】读入一个数N(1=N=1000) 【文件输出】输出有多少个数中有偶数个数字3。 【样例输入】2 【样例输出】73 递推进阶 【例题2】铺磁砖问题 【问题描述】用1x1和2x2的磁砖不重叠地铺满Nx3的地板，问共有多少种不同的方案？ 【文件输入】输入一个整数n（1=N=1000）。 【文件输出】输出方案数，由于结果可能很大，你只需要输出这个答案mod 12345的值。 【样例输入】2 【样例输出】3 递推进阶 【例题3】路程问题 【问题描述】从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？ 【文件输入】输入一个整数n（1=n=1000）。 【文件输出】输出走法数。由于结果可能很大，你只需要输出这个答案mod 12345的值。 【样例输入】2 【样例输出】7 递推进阶 【例题4】圆周上的弦 【问题描述】圆周上有N个点。连接任意多条（可能是0条）不相交的弦（共用端点也算相交）共有多少种方案？ 【文件输入】输入一个整数n（1=N=1000）。 【文件输出】输出方案数。由于结果可能很大，你只需要输出这个答案mod 12345的值。 【样例输入】4 【样例输出】9 递推进阶 【例题5】矩形中的树 【问题描述】在网格中取一个N x 1的矩形，并把它当作一个无向图。这个图有2(N+1)个顶点，有3(N-1)+4条边。这个图有多少个生成树？ 【文件输入】输入一个整数n（1=N=1000）。 【文件输出】输出这个图有多少个生成树？由于结果可能很大，你只需要输出这个答案mod 12345的值。 【样例输入】1 【样例输出】4 第三部分 递归策略 递归的概念与基本思想 一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。 递归的实现方法 递归是借助于一个递归工作栈来实现；递归=递推+回归； 1.递推：问题向一极推进,这一过程叫做递推；这一过程相当于压栈。 2.回归：问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈。 用递归算法求 n! 定义：函数 fact(n)=n! fact(n-1)=(n-1)! 则有 fact(n)=n*fact(n-1) 已知 fact(1)=1 * 下面画出了调用和返回的递归示意图 递归的实现 递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。由此可以想到，减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简。 【例题】写出结果 void rever() { char c; cinc; if(c!=!)rever(); coutc; } int main() { rever();