C语言-递推求解

ACM程序设计福州大学至诚学院冯新2024/5/161第五讲递推求解2024/5/162先来看一个超级简单的例题:有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第5个人多少岁？如果所坐的不是5人而是n人，写出第n个人的年龄表达式。

2024/5/163显然可以得到如下公式:化简后的公式:F(n)=10+(n-1)*2f[n]=f[n-1]+2f[1]=102024/5/164Fibnacci数列：Description2009年到来了。经过2008年一年的修炼，数学神童倩倩终于把0到30的Fibonacci数列(f[0]=0,f[1]=1;f[i]=f[i-1]+f[i-2](i>=2))的值全部给背了下来。接下来，Ths决定要考考他，于是每问他一个数字，他就要把答案说出来，可是Ths自己又记不住。于是他决定编写一个程序来测验倩倩说的是否正确。Input输入若干数字n(0<=n<=30)，每个数字一行。读到文件尾。Output输出f[n]。SampleInput012345SampleOutput0112352024/5/165Fibnacci数列：即：0、1、1、2、3、5、8、13、21、34…f[0]=0f[1]=1f[n]=f[n-1]+f[n-2]2024/5/166Fibnacci数列：#include<stdio.h>intmain(){

intf[40];f[0]=0;f[1]=1;

for(inti=2;i<=30;++i){

f[i]=f[i-1]+f[i-2];}

intk;

while(scanf("%d",&k)!=EOF&&k!='\n'){

printf("%d\n",f[k]);}return0;}2024/5/167简单思考题:在一个平面上有一个圆和n条直线，这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。2024/5/168我们先来看一下N条相交的直线最多能把平面分割成几块。很明显，当添加第n条直线时，为了使平面最多，则第n条直线要与前面n-1条直线都相交，且没有任何三条线交于一个点。这样，第n条直线一共有n-1个交点。我们知道，增加n个焦点，则增加n+1个平面。所以n条直线分割平面最大数是f(n)=f(n-1)+n或f（n）=1+1+2+3+...+n=(n2+n+2)/22024/5/169是不是这个——F(1)=2;F(n)=F(n-1)+n;化简后：F(n)=n(n+1)/2+1;2024/5/1610太简单了?来个稍微麻烦一些的

2024/5/1611例:（2050）折线分割平面问题描述：平面上有n条折线，问这些折线最多能将平面分割成多少块?样例输入

1 2样例输出

2 72024/5/1612例:（2050）折线分割平面我们不忙着解这道题。我们先来看一下N条相交的直线最多能把平面分割成几块。很明显，当添加第n条直线时，为了使平面最多，则第n条直线要与前面n-1条直线都相交，切没有任何三条线交于一个点。这样，第n条直线一共有n-1个交点。我们知道，增加n个焦点，则增加n+1个平面。所以n条直线分割平面最大数是f(n)=f(n-1)+n或f（n）=1+1+2+3+...+n=(n2+n+2)/22024/5/1613例:（2050）折线分割平面我们再来看看，每次增加的不是一条直线，而是两条相互平行的线，那又如何呢？当第N次添加时，前面已经有2N-2条直线了，按我们上面讨论的知道，第N次添加时，第2N-1条直线和第2N条直线各能增加2(n-1)+1个平面。所以第N次添加增加的面数是2[2(n-1)+1]=4n-2个。2024/5/1614例:（2050）折线分割平面再来看如果把每次加进来的平行边让它们一头相交，情况又如何呢？我们看到，平面1、3已经合为一个面，既少了一个面。因此，每当一组平行线相交后，就会减少一个面。因此，本题所要求的折线分割平面，自然就是上面求的的平行线分割平面数减去N即增加4n-3个。2024/5/1615思考:如何用递推解决?结论——F(n)=F(n-1)+4n-3F(0)=12024/5/1616另外一种结论:Zn=2n(2n+1)/2+1-2n =2n^2–n+1为什么?2024/5/1617#include<stdio.h>intmain(){

intn,i,j,f0,f1;

scanf("%d",&i);while(i--&&scanf("%d",&n)) {f0=1; for(j=1;j<=n;j++){f1=f0+4*j-3;f0=f1;}

printf("%d\n",f1);}return0;}2024/5/1618#include<stdio.h>intmain(){

intn,i;

scanf("%d",&i);while(i--&&scanf("%d",&n))

printf("%d\n",2*n*n-n+1);return0;}2024/5/1619总结：递推求解的基本方法：首先，确认：能否容易的得到简单情况的解？然后，假设：规模为N-1的情况已经得到解决。最后，重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。2024/5/1620问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。思考题：平面分割方法2024/5/1621F(1)=2F(n)=F(n-1)+2(n-1)简单分析——11324123465781234567108911121314n=1n=2n=3n=422024/5/1622在2×n的长方形方格中,用n个1×2的骨牌铺满方格,例如n=3时,为2×3方格，骨牌的铺放方案有三种(如图),输入n,输出铺放方案的总数思考题（204