引言:据说一群在毕达哥拉斯领导下工作的古希腊数学家,发现了数字系列1,3,6,10,15,21...
中有一种奇特的联系。你能知道这个数字的系列的下一个数字是什么吗?
给你一点思考的时间,在这里停下来得出你自己的想法并验证你的结论,别往下偷看哦。
当我看到这个数字系列时我想起了中学时找通项公式的方法:
(你可以先采用归纳法,不一定一次就能找出来,贵在参与。。。)
第一项的值为初始值: n=1,f(1)=1;
第二项的值: n=2,f(2)=f(1)+2=1+2=3;
第三项的值: n=3,f(3)=f(2)+3=3+3=6;(靠谱O(∩_∩)O~)
第四项的值: n=4,f(4)=f(3)+4=6+4=10;(靠谱,不过继续)
第五项的值: n=5,f(5)=f(4)+5=10+5=15;
..........
..........
第N项的值: n=n,f(n)=f(n-1)+n;
基本上已经找出规律来了吧,你也可以采用数学归纳法来证明一下你的结论,说到这里,真有点怀念中学时代啊。
不过我想大多数人都不会那么去做?
How to do?Let computer just do it!
A.用循环证实你的想法:
public int triangle(int n){
int total=0;
while(n>0) //直到n=0
{
total=total+n;
--n;
}
return total;
}
这个循环一直做了n次,直到n=0时exit
B.使用递归查找第N的值:
递归用一种形象的说法,就是推卸责任给别人,比如说,Marry问你道小学数学题,她很高兴地拿着
漫画版数学课本来问你:“哥哥,n=1,f(1)=1...,n=8,f(8)=f(7)+8;n=9,f(9)=?"
而你说:"Marry,你告诉我f(8)的值,我就告诉你f(9)的值。。。"
结果Marry就哭着去告诉妈妈说我欺负他。
妈妈过来看见我正在玩游戏,有点不高兴,于是我赶快用计算机给她算了算,并偷偷对Marry说:
What is f(9)?Let computer just do it and tell us!
其实我什么也没做,这一切全是Marry以及出这道题的人告诉你的答案!
public int triangle(int n){
return (n + triangle(n-1));
}
在计算机里运行一下你也许会发现一个问题,就是它并没有给你返回一个结果,而是无限的循环下去。。。
没有答案,怎么办?
推卸责任是不对的...
How to do?
C.不推卸责任:
为了防止无限重复推卸责任,使你的计算机陷于无法自拔的境地,你只需要找到JUST one!
也就是当n=1的时候,f(1)=1是知道的,你仅仅要做的就是找到f(1)帮你解围,而不是无限的推卸责任和扯皮!
所以推卸责任到此为止,STOP here!
public int triangle(int n){
if(n==1)
return 1;
else
return (n + triangle(n-1));
}
说明:每一个递归方法都有一个基值(终止)条件,此时我们称为基值情况。
上面就是我们经常遇到的三角数字的应用。
D.总结一下递归方法特征:
(1)调用自身。
(2)当它调用自身的时候,它这样做是为了解决更小的问题,这也是一种分治策略。
(3)总存在某个足够简单的问题的层次,在这一层算法不需要推卸责任就可以直接解答且返回结果。
E.递归方法有效率吗?
递归就是程序设计中的数学归纳法。
人们掌握了递归方法之后,常常采用递归,是因为它从概念上简化了问题,它采取分治的策略,使规模化小,
从而变得更加简单,而不是因为本质上更有效率。
这个方法的大规模调用,对CPU和内存都有额外的开销。它需要在系统内存空间存储所有的中间参数以及返回值,
如果大量的数据需要存储,就会引起栈溢出的问题。当大规模自身方法调用时可考虑消除递归。
下回将讨论这个问题,以及汉诺塔问题,递归的二分查找,变位字的全排列问题。。。Sleeping
分享到:
相关推荐
递归与分治策略是学习计算机算法设计与分析的基础,掌握了这样的思想才能良好地高效率地去解决一些问题
对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止
理解递归的概念 掌握设计有效算法的分治策略:分治法的基本思想 通过范例学习分治策略的算法分析及设计技巧 二分搜索技术、大整数的乘法、Strassen矩阵乘法 合并排序和快速排序
计算计算法课件。递归与分治的思想以及几个经典问题
算法设计与分析实验报告:递归与分治策略,用python写的,附源码。主要处理问题如下: 1.ackerman函数实现; 2.大数划分; 3. 数据集合{1,2,3,4,5,6,7,8,9,10}的排列组合;
1. 编程实现整数的划分问题的递归算法 3. 编程实现特殊棋盘覆盖问题的求解
本资源是从众多学生中选取出来的优秀范例,运行效率较高,包含完整可执行代码和详细算法...范例中包含了士兵战队,集合划分等5个基于递归与分治策略算法实现的问题,每个范例都有详尽代码和算法分析PPT!学习的好材料。
递归与分治实验(二)Problem A:再次Hanoi塔问题Problem B:输油管道问题Problem C:Integer FactorizationProblem D:邮局选址问题Problem E:Gray code
在一个2的k次方乘以2的k次方个方格的棋盘中,恰有一个方格与其他方格不同为特殊方格,棋盘称为特殊棋盘,用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
算法中的递归与分治策略,这是老师上课的讲课的时候用的PPT,觉得不错!
C 语言程序设计:递归与分治策略.ppt
c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构 五大常用算法
深入理解分治法的算法思想,应用分治法解决实际的算法问题。 【实验性质】 验证性实验(学时数:2H) 【实验内容与要求】 1、设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:⑴每个选手...
递归与分治策略课件.pptx
C++语言程序设计:递归与分治策略.ppt
算法设计与分析:第02章 递归与分治策略.ppt
递归与分治策略讲义课件.pptx