下载文档原格式
递推算法在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第N项数或所有的数列元素（如果可以枚举的话），或求前N项元素之和。
这种从已知数据入手，寻找规则，推导出后面的数的算法，称这递推算法。
典型的递推算法的例子有整数的阶乘，1，2，6，24，120…，a[n]=a[n-1]*n(a[1]=1)；前面学过的2n，a[n]=a[n-1]*2(a[1]=1)，菲波拉契数列：1，2，3，5，8，13…，a[n]=a[n-1]+a[n-2](a[1]=1,a[2]=2)等等。
在处理递推问题时，我们有时遇到的递推关系是十分明显的，简单地写出递推关系式，就可以逐项递推，即由第i项推出第i+1项，我们称其为显示递推关系。
但有的递推关系，要经过仔细观察，甚至要借助一些技巧，才能看出它们之间的关系，我们称其为隐式的递推关系。
下面我们来分析一些例题，掌握一些简单的递推关系。
例如阶梯问题：题目的意思是：有N级阶梯，人可以一步走上一级，也可以一步走两级，求人从阶梯底走到顶端可以有多少种不同的走法。
这是一个隐式的递推关系，如果编程者不能找出这个递推关系，可能就无法做出这题来。
我们来分析一下：走上第一级的方法只有一种，走上第二级的方法却有两种（两次走一级或一次走两级），走上第三级的走法，应该是走上第一级的方法和走上第二级的走法之和（因从第一级和第二级，都可以经一步走至第三级），推广到走上第i级，是走上第i-1级的走法与走上第i-2级的走法之和。
很明显，这是一个菲波拉契数列。
到这里，读者应能很熟练地写出这个程序。
在以后的程序习题中，我们可能还会遇到菲波拉契数列变形以后的结果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。
我们再来分析一下尼科梅彻斯定理。
定理内容是：任何一个整数的立方都可以写成一串连续的奇数和，如：43=13+15+17+19=64。
分治算法是一种算法设计思想，其主要思想是将一个复杂的问题分解为两个或更多相同或相似的子问题，直到子问题简单到可以直接解决。
然后，再将子问题的解合并，形成原问题的解。
这种算法设计思想常用于数据结构和算法设计中，如排序算法（如快速排序和归并排序）、二叉树操作等。
递归与分治的关系
递归是一种编程或函数自我调用的方法，递归函数会不断地调用自身，直到满足某个终止条件。
分治算法常常使用递归作为其实现手段，通过递归调用来实现问题的分解和解的合并。
这种情况下，递归就成为了实现分治的一种手段。
虽然分治算法常常依赖于递归来实现，但并不是所有的递归算法都是分治算法。
分治算法的关键在于解决问题的方式：它把一个问题分解为若干个独立的子问题，然后对子问题求解，最后合并子问题的解来得到原问题的解。
而递归只是一种函数自我调用的编程技巧，其并没有明确规定问题需要如何被分解和求解。
示例：归并排序
归并排序就是一个典型的分治算法。
归并排序首先将一个待排序的序列分解为两个或更多的子序列，然后对每个子序列进行排序，最后将排序后的子序列合并为一个有序序列。
递推算法在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第N项数或所有的数列元素（如果可以枚举的话），或求前N项元素之和。
这种从已知数据入手，寻找规则，推导出后面的数的算法，称这递推算法。
典型的递推算法的例子有整数的阶乘，1，2，6，24，120…，a[n]=a[n-1]*n(a[1]=1)；前面学过的2n，a[n]=a[n-1]*2(a[1]=1)，菲波拉契数列：1，2，3，5，8，13…，a[n]=a[n-1]+a[n-2](a[1]=1,a[2]=2)等等。
在处理递推问题时，我们有时遇到的递推关系是十分明显的，简单地写出递推关系式，就可以逐项递推，即由第i项推出第i+1项，我们称其为显示递推关系。
但有的递推关系，要经过仔细观察，甚至要借助一些技巧，才能看出它们之间的关系，我们称其为隐式的递推关系。
下面我们来分析一些例题，掌握一些简单的递推关系。
例如阶梯问题：题目的意思是：有N级阶梯，人可以一步走上一级，也可以一步走两级，求人从阶梯底走到顶端可以有多少种不同的走法。
这是一个隐式的递推关系，如果编程者不能找出这个递推关系，可能就无法做出这题来。
我们来分析一下：走上第一级的方法只有一种，走上第二级的方法却有两种（两次走一级或一次走两级），走上第三级的走法，应该是走上第一级的方法和走上第二级的走法之和（因从第一级和第二级，都可以经一步走至第三级），推广到走上第i级，是走上第i-1级的走法与走上第i-2级的走法之和。
很明显，这是一个菲波拉契数列。
到这里，读者应能很熟练地写出这个程序。
在以后的程序习题中，我们可能还会遇到菲波拉契数列变形以后的结果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。
我们再来分析一下尼科梅彻斯定理。
定理内容是：任何一个整数的立方都可以写成一串连续的奇数和，如：43=13+15+17+19=64。
递归与递推递推递归递归：从已知问题的结果出发，⽤迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。
递推：从已知道的若⼲项出发，利⽤递推关系依次推算出后⾯的未知项的⽅法，我们称为递推算法。
递推与递归不同：递归是从未知到已知逐步接近解决问题的过程，⽽递推从已知到未知。
递推算法是⼀种⽤若⼲步可重复运算来描述复杂问题的⽅法。
递推是序列计算中的⼀种常⽤算法。
通常是通过计算前⾯的⼀些项来得出序列中的指定项的值。
递推的关系式可以暴枚找规律，也可以化繁为简，例如铺砖问题，最后⼀列砖铺与不铺，以及最后两列砖铺与不铺的情况相加即可求出关系式。
⽽关于递归，就是函数中再次调取函数，从⽽使困难的问题化为“1+1”类型简单的问题，得出结果再还原，操作过程类似于“U”型。
递归的重点是找到递归关系和递归出⼝。
……（概念太多，直接摆题）经典例题统计奇数和偶数个3内存限制：128 MiB时间限制：1000 ms标准输⼊输出题⽬类型：传统评测⽅式：⽂本⽐较题⽬描述在所有的N位正整数中，有多少个数中有偶数个数字3？⼜有多少个数有奇数个3？由于结果可能很⼤，你只需要输出这个答案对12345取余的值。
输⼊格式输⼊⼀个数N(1<=N<=1000)，输⼊形式为⽂件输⼊，以读到0或⽂件末尾结束。
输出格式对于每⼀个N位正整数，输出有多少偶数个3以及多少奇数个3，中间⽤空格隔开。
样例样例输⼊2样例输出73 17数据范围与提⽰分别找出奇数偶数的递推式样例说明：在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个对于⼀位数，除3外，其他全为含有偶数个三（数组元素初始化），紧接着，对于两位数，13，23，30~39（除33外）【这⾥有9个数，也可以进⾏思考】，43，53，63，73，83，93含有奇数个三，再看三位数（差不多就可以找到规律……）。
声明：a数组存储含奇数个三的个数，b数组⽤于存储偶数i的数值 1 2 3 ……a[i] 1 17 674 ……b[i] 8 73 226 ……So,a[i]=(b[i-1]+a[i-1]*9)%12345,b[i]=(a[i-1]+b[i-1]*9)%12345;#include<cstdio>using namespace std;int main(){int n,a[10005],b[10005];a[1]=1,b[1]=8;for(int i=2;i<=1001;i++){a[i]=(b[i-1]+a[i-1]*9)%12345;b[i]=(a[i-1]+b[i-1]*9)%12345;}while(scanf("%d",&n)!=EOF){if(n==0)return 0;printf("%d %d\n",b[n],a[n]);}return 0;}Hanoi塔内存限制：128 MiB时间限制：1000 ms标准输⼊输出题⽬类型：传统评测⽅式：⽂本⽐较题⽬描述问题的提出：Hanoi塔由n个⼤⼩不同的圆盘和三根⽊柱a,b,c组成。
