目录

1，什么是泛型编程

2，泛型的思想来源

3，算法的起源 VS 数学的起源

4，列竖式计算乘法 VS 埃及乘法

5，十进制 VS 二进制

6，加法链

7，严格尾递归

泛型编程是一种专注于对算法及数据结构进行设计的编程方式，它使得这些算法及数据结构能够在不损失效率的前提下，运用到最为通用的环境中。

这种想法是从个数学中衍生出来的，尤其与抽象代数这个数学分支有关。 抽象代数里面的抽象很大程度上是从另外一个数学分支的具体成果中得出的，那个分支比抽象代数更为古老，它叫做数论。

要想成为优秀的程序员，就必须理解泛型编程的原则；要想理解泛型编程的原则，就必须学会抽象；要想学会抽象，就必须知道它所依据的数学基础。

算法（algorithm）是用来完成计算任务的一系列有限步骤。由于算法与计算机编程的关系特别密切，因此很多人或许认为，算法是一个来自计算机科学专业的概念。其实算法这个词已经有几千年历史了。数学中充满了各种各样的算法，有些算法我们天天在用，就连小学生计算加法时所用的竖式（long addition）都可以说是一种算法。

尽管算法的历史很悠久，但它并不是天生就有的，而是由人发明出来的。虽然我们并不清楚第一个发明算法的人是谁，但我们知道，早在四千多年前埃及就已经有了某些算法。

在我们的通常观念中，逻辑简单的问题是不需要算法的，需要算法的都是逻辑比较复杂的问题（比如OJ上的题目）

几千年前，人们用绳子计数，在这个时代，乘法就是一个比较困难的问题，需要算法。

埃及乘法/俄罗斯农夫算法

这种算法所依据的原理是：4a = ((a+a)+a)+a = (a+a) + (a+a), 这个原理是根据加法结合律推算出来的。

如果采用这个办法，那么只需把a+a的值计算一次就行了，这样可以降低加法运算的次数。

埃及乘法算法的思路是：反复地将n减半，并将a加倍，同时求出a的各种倍数，这些倍数与a的比值都是2的整数次幂。

41*59 = 1*59 + 8*59 + 32*59

由于该算法在将n减半的时候需要判断n是奇数还是偶数，因此尽管没有直接的证据，但我们依然能够推测出：古埃及人已经知道了奇数和偶数之间的区别。

埃及乘法，在ACM里面一般叫做快速乘法（算法和快速幂差不多，所以叫法一致）

快速乘法参考：CSU 1162: Balls in the Boxes（快速幂、快速乘法）快速乘法、快速幂、矩阵快速幂_csuzhucong的博客-CSDN博客

列竖式计算两位数的乘法大概是这样的：

诶及乘法用二进制表示大概是这样的：

当然，诶及乘法和二进制列竖式乘法还是有差异的，诶及乘法不涉及进制转换，所以上图的上面一半是二进制列竖式乘法，下面一半才是埃及乘法。

列竖式计算乘法 和 埃及乘法 在泛进制的角度上来看是一样的。

（1）为什么人类使用十进制，机器使用二进制？

因为人类有十个手指头，机器的电路有开关两种状态，各自用各自方便的进制基数。

（2）列竖式计算乘法是怎么来的？

并不是每个国家的小学生计算两位数的乘法的方法都和中国一样，甚至据说有些国家的学生到了小学毕业还是觉得计算乘法很难，因为他们的计算方法不一样，而且据说别的语言的九九乘法表没有汉语这么顺口好记。

我推测，应该是在有了阿拉伯数字和九九乘法表之后，埃及乘法就被合理改造成列竖式计算乘法了。

从这个角度来说，埃及乘法就是一个泛型算法，进制就是数据结构的差异，就好像max函数可以传入int也可以传入double一样。

补更：我在本书中刚好发现了这个科普：

0的突破发生在公元1203年。这一年，比萨的列奥那多（Leonardo Pisano，也称为斐波那契，Fibonacci）出版了一本名为《计算之书》（Liber Abaci）的著作，其中不仅介绍了0与十进制位值计数法，而且首次向欧洲人讲述了算术运算的标准步骤，也就是怎样用竖式来计算加减乘除，这些步骤直到今天依然在小学课堂上传授。我们可以说，列奥那多一举将数学带回了欧洲。

（3）埃及乘法是二进制吗？

二进制应该是近代才发明的，据说是牛顿的老对手莱布尼茨发明的。

埃及乘法被发明的时候没有二进制，用绳子计数只有加减法，没有很强的乘法的概念，更没有除法，也更不会涉及进制转换了。

那为什么埃及算法刚好契合二进制呢？因为，加法是二元操作符，而且，绳子计数可以很快的进行除2操作！

虽然没有除法，但是把绳子对折，这就是天然的除2啊，书中也提到，这个时候的人们应该已经有奇数和偶数的概念了。

书中也提到相关概念，这种乘法是依赖加法结合律的，也就是a+a+a+a+a+a = (a+a) + (a+a) + (a+a) 

看到了吗？每个括号都是把2个数括起来，让6个数相加的问题变成了3个数相加的问题。

这里指的是一个如何计算nx，其中n是已知数，而x是未知数，设计一个对x通用的算法。

（1）埃及乘法的加法次数

设n是一个a位的二进制数，这a位由b个1和a-b个0组成，那么埃及乘法计算nx的过程中，加法的次数是a+b-2

用函数来表示：AJ(n) = a+b-2

当n是1到15时，函数值分别是0,1,2,2,3,3,4,3,4,4,5,4,5,5,6

显然，AJ函数并不是递增函数

（2）加法链

埃及乘法的加法次数是最少的吗？这个算法是最优的吗？

书中给出了反例，显然也是最小的反例：

这个程序其实是先算出b=3x，需要2次加法，再算出5b，需要3次加法，一共需要5次加法

这样一种计算乘法的方式叫做加法链，埃及乘法本身也是一种加法链（长度为1的链）

（3）最优加法链

按照加法链的方式计算乘法，需要的最少加法次数记为L(n)

如果一个加法链，用它计算乘法需要的加法次数是L(n)，那么它就是最优加法链

（4）L函数的性质

L(x)