下载文档原格式
递推算法在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第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组成。
递归与递推公式的掌握技巧掌握递归与递推公式的技巧在计算机科学领域中，递归和递推公式是重要的概念和工具。
递归是指在一个函数或过程内部调用自己，直到满足某个条件才返回结果。
递推公式是指通过前面的结果推导出后面的结果的公式，也称为递归公式。
递归和递推公式在算法设计、数据结构、数学等领域都得到了广泛应用。
递归和递推公式的掌握是编程和数学学习的重点之一。
在实际应用中，掌握递归和递推公式对程序的正确性、效率和可读性都是至关重要的。
本文将介绍如何掌握递归和递推公式的技巧，帮助读者更好地应用它们解决问题。
第一部分：递归的设计和实现递归的设计和实现是一项重要的技巧。
递归函数的设计和实现需要考虑以下几个方面：1.确定递归的终止条件递归的过程必须能够终止，否则会造成死循环或栈溢出等问题。
因此，在设计递归函数时必须确定递归的终止条件。
例如，计算斐波那契数列的递归函数可以定义如下：```int fibonacci(int n) {if (n <= 1) {return n;}else {return fibonacci(n - 1) + fibonacci(n - 2);}}```在这个例子中，当n小于或等于1时，递归终止，返回n的值。
如果n大于1时，递归调用fibonacci函数求解f(n-1)和f(n-2)的和。
递归终止条件的确定是函数正确实现的关键之一。
2.转化问题的规模递归通常是为了解决类似于“分而治之”的问题。
通过递归调用将原问题拆分成子问题，并在子问题得到解后合并得到原问题的解。
例如，快速排序算法就是一种递归的排序算法，它的实现如下：```void quick_sort(int arr[], int left, int right) {if (left < right) {int pivot = partition(arr, left, right);quick_sort(arr, left, pivot - 1);quick_sort(arr, pivot + 1, right);}}int partition(int arr[], int left, int right) {int pivot = arr[right];int i = left - 1;for (int j = left; j < right; j++) {if (arr[j] <= pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[right]);return i + 1;}```在这个例子中，快速排序通过递归调用将原问题拆分为更小的子问题，并在子问题解决后进行合并。
递归分析和分治算法递归分析一般利用的方法是主定理，辅助的方法有替换法，递归树方法~主定理：递归树：主定理的证明可以通过递归树的方法进行；主定理适用的范围比较局限，有些情况不能被包括，这些情况就需要利用递归树的方法了，主定理的case1是f(n)小于n log b a多项式时间，原定理描述为f(n)=O（n log b a-ε）且ε>0，它与case2中f(n)=Θ(n log b a)中间差一些情况，就是f(n)小于n log b a，但是多余的不是多项式时间；另外就是case2和case3之间相差的部分，就是f(n)大于n log b a，但是如果不大于多项式时间，就不能满足主定理了；另外一种是case3中的f(n)不满足后面的情况；举个例子，如果最近点对中间利用快速排序进行排序，则合并时间nlgn，递归公式T（n）=2T（n/2）+nlgn，这种情况介于case2和case3，所以利用递归树：T（n）=nlgn+n(lgn-lg2)+n(lgn-lg4)+...=nlgnlgn-n(lg2+2lg2+3lg2+...+lgnlg2)=nlgnlgn-nlg2((1+lgn)lgn)/2=nlgnlgn=nlg2n;不过这里我查到mit给的主定理和算法导论有所不同，涵盖了上面的情况，如下：可能这算是一种情况来了；那么这里我在取一个不满足主定理的例子~所以主定理不满足时就利用决策树进行带入吧！如果数学计算能力比较强大还是可以计算出来的，毕竟主定理都是决策树证明的，数学能力不强表示证明有点困难...不过这里有个偷懒的证明方法，直接假设f（n）是一个n k形式的；T（n）=aT（n/b）+n kT（n/b）=aT（n/b2）+（n/b）k...所以T(n)=a（aT（n/b2）+（n/b）k）+n k=n k （1+a/b k+...+(a/b k)h)=(n k-n logba)/(1-a/b k),接下来讨论a和b k的关系决定了为n k还是n logba，上面如果为1则为n k log b n了。
传统基本算法（迭代、递归、分治）一，迭代与递推1）迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
迭代算法一般用于数值计算。
迭代法应该是我们早已熟悉的算法策略，程序设计语言课程中所学的累加、累乘都是迭代算法策略的基础应用。
例如：斐波那契数列例子：兔子繁殖问题一对兔子从出生后第三个月开始，每月生一对小兔子。
小兔子到第三个月又开始生下一代小兔子。
假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。
·问题分析因为一对兔子从出生后第三个月开始每月生产一对小兔子，则每月新下生的小兔子的对儿数显然由前两个月的小兔子的对儿数决定。
则繁殖过程如下：一月二月三月四月五月六月 ……1 1 1+1=2 2+1=3 3+2=5 5+3=8 ……·数学建模（斐波那契数列）y1=y2=1，yn=yn-1+yn-2，n=3，4，5，……2）倒推法的概念·倒推法：是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。
例如，在不知前提条件的情况下，由结果倒过来推解它的前提条件，从而求解问题。
又如，由于存储的要求，而必须从后向前进行推算。
另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法，则问题容易理解和解决。
例子：穿越沙漠问题用一辆吉普车穿越1000公里的沙漠。
吉普车的总装油量为500加仑，耗油率为1加仑/公里。
由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。
该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。
·问题分析贮油点问题要求要以最少的耗油量穿越沙漠，即到达终点时，沙漠中的各临时油库和车的装油量均为0。
这样只能从终点开始向前倒着推解贮油点和贮油量。
·数学模型根据耗油量最少目标的分析，下面从后向前分段讨论。
第一段长度为500公里且第一个加油点贮油为500加仑。
