程序设计基础11_1_递推.ppt

第11章 递推与递归;主要内容; Fibonacci数列问题： f(1)=0 f(2)=1 边界 f(n)=f(n-1)+f(n-2) 递推关系式 简洁高效的常见数学模型。 特点：每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有关联——递推关系式。 求解方法： 从初始的一个或若干个数据项出发——边界 通过递推关系逐步推进得到最终结果——递推法;解决递推问题有三个重点：;举例 猴子第1天摘下若干个桃子,当即吃了一半又一个。第2天又把剩下的桃吃了一半又一个,以后每天都吃前一天剩下的桃子的一半又一个,到第10天猴子想吃时,只剩下一个桃子。 问猴子第1天一共摘了多少桃子? ; 举例 猴子分食桃子 五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。 不过，就在半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。 第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。 第三只，第四只，第五只猴子都依次如此分食桃子。 那么桃子数最少应该有几个呢？;#include stdio.h int main() { int x,s,k,i; x=6; k=0; //整除标志 while ( k!=4) { s=x; k=0; for ( i=4; i=1; i--) { if ( s%4 ==0) k++; else break; s=s*5/4+1; } x=x+5; } printf(s=%d\n,s); return 0； };首先，用数组f(i)来存储第i年的母牛总数，则第n年的母牛总数为f(n)。 F(n)只与两个值有关： 一是在本年之前就已经出生的母牛数目； 二是在本年新出生的小母牛数目。;递推公式： f(n)=f(n-1)+f(n-3) (n=4) 递推的边界条件：第1、2、3年母牛总数可知 f(1)=1 f(2)=2 f(3)=3;举例 骨牌问题 在2×n的长方形方格中，用n个1×2的骨牌铺满方格，输入n ，输出铺放方案的总数。  例如 n=3时，为2×3方格，骨牌的铺放方案有三种方法，如下图所示：;长度为n时的骨牌铺放方案不容易直接得到，可以从最简单的情况开始寻找问题解决的规律——递推解决问题的基本途径。 以f(i)表示长度为i时的铺放方案数目 当n=1时，只能是一种铺法，即f(1)= 1，如下左图所示。 当n=2时，只能是两种铺法，即f(2)= 2，如下右图所示。;n=3时骨牌的铺放方案有三种方法，如下图所示：;对于一般的n值，其第一块骨牌的铺法也只有两种可能，横铺或者竖铺: ;顺推法; 设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，求从底层开始走完全部楼梯有多少种走法。（例如：当n=3时，共有4种走法， 即1+1+1，1+2，2+1，3 ） ; 算法分析： n的值?? 走法 1????? 1 2????? 2 3 4 4 7 从递推的思想出发，可以设想，从第4项开始，每1项等于前面3项的和。;#include stdio.h void main( ) { int x,n,i,a,b,c; scanf(%d,n); a=1; b=2; c=4; if (n==1) x=1; else if (n==2) x=2; else if (n==3) x=4; for (i=4; i=n; i++) { x=a+b+c; a=b; b=c; c=x; } printf(%d,x); } ;例5 错排公式 某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封，共有多少种不同情况？ 对n封信以及n个信封各自按照从1到n进行编号， f（n）表示当n个编号的信放在n个编号位置的信封，信的编号与信封位置编号各不对应的方法数； 类似，f（n-1）表示n-1个编号的信放在n-1个编号位置的信封，各不对应的方法数。 其它类推。 ;;;例