企业建设网站的步骤是什么意思,图片转二维码在线制作生成器,电子鲜花php网站怎么做,网站成立时间查询0 回顾
之前的笔记#xff08;0#xff09;和笔记#xff08;1#xff09;#xff0c;我们介绍了算法的基本含义#xff0c;并且举了一些实例#xff0c;同时理解了#xff0c;算法就是人类在教计算机做事情#xff01;
我们知道#xff0c;算法就是解决问题的方案…0 回顾
之前的笔记0和笔记1我们介绍了算法的基本含义并且举了一些实例同时理解了算法就是人类在教计算机做事情
我们知道算法就是解决问题的方案我们将自然语言描述的问题转换为符号语言再解决问题使用计算机思维构建解决问题的算法最后转换为计算机可以识别的语言教会计算机让它帮助我们解决问题。
在算法设计的时候我们需要关注其时间和空间的复杂度这与实际问题有关可能关注事件也可能关注空间也可能二者兼有。
下面我们来看看递归思想并且使用实例来理解抽象的思想。
1 递归思想
递归是可能计算机与人类最大的不同人类是递推思维能够发散计算机是递归思维能够做重复且简单的固定事情。
因此我们教计算机做事的时候要尽可能简单且固定也就是我们需要将一个复杂的问题拆解成若干小问题这些小问题最好还是已知的已经被解决的这样我们就很容易能够设计出一个算法并且教会计算机做事。
1.1 递归的含义
所谓的递归看起来就像同样的一件事情做了很多遍虽然每一次的代码一样但是每一次的数据不一样导致行为不一样并且会有一个尽头一旦走到尽头了就得原路返回来。
我们看一个例子
#include iostream
using namespace std;void story(int i) {if (i 10)return;cout 从前有个庙庙里有个老和尚老和尚给小和尚讲故事 endl;cout 讲的故事是什么呢讲的是 endl;story(i 1);
}int main()
{story(1);return 0;
}这就是生活中的一个递归的例子还蛮有趣的
注意它并不是循环与循环还是有差别的最重要的就是递归在条件终止之后会返回来而循环条件终止就停了。
1.2 递归算法的重要结构
终止条件 终止处理办法递归处理方法 我们知道递归不可能无限进行下去因此需要终止条件以及触发该条件后对应的处理方案。
并且更重要的是我们需要知道递归如何处理。
对于递归程序通常都是解决一个小问题。
我们将一个大问题分解成若干个小问题然后这些小问题的处理方式是相似的我们用递归来分别解决每一个小问题得到每个小问题的解之后将这些解合并。
阶乘问题 先列出递归方程再转换为程序即可。
// 阶乘问题
int factorial(int n) {if (n 0)return 1;elsereturn n * factorial(n - 1);
}如果不用递归呢
使用递推 从1到n.用循环搞定。
// 不用recursion的阶乘递推
int factorial2(int n) {if (n 0)return 1;int result 1;for (int i 1; i n; i) {result * i;}return result;
}递归特点有去有回从n到1从结果到起点再返回来。
对于递归来说最开始目标的n就是已知的然后逐渐变化到临界值经过层层处理再返回来。关键点递归方程
斐波那契数列
递归方程
f(n) 1n 1或n 0f(n) f(n-1) f(n-2)n 1
// 斐波那契数列
int fib(int n) {if (n 1 || n 0)return 1;return fib(n - 1) fib(n - 2);
}迭代就是重复执行一些指令指令是一定的但是相关的数据是变化的。
递归调用的过程终点参数在不断变化一直在逼近终点最终停下来依次返回。
小结
我们先将一个问题使用符号语言描述拆解问题将其转换成递归方程使用数学语言描述然后将其转换为算法和实际的程序。
所谓的递归就是先给出终点参数它是复杂的然后随着参数的减小会逐渐简单然后得到最简单的结果之后再往回走就能获得复杂问题的结果。
这与人类思维不一样人类通常是递推先解决简单问题再逐渐复杂化最终解决复杂问题。
因此求解问题的时候可以简单问题找规律最终获得复杂抽象的方程从而获得最终结果。
