《ACM课件(lecture04)递推求解课件》由会员分享，可在线阅读，更多相关《ACM课件(lecture04)递推求解课件（39页珍藏版）》请在金锄头文库上搜索。
1、ACM ACM 程序设计程序设计计算机学院计算机学院 刘春英刘春英7/19/20241ACM课件(lecture04)递推求解今天，今天，你 了吗？AC7/19/20242ACM课件(lecture04)递推求解每周一星（每周一星（2）：）：水域浪子水域浪子 7/19/20243ACM课件(lecture04)递推求解第三讲第三讲 递递 推推 求求 解解7/19/20244ACM课件(lecture04)递推求解先来看一个先来看一个超级超级简单的简单的例题例题:l有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他
2、10岁，最后求第5个人多少岁？l如果所坐的不是5人而是n人，写出第n个人的年龄表达式。 7/19/20245ACM课件(lecture04)递推求解显然可以得到如下公式显然可以得到如下公式: :化简后的公式:F(n)=10+(n-1)*27/19/20246ACM课件(lecture04)递推求解再来一个简单题再来一个简单题: :7/19/20247ACM课件(lecture04)递推求解再来一个简单题再来一个简单题: :蟠桃记7/19/20248ACM课件(lecture04)递推求解递推公式递推公式? ?lF(n)=(F(n-1)+1)*27/19/20249ACM课件(lecture04
3、)递推求解Fibnacci Fibnacci 数列：数列：即：1、2、3、5、8、13、21、347/19/202410ACM课件(lecture04)递推求解思考思考: :l递推公式的伟大意义？l有了公式，人工计算的方法？l常见的编程实现方法？（优缺点？）7/19/202411ACM课件(lecture04)递推求解简单思考题简单思考题: :l在一个平面上有一个圆和在一个平面上有一个圆和n条直条直线，这些直线中每一条在圆内同线，这些直线中每一条在圆内同其他直线相交，假设没有其他直线相交，假设没有3条直条直线相交于一点，试问这些直线将线相交于一点，试问这些直线将圆分成多少区域。圆分成多少区域。
4、7/19/202412ACM课件(lecture04)递推求解是不是这个是不是这个F(1)=2;F(n)=F(n-1)+n;化简后：F(n)=n(n+1)/2+1;7/19/202413ACM课件(lecture04)递推求解太简单了太简单了? ?来个稍微麻烦一些的来个稍微麻烦一些的7/19/202414ACM课件(lecture04)递推求解例例: : （20502050）折线分割平面）折线分割平面问题描述问题描述： 平面上有平面上有n n条折线，问这些折线最多能将平面分条折线，问这些折线最多能将平面分割成多少块割成多少块? ?样例输入样例输入1 12 2样例输出样例输出2 27 77/19
5、/202415ACM课件(lecture04)递推求解思考思考2 2分钟分钟: :如何解决如何解决? ?7/19/202416ACM课件(lecture04)递推求解结论结论: :lZn=2n(2n+1)/2+1-2n=2n2n+1为什么为什么? ?7/19/202417ACM课件(lecture04)递推求解趁热打铁，趁热打铁，来个差不多的来个差不多的7/19/202418ACM课件(lecture04)递推求解说起佐罗，大家首先想到的除了他脸上的面具，说起佐罗，大家首先想到的除了他脸上的面具，恐怕还有他每次刻下的恐怕还有他每次刻下的“Z”“Z”字。我们知道，一字。我们知道，一个个“Z”“Z
6、”可以把平面分为可以把平面分为2 2部分，两个部分，两个“Z”“Z”可以可以把平面分为把平面分为1212部分，那么，现在的问题是：如果部分，那么，现在的问题是：如果平面上有平面上有n n个个“Z”,“Z”,平面最多可以分割为几部分平面最多可以分割为几部分呢？呢？说明说明1 1：“Z”“Z”的两端应看成射线的两端应看成射线说明说明2 2：“Z”“Z”的两条射线规定为平行的的两条射线规定为平行的附加思考题（还没加到附加思考题（还没加到OJ）：）：“佐罗佐罗”的烦恼的烦恼 7/19/202419ACM课件(lecture04)递推求解总结：递推求解的基本方法：总结：递推求解的基本方法：l首先确认，是
7、否能很容易的得到简单情况的解l假设规模为N-1的情况已经得到解决l重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。l强调：1、编程中的空间换时间的思想2、并不一定是从N-1到N的分析7/19/202420ACM课件(lecture04)递推求解问题的提出：问题的提出： 设有设有n n条封闭曲线画在平面上，而任条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。闭曲线把平面分割成的区域个数。思考题
8、：平面分割方法思考题：平面分割方法7/19/202421ACM课件(lecture04)递推求解11324123465781234567108911121314n=1n=2n=3n=4F(1)=2F(n)=F(n-1)+2(n-1)7/19/202422ACM课件(lecture04)递推求解某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。 1465 1465 不容易系列之一不容易系列之一7/19/202423ACM课件(lecture04)递推求解分析思路：分析思路：1、当有N封信的时候，前面N-1封信可以有N-1或者N-2封错装3、后者简单，只
9、能是没装错的那封信和第N封信交换信封，没装错的那封信可以是前面N-1封信中的任意一个，故=F(N-2)*(N-1)2、前者，对于每一种错装，可以从N-1封信中任意取一封和第N封错装，故=F(N-1)*(N-1)7/19/202424ACM课件(lecture04)递推求解得到如下递推公式：得到如下递推公式：基本形式：d1=0; d2=1递归式：dn= (n-1)*( dn-1 + dn-2)这就是著名的错排公式这就是著名的错排公式7/19/202425ACM课件(lecture04)递推求解在在2n2n的一个长方形方格中的一个长方形方格中, ,用一个用一个1 21 2的骨牌铺满方格的骨牌铺满方
10、格, ,例如例如n=3n=3时时, ,为为2 32 3方格，骨牌的铺放方案有三种方格，骨牌的铺放方案有三种( (如图如图),),输入输入n ,n ,输出铺放方案的总数输出铺放方案的总数思考题（思考题（2046）：）：7/19/202426ACM课件(lecture04)递推求解有有1n1n的一个长方形，用的一个长方形，用1111、1212、1313的骨牌铺满方的骨牌铺满方格。例如当格。例如当n=3n=3时为时为1313的方格，此时用的方格，此时用1111，1212，1313的骨牌铺满方格，共有四种铺法。如图的骨牌铺满方格，共有四种铺法。如图 输入输入 n n（0=n=300=n3)然后就是对n
11、=3的一些特殊情况的处理了，显然：F(0)=1(没有人也是合法的，这个可以特殊处理，就像0的阶乘定义为1一样)F(1)=1F(2)=2F(3)=47/19/202432ACM课件(lecture04)递推求解有排成一行的个方格，用红有排成一行的个方格，用红(Red)(Red)、粉、粉(Pink)(Pink)、绿、绿(Green)(Green)三色涂每个格子，每三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色求全部的满足要求且首尾两格也不同色求全部的满足要求的涂法的涂法. .附加思考题：附加思考题：不容易系列之不容易系列之(3)(3
12、) LELE LELE的的RPGRPG难题难题 7/19/202433ACM课件(lecture04)递推求解一把钥匙有一把钥匙有N N个槽，个槽，2N262N26槽深为槽深为1 1，2 2，3 3，4,5,64,5,6。每钥匙至少有。每钥匙至少有3 3个不同的深度且相连的槽个不同的深度且相连的槽其深度之差不得为其深度之差不得为5 5。求这样的钥匙的总数。求这样的钥匙的总数。 本题无输入本题无输入对对2N262N26，输出满足要求的钥匙的总数。，输出满足要求的钥匙的总数。附加思考题：附加思考题：1480_1480_钥匙计数之二钥匙计数之二 7/19/202434ACM课件(lecture04)
13、递推求解详见解题报告：详见解题报告：l仔细阅读，耐心品味，关键掌握从n-1到n的推导过程。7/19/202435ACM课件(lecture04)递推求解Any question?7/19/202436ACM课件(lecture04)递推求解HDOJ作业：作业：1290献给杭电五十周年校庆的礼物献给杭电五十周年校庆的礼物1297ChildrensQueue1438钥匙计数之一钥匙计数之一1465不容易系列之一不容易系列之一1466计算直线的交点数计算直线的交点数1480钥匙计数之二钥匙计数之二2013蟠桃记蟠桃记2018母牛的故事母牛的故事2041超级楼梯超级楼梯2042不容易系列之二不容易系列之二20442050(10/5专题练习专题练习)7/19/202437ACM课件(lecture04)递推求解课后一定课后一定要练习！要练习！7/19/202438ACM课件(lecture04)递推求解See you next week.Thank you! 7/19/202439ACM课件(lecture04)递推求解
