如何用生成函数求解递归方程f(n)=2f(n/2)+cn
解：
令f(1)=c
f(2)=2c+2
f(4)=2(2c+2)+4 = 4c+8
f(8) = 2(4c+8)+8 = 8c+24
f(16) = 2(8c+24)+16 = 16c+64
f(2^k) = c*2^k + P(k)
考虑P(k)
P(0) = 0
P(1) = 2 *P(0) + 2
P(2) = 2*P(1)+4
p(n-2) = 2*P(n-3)+2^(n-2)
p(n-1) = 2*P(n-2)+2^(n-1)P(n)
= 2* P(n-1) + 2^n = 2*2*P(n-2)+2*2^(n-1)+2^n
= 4P(n-2)+2*2^n
= 4*2P(n-3)+4*2^(n-2)+2*2^n
归纳得到P(n) = 2^kP(n-k)+k*2^n = 2^nP(n-n)+n*2^n =n*2^n
所以P(n-1) = (n-1)2^(n-1)
2*P(n-1)+2^n = 2*(n-1)*2^(n-1) + 2^n=P(n) 得到验证
带回f(2^k)得到f(2^k) = c*2^k+k*2^k，对于任意常数c成立
扩展资料性质：
1、 子问题须与原始问题为同样的事，且更为简单。
2、不能无限制地调用本身，须有个出口，化简为非递归状况处理。
3、由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
4、递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
#include double a(double x,int n) { if(n==0) return 1; else if(n==1) return x; else return a(x,n-1)*x/n; } int main() { double x; int n; scanf("%lf%d",&x,&n); printf("%lf
",a(x,n)); return 0; }
解：
令f(1)=c
f(2)=2c+2
f(4)=2(2c+2)+4 = 4c+8
f(8) = 2(4c+8)+8 = 8c+24
f(16) = 2(8c+24)+16 = 16c+64
f(2^k) = c*2^k + P(k)
考虑P(k)
P(0) = 0
P(1) = 2 *P(0) + 2
P(2) = 2*P(1)+4
p(n-2) = 2*P(n-3)+2^(n-2)
p(n-1) = 2*P(n-2)+2^(n-1)P(n)
= 2* P(n-1) + 2^n = 2*2*P(n-2)+2*2^(n-1)+2^n
= 4P(n-2)+2*2^n
= 4*2P(n-3)+4*2^(n-2)+2*2^n
归纳得到P(n) = 2^kP(n-k)+k*2^n = 2^nP(n-n)+n*2^n =n*2^n
所以P(n-1) = (n-1)2^(n-1)
2*P(n-1)+2^n = 2*(n-1)*2^(n-1) + 2^n=P(n) 得到验证
带回f(2^k)得到f(2^k) = c*2^k+k*2^k，对于任意常数c成立
扩展资料
性质：
1、 子问题须与原始问题为同样的事，且更为简单。
2、不能无限制地调用本身，须有个出口，化简为非递归状况处理。
3、由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
4、递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
对于形式如f(n)=g(n)f(n-1)+h(n)的递归方程，可利用递推关系得到：
f(n)=g(n)f(n-1)+h(n)
=g(n)g(n-1)g(n-2)....g(1)g(0)[f(0)+ sum[ h(i)/g(i)g(i-1)...g(1)] ]。其中，sum表示i从1到n求和。
对上面的式子，可以设n=2^k，则k=logn。则有：
f(k)=2f(k-1)+c2^k
直接应用公式，得：
f(k)=2^k[ c*sum(2^i/2^i) ]
=2^k*c*k
=cnlogn
如何用生成函数求解递归方程H(n)=H(n-1)+9H(n-2)-9H(n-3),n>2 H(0...
用C吗？不是很难的哦，不过只有五分，有谁愿意敲那么多东西啊
什么是生成函数?
详情请查看视频回答
斐波那契(Fibonacci)数列(3):生成函数
本文以分析工具，探讨斐波那契数列的生成函数法。生成函数法是组合数学中常用技巧，借函数处理数列问题。设斐波那契数列为：F(0)=0, F(1)=1, 定义生成函数为G(x)=F(0) + F(1)x + F(2)x^2 + F(3)x^3 +...基于斐波那契数列的递推公式，我们构造方程求G(x)表达式。易得G(x) = x ...
斐波那契数列相关问题精讲
方法4：生成函数(generating function)，也称为母函数法 以斐波那契数列通项为例，逐一展示以上方法 方法1：公式 待定系数得到公式 的通项公式后继续凑等比数列即可。方法2：递推公式可以当作为一个差分方程看待。有关差分方程的知识可以参考此文 其对应的特征方程为公式 故公式 将公式 代入可以解得 ...
离散数学这门课程第九章递推关系和生成函数的知识点有哪些?
离散数学这门课第九章递推关系和生成函数的知识点包含章节导引,第一节递推关系,第二节求解常系数线性递推关系,第三节生成函数,课后巩固,。
生成函数的介绍
最早提出母函数的人是法国数学家LaplaceP.S.在其1812年出版的《概率的分析理论》中明确提出。 生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多。 生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项，生成函数是推导Fibonacci数列...
如何求解高次递推数列的通项?
就可以得到数列的通项公式。例如，如果我们求出的解是an=(C1+C2*n)*e^(C3*n)，那么数列的通项公式就是an=(C1+C2*n)*e^(C3*n)。需要注意的是，这种方法只适用于一些特殊的高次递推数列，对于一般的高次递推数列，可能需要运用到更复杂的方法，如生成函数法、矩阵法等。
母函数——生成函数——形式级数(Generating function)
计数问题的艺术：水果篮的奇妙计数法，乘法原理的巧妙应用 - 从简单到复杂，母函数让你轻松应对计数难题。集合计数的高级技巧：子集与元素和，通过母函数一网打尽 - 子集的基本定理，结合母函数，让你洞察集合的深层结构。母函数在递推、计数及集合问题的舞台，犹如璀璨的星辰，照亮解决问题的路径...
【python】生成器是什么?怎么用?能干啥?
在Python中，生成器是一种高效迭代的工具，它是一种特殊的函数，通过yield关键字实现延迟计算和内存节省。生成器函数不同于普通函数，它会在每次迭代时暂停执行，只返回一个值，然后保存状态，等待下一次迭代。创建生成器的方式有两种：生成器表达式，类似列表推导式但用小括号();以及生成器函数，只需将...
c语言函数递归(实现原理与应用场景)
递归的实现原理 递归函数的实现原理可以通过以下步骤来理解：1.函数调用自身，将问题分解成更小的子问题。2.子问题可以通过调用函数本身来解决。3.当子问题足够简单时，可以直接解决，不需要再次调用函数本身。4.将子问题的解合并成原问题的解。递归函数的实现原理可以用一个经典的例子来解释：阶乘函数。
童卸雪凝： ^对于形式如f(n)=g(n)f(n-1)+h(n)的递归方程,可利用递推关系得到:f(n)=g(n)f(n-1)+h(n) =g(n)g(n-1)g(n-2)....g(1)g(0)[f(0)+ sum[ h(i)/g(i)g(i-1)...g(1)] ].其中,sum表示i从1到n求和.对上面的式子,可以设n=2^k,则k=logn.则有:f(k)=2f(k-1)+c2^k 直接应用公式,得:f(k)=2^k[ c*sum(2^i/2^i) ] =2^k*c*k =cnlogn
叶县17877323494： 使用递归编写函数,求f(n)当n = 0时,f(n) = 0;当n = 1时,f(n) = 1;当n >= 2时,f(n) = 2f(n - 1) + 3f(n - 2):我只想要题解,只是很想知道这个题目的规律 - ？
童卸雪凝：[答案] int f(int n) { if (n == 0 || n == 1) return n; else return 2 * f(n - 1) + 3 * f(n - 2); } 数学解法如下: 递推方程的特征方程为: x^2=2x+3,解得特征根为x1=-1,x2=3, 从而f(n)=C1*(-1)^n + C2*3^n,再代入f(0)=1,f(1)=1,解得 C1=-1/4, C2=1/4,从而f(n)=-1/4*(-...
叶县17877323494： C语言用递归求函数的第n项f(n) = 1*2 + 2*3 + 3*4 + …… + n*(n+1) - ？
童卸雪凝： #include <stdio.h> int sumn(int n,int *flag) {(*flag)++;if(n==1)return n*(n+1);elsereturn n*(n+1)+sumn(n-1,flag); } int main() {int count=0,result;int n=0;scanf(＂%d＂,&n);if(n>0){result=sumn(n,&count);printf(＂%d\n＂,result);}else{...
叶县17877323494： 设计一个main函数求递归函数f的第m项,其中f(1)=0,f(2)=1,f(n)=f(n - 1)+f(n - 2);谢谢 - ？
童卸雪凝： 看一下吧 void main() { int f(int); int m; scanf(＂%d＂,&m); printf(＂f(%d)=%d＂,m,f(m)); getch(); } int f(int n) { if n==1 return 0; else return f(n-1)+f(n-2); } 希望回答对你有帮助.
叶县17877323494： 递归函数的计算 - ？
童卸雪凝： 数论函数的一种,其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数.处处有定义的函数叫做全函数,未必处处有定义的函数叫做部分函数.最简单又最基本的函数有三个:零函数O(x)=0(其值恒为0);射影函数;...
叶县17877323494： python递归求斐波那契数列前10项 - ？
童卸雪凝： 你好,很高兴为你解答.根据斐波那契数列F(n)=F(n-1)+F(n-2),当n=1和n=2时,F(n)=1,可以利用函数+if分支结构编写递归程序,求出斐波那契数列前10项.具体代码如下: 求斐波那契数列前10项
叶县17877323494： 求解递归方程:(1) f(1)=1;f(n)=2*f(n - 1)+1; - ？
童卸雪凝：[答案] f(1)=1;f(n)=2*f(n-1)+1 f(n-1)=2*f(n-2)+1 (1)f(n-2)=2*f(n-3)+1 (2).f(2)=2f(1)+1 (n-2)f(1)=1 (n-1)(1)x2+(2)x4+.+(n-2)x2^(n-2)+(n-1)x2^(n-1)消去相同的得f(n)=1+2+2^2+.+2^(n-1)f(n)=2^n-1
叶县17877323494： 如何求解像T=2T+nlgn这种递归式 - ？
童卸雪凝： an=2a(n-1)+1+3^n an+1=2[a(n-1)+1]+3^n 如看不出来,方法如下 设an+1-y*3^n=2[a(n-1)+1-y*3^(n-1)] 前面的an带入解得y=3 则an+1-3*3^n=2[a(n-1)+1-3*3^(n-1)] 解方程也用这个方法.你给个例子发我在线
叶县17877323494： 求高手解决一道c语言题目{编写一递归函数fac用来求阶乘t!.主函数调用该函数,求20!}急!!!. - ？
童卸雪凝：#include ＂stdio.h＂ #include ＂conio.h＂main() { float f(int);/* 函数原型 */ int n = 20; float sum; printf(＂Input a number:＂); //scanf(＂%d＂,&n); sum=f(n); printf(＂%d!=%.2f\n＂,n,sum); getch(); }float f(int n) { float sum; if(n<0) printf(＂...
叶县17877323494： 在计算1个算法的时间复杂度时,如何解递归方程? - ？
童卸雪凝： 如果递归表达式符合 T(n) = aT(n/b)+f(n)的形式,则可以首先尝试应用主定理. 如果不可以的话就画递归树,各层求和累加,得到T(n)的表达式.
