2010.11第二次宏福讲座

《2010.11第二次宏福讲座》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、byyu_zhuoran@sap引入了解递推引入首先，给大脑热热身一道简单题BOJ1417Cloudiris'sFlower引入clourdiris是一个非常非常喜欢花的人（比较学术的说法是花痴），她的生日要到了，他的队友dalong和champ准备送给她一个特别的礼物：一种叫Tracer的神奇的花。这种花第一年不能结种子，从第二年开始每株每一年都会结一个种子。假设所有的种子能瞬间张出苗来,转年就可以结果，问第N年cloudiris的花棚能有多少株Tracer花。(cloudiris收到花种子的年是第

2、一年，假设所有的花都不会死亡)Sourcecloudirs@tracer题目作者：郝宵虹@tracer引入Fibonacci养了好多兔子唉~引入Fibonacci数列的定义：F[1]=1;F[2]=1;当n>=3时F[n]=F[n-1]+F[n-2];大家看懂了么？引入Fibonacci数列的定义：F[1]=1;F[2]=1;当n>=3时F[n]=F[n-1]+F[n-2];大家看懂了么？这既是高中时就学习过的数学定义，即递推式。递推：可以从数列的初始值开始，通过数列的递推关系求出数列的每一项~（当

3、然，在计算机上还有时间和空间的要求:p）引入我们通过学习了一维数组就可以搞定Fibonacci数列啦~~happyintF[30],n;//为什么开的大小是30？memset(F,0,sizeof(F));//这句话什么意思？需要么？F[1]=F[2]=1;for(inti=3;i<=29;i++)F[i]=F[i-1]+F[i-2];while(scanf(“%d”,&n)!=EOF)//这是什么？printf(“%d”,F[n]);引入我们通过学习了一维数组就可以搞定Fibonacci数列啦~

4、~happy我们知道计算机是支持二维数组的。我们是不是可以类似求二维的数列呢？想一想引入我们知道计算机是支持二维数组的。我们是不是可以求二维的数列呢？想一想曾经学习过的二维数列？对啦！组合数C(n,r)组合数的递推关系是杨辉三角(PascalTriangle)C(n,r)=C(n-1,r-1)+C(n-1,r)初始条件是什么？应该用怎样的递推顺序？自己想一想这是一道作业题哦引入补充知识，同余模运算def：A=B(modC)即A%C==B%C<=>A和B除以C的余数相等性质：(a+b)%c==a%c+b

5、%ca*b%c==(a%c)*(b%c)组合数的递推变成C(n,r)%mod=(C(n-1,r-1)+C(n-1,r))%mod引入小结从上面的两个例子中我们学会了什么？a.数组—数列之间的关系？两个领域的不同称谓。b.递推求解：找到初值与递推关系；c.一维，二维，高维。d.求解高考时搞死我们的数列题目建模与求解简单的动态规划建模与求解我们现在已经学会了如何递推求解数列了，可以大展伸手了么？还不可以哦~ACM的题目可不会把递推公式赤裸裸地摆在你面前，需要由我们自己定义高效的状态，即数列对应含义；挖掘数

6、据间的关系找到递推式。建模与求解这就需要我们建立合适的数学模型进入建模一节我们将从几道经典例题入手了解如何建模1.0/1背包2.无穷背包3.最长上升子序列4.魂斗罗5.ACM的选拔6.盛大派对建模例题一：背包问题背景简介它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品

7、，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题

8、，即在总重量不超过W的前提下，总价值是否能达到V？建模与求解当然，我们暂时不用学那么难。我们只需要先解决最简单的0/1背包问题BNUoj4183Description给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。Input第一行n C,表示物品个