猫史档案馆

开始前，先放一个漫画……

“不学数学也能活得很好”可能也是一部分训练师的心态。

但是想要进一步学好编程，“算法”是一定要好好学的。

很多编程猫的训练师都已经完成基本的编程学习了，今天起，我会定期在百科上发帖教大家一些简单的算法和数据结构知识，也会在“图书馆”里直接更新。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

我们先说最简单的一个例子，数学家高斯的故事。

高斯在小时候，曾经被老师罚，让他算出1＋2+3+4+……＋99+100的和。

各位训练师你们如果用计算机来做，会怎么做呢？

可以这样来做：

方案一：直接让1加到100

设定一个变量“数字”，一个变量“和”，

然后执行100次：

和＝和＋数字；（这里左边的和会变成新的结果，后面一个和是原来的总和。）

数字＝数字＋1；

像这样：

你们可以试试看～

这个计算机做当然不会慢，但是人做起来就很傻了，因为我们的数学家高斯已经想到了更好的方案：

方案二

   和    ＝    1  +   2 +  3  +  4  +……＋ 99 +100

   和    ＝ 100 + 99 + 98 + 97 +……＋  2  + 1   

（把上下两列相加，得到：）

和＋和＝  101+101+101+101+ …… ＋101 + 101

和＋和＝ 100个101相加

和 X 2 ＝  101 X 100

所以，和＝101✖️ 100 ➗  2

这样，高斯可以一下子就得到了答案。

方案一的算法虽然很好理解，但是执行次数多，也就意味着：

方案一的算法复杂度高（算法复杂度具体怎么衡量，后面我们会讲）

利用方案二的这个算法，我做了一个可以求1+2+3一直加到任意一个数字的和的程序：

https://idebeta.codemao.cn/w/97206?type=iframe

大家可以试着做出来看看！

算法是非常有意思的，这一次从简单的部分讲起，慢慢讲到排序，二叉树，图的遍历，散列表等等，数据结构上我们也会从数组和链表，讲到栈，队列，树和图。

大家有什么问题，直接在这个帖子上回复我吧！